Does a linear program always attains its infimum?

Question

Consider the following (Lp). $$ \min \;\; \mathbf{c} \cdot \mathbf{x}\\ \text{s.t. } A\mathbf{x} \geq \mathbf{b} \\ \mathbf{x} \geq \mathbf{0} \\ $$ If $S$ is the feasable set of (Lp), Prove that the following definitions are equivalent.

1. (Lp) is unbounded if $\; ∃ \{x^v\}_{v}⊆ S $ $ ;cx^v → −∞ \;$ as $v → ∞.$

2. (Lp) is unbounded if $\; ∀x ∈ S,\; ∃ \,y ∈ S\;;\; c y < cx.$

Proving 1 $\Rightarrow$ 2 is an easy result from the definiton of limits.

Proving 2 $\Rightarrow$ 1 is not easy! There is no guarantee that you can find a sequence whose limit goes to $−∞$. The fact that we have a decreasing sequence of $cx$ for $x ∈ S$ does not necessarily imply (1). Maybe this sequence doesn't get less than a specific number, i.e, it has an infimum in ℝ.

Remark : If all coordinates of $c$ are positive, since we know that $ x >= 0$ it results that for any $x ∈ S$, $cx >= 0.$ In this case of course the limit of any such sequence is not $−∞$.

What are your thoughts? Are these 2 definitions really equivalent?

Answer 1

The existence of an optimal solution is a fundamental concern

Is there an optimal solution? A solution is not worse than any other solution is called an optimal solution.

That is a fundamental question in the theory of linear programming. It is, in fact, a question of foremost importance in any problem that asks to find the optimal value/solution of some objective function.

In the case of linear programming, this question should have been answered in every introductory course on linear programming, either explicitly or implicitly.

As you have pointed out, the answer is not obvious as one might have thought.

(Another fundamental question that usually goes together with the existence is the uniqueness.)

Yes, there is an optimal solution with standard assumptions in linear programming

Assume the objective is to minimize some linear function. The case of maximizing is the same as to minimize the negative of the objective function.

Assume the feasible region is nonempty. Otherwise, there is no solution, let alone an optimal solution.

Assume the objective function in the feasible region is bounded from below. Otherwise, given any solution, there is a solution that lets the objective function take a smaller value.

With the assumptions above, a problem of linear programming given in the canonical form as given in the question, which is repeated below, always has an optimal solution.

$$\begin{array}{rl} \text{find} & {\bf x}\\ \min & {\bf c} \cdot {\bf x}\\ \text{s.t.} &A{\bf x} \geq {\bf b} \\ &{\bf x} \geq \bf0 \\ \end{array}$$

Why does there exist an optimal solution?

Note a linear function on a closed convex subset of $\Bbb R^d$ that is bounded below might not attain its infimum. For example, the function $y$ on the region $\{(x,y)\mid 0<x\text{ and } y\ge 1/x\}$ does not attain its infimum, $0$. So it is not obvious that there exists an optimal solution.

The feasible region, as intersection of half-spaces which are convex spaces, is a possibly-unbounded polyhedron that is also convex. We will use "the polyhedron" and "the feasible region" interchangeably.

Since the objective function is linear, its minimum value on any line segment can be attained on either endpoint of that line segment. Moving a point along line segments in the polyhedron to their endpoints along the direction that lowers the value of the objective function repeatedly, we can either find a boundary point of the polyhedron that attains the infimum of the objective function or realize that the objective function is not bounded from below. This is ensured by the finiteness of the dimension of $\Bbb R^d$ and the "finiteness" of the shape of the boundary of the polyhedron.

Rigorous proof

We can follow along the material given in this course handout.