I have two constraints in a linear programming model:
x1 + x2 <= 5
x1 >= 2
Note that there are no nonnegativity constraints so the problem is unbounded from below.
The point (2,3) is the only extreme point and, if the problem is a maximization problem, it is the optimal solution. Now I've been asked to provide three linear functions which are maximized at this point. Fair enough, we have to solve the linear combination for the two constraints (which is the intersection where we get the point (2,3):
y1 (x1 + x2 = 5)
+
y2 (-x1 = -2)
yields ax1 + bx2 = c
Now it is said that for a maximised (optimal) function, the associated y values must b non-negative. Can anyone explain me why? Indeed I tested this, negative ys give functions that are minimized at this point, while positive ys give functions that are maximized. Why do they have to be positive to yield a function that is maximized at (3,2)?
Thanks!
Best Answer
A little abstraction helps here, I think. (Note that my discussion assumes that the feasible set is non-empty. This is true in your example.)
Consider the problem $\max \{d^T x | a_i^T x \leq b_i, \ \ i = 1,...,n \}$.
Suppose you are at some feasible point $x$, and for some direction $h$ the following conditions are satisfied: (1) $a_i^T h \leq 0$ for all $i$, and (2) $d^Th >0$. By considering the point $x(t) = x+th$, you can see that the objective can be increased arbitrarily while keeping the constraints satisfied.
Consequently, to have a bounded maximum, it must be the case (ie, a necessary condition) that if $a_i^T h \leq 0$ for all $i$, then $d^Th \leq0$. This is an important point. The remainder of the answer is showing the connection between this condition and the non-negativity you asked about.
First, a small digression to provide some intuition. Suppose you have two closed linear subspaces $A,B$. Then you have $A \subset B$ iff $B^\bot \subset A^\bot$. In my opinion, this duality (with suitable generalizations) is the essence of understanding and obtaining useful geometric characterizations of many optimality conditions.
Now consider a non-empty closed convex cone $K$. Notations and definitions vary a bit here, but I will define the polar of $K$ to be $K^\bot = \{h | x^T h \leq 0, \ \forall x \in K \}$. The definition matches that of orthogonal complement for subspaces. The essential point here is that if you have two non-empty closed convex cones $K_1, K_2$, then $K_1 \subset K_2$ iff $K_2^\bot \subset K_1^\bot$. You see the formal similarity with subspaces here.
Now return to our problem. Let $A = \mathbb{cone} \{a_i\} = \{ \sum \lambda_i a_i | \lambda_i \geq 0 \}$. $A$ is a non-empty convex cone. A point $x \in A$ iff $x$ can be written as a non-negative combination of the $a_i$. Let $D = \mathbb{cone} \{d \} = \{\lambda d\}_{\lambda \geq 0}$. Then we can rephrase the condition above as if the problem is to have a bounded maximum, we must have $A^\bot \subset D^\bot$. However, this is equivalent to $D \subset A$ by duality, from which we obtain that $d = \sum_i \lambda_i a_i$ for some non-negative constants $\lambda_i$.
In your example, $a_1 = (1,1)^T, a_2 = (-1,0)^T$. Hence to have a bounded maximum, $d = (d_1,d_2)$ must satisfy $d_1\leq d_2$, $d_2 \geq 0$.
Now notice that if we can write $d = \sum_i \lambda_i a_i$ with $\lambda_i \geq 0$, then it follows that the maximum is bounded, because $d^T x = \sum_i \lambda_i a_i^T x \leq \sum_i \lambda_i b_i$. This shows that in your example, since you have a point $(2,3)^T$ for which all constraints are active, then $a_1^T (2,3)^T = 5$ and $a_2^T (2,3)^T = -2$, then the maximum will be attained at that point and the maximum is given by $5 \lambda_1 - 2 \lambda_2$.