bounded vs. unbounded linear programs

Question

Consider a (linear) optimization problem of the form "maximize $c^{\top}x$ subject to $\varphi(x)$". Consider the following definitions:

1. The program is called unbounded iff it is feasible but its objective function can be made arbitrarily "good" [script1], i.e., the objective function can assume arbitrarily large positive values at feasible vectors [script2].

2. The program is called bounded iff the maximum is attained (in other words, the maximum exists) [Theory of linear and integer programming, Schrijver 1986].

3. The program is called bounded iff it is not unbounded [script2].

The definition of "unbounded" (1.) seems pretty standard. However, the definitions of "bounded" (2. and 3.) are not: 2. is different from 3.

What I am asking for is a suggestion for a clean terminology in the context of linear programming which suits both the mathematical needs (e.g., the Duality Theorem) and is good English at the same time. Of course, each author, including the two above, uses his/her clean, consistent terminology system. Thus, here I am asking not only for good, consistent terminology but also for an explanation, i.e., a rationale behind it.

If such a discussion is available elsewhere, I'd be glad to have a reference. Perhaps, there might be synonyms for the terms bounded/unbounded which one can use without risking ambiguity.

I am thinking of dropping the term "bounded" altogether to sidestep the ambiguity and introducing only the concepts "feasibly bounded" / "feasible bounded" and "unbounded". (Of course, the concepts "feasible" and "infeasible" are introduced before that.) What do you think?

Answer 1

The theory of dual linear programs is most easily explained using both feasible versus infeasible as well as bounded vs. unbounded to describe linear programs. There may be linear programming topics where we could get by with a more limited vocabulary, but duality seems not to be amenable to such treatment.

The discussion below is intended to outline the usefulness of bounded versus unbounded solutions limited to the case of feasible programs. In this case the OP has acknowledged that the concepts are exactly complementary.

Certainly we want to be able to state two results, a weak duality and a strong duality theorem. To begin with we want to define a primal program and its dual program. Typically one does not try to do this in utter generality. Rather (see Applied Mathematical Programming, Sec. 4.2 here) we usually confine the discussion to a primal program that is in standard form:

$$\begin{align*} &\mbox{maximize} & c^T x \\ &\mbox{subject to} & Ax \le b \\ &\mbox{and} & x \ge 0 \end{align*}$$

for which a symmetric dual problem can be formulated:

$$\begin{align*} &\mbox{minimize} & b^T y \\ &\mbox{subject to} & A^T y \ge c \\ &\mbox{and} & y \ge 0 \end{align*}$$

So far we have placed no restrictions on these linear programs other than assuming the standard form of the primal problem. Given this rather basic setup, we can state:

• (Weak Duality Property) If $x$ is a feasible solution of the primal problem and $y$ a feasible solution of the dual problem, then $c^T x \le b^T y$.

Existence of feasible solutions of both problems is clearly essential to being able to state this result, but no assumptions about bounded or unbounded programs need to be made. On the other hand, some further duality statements do need those concepts:

• (Strong Duality Property) If the primal problem has a finite optimal solution, then so does the dual problem, and the two optimal values of respective objective functions are equal.

• (Unboundedness Property) If the primal problem (resp. the dual problem) has unbounded solutions, then the dual problem (resp. the primal problem) is infeasible.

Note 1: Unbounded solutions for the primal problem, because it is a maximization of the objective, means arbitrarily "high" values are attained by feasible points $x$. Unbounded solutions for the dual problem, because it is a minimization of the objective, means arbitrarily "low" values are attained by feasible points $y$.

Note 2: We have combined two statements in the latter formulation, but these are not converses! Rather the roles of the primal problem and the dual problem can be interchanged, but there is no claim that infeasibility of one implies unboundedness of the other. That would be false, in view of the fact that both the primal and the dual problems can be infeasible (in fact all four feasibility vs. infeasibility possibilities are viable).

It is not my intention to go into proof details for these statements, only to show by giving them that separate semantic importance attaches to feasible vs. infeasible and bounded vs. unbounded.

Answer 2

Let's say that the constraints $\varphi(x)$ determine a non-empty set $X$ of feasible points.

Bounded: The linear program is bounded if there exists an $M\in \mathbb{R}$ such that $c^{T}x\leq M$ for all $x\in X$.

Note that this is equivalent to the first definition (not too hard to see). If the max value exists, take $M$ to be that max value. If there is such an $M$, then there is a least such $M$ (least upper bound property) and that least upper bound will be a max (provided that the feasible region is compact).

This definition (which is what I was taught) is nice because it is consistent with many other definitions of boundedness. For example, a sequence $(x_n)_{n=1}^{\infty}$ is bounded if $x_n\leq M$ for all $n$. A subset $S$ of $\mathbb{R}^{n}$ is bounded if there exists an $M$ so that $\Vert x\Vert \leq M$ for all $x\in S$. And certainly many others.

Similarly the "reverse" definition makes sense for unbounded.

Unbounded: The linear program is unbounded if for any $M\in \mathbb{R}$ there exists an $x\in X$ such that $c^{T}x>M$. Note that being unbounded implies that the feasible region $X$ is non-empty.

Hope this helps for some rationale.