Raising the bar

The economical way to use the Kuhn-Tucker theorem

M. Baltovic in his guide to Optimization Theory blindly checks the constraint qualification condition for all possible constraints combinations. This is not rational because a) the work can be substantially reduced by properly using the Kuhn-Tucker conditions and b) some constraint combinations may not have sense.

We illustrate this point using Example 6.4:

maximize $latex f(x_1,x_2)=p_1x_1+p_2x_2$ subject to $latex x_1\geq 0$, $latex x_2\geq 0$, $latex x_1^2+x_2^2\leq 1$.

$latex p_1,p_2$ are assumed to be positive. (The solution can be found using also convexity).

The key is to eliminate simple cases one by one

Case 1. Are internal solutions possible? In case of internal solutions, the constraints are irrelevant and FOC's can be applied to the objective function alone. Equations $latex \frac{\partial f}{\partial x_1}=0,\frac{\partial f}{\partial x_2}=0$ give $latex p_1=p_2=0,$ which is impossible.

Denote the boundaries $latex b_1=\{x_1=0\},$ $latex b_2=\{x_2=0\},$ $latex b_3=\{x_1^2+x_2^2=1\}.$ The Kuhn-Tucker conditions are (the numbering follows that in Baltovic):

(6.3) $latex \lambda _1\geq 0,$ $latex x_1\geq 0,$ $latex \lambda _1x_1=0$

(6.4) $latex \lambda _2\geq 0,$ $latex x_2\geq 0,$ $latex \lambda _2x_2=0$

(6.5) $latex \lambda _3\geq 0,$ $latex 1\geq x_1^2+x_2^2,$ $latex \lambda_3(1-x_1^2-x_2^2)=0$

(6.6) $latex p_1+\lambda_1-2\lambda_3x_1=0$

(6.7) $latex p_2+\lambda_2-2\lambda_3x_2=0$

Remember that these conditions work only when the maximizing point satisfies the constraint qualification condition. It is obviously satisfied for $latex b_1,b_2,b_3$ considered separately.

Case 2. Suppose the maximum belongs to only $latex b_1$ (and not to $latex b_1\cap b_2$ or $latex b_1\cap b_3).$ Then from (6.6) $latex p_1=-\lambda_1\leq 0,$ which is impossible.

Case 3. Similarly, if the maximum belongs to only $latex b_2,$ then $latex p_2=-\lambda_2\leq 0,$ which is also impossible.

Case 4. If the maximum belongs only to $latex b_3,$ then $latex x_1,x_2>0$ and from (6.3), (6.4) we see that $latex \lambda_1=\lambda_2=0.$ From (6.5)-(6.7) then

$latex x_1^2+x_2^2=1,$ $latex p_1=2\lambda _3x_1,$ $latex p_2=2\lambda_3x_2.$

This system can be easily solved to give the maximizing point

$latex x_{\max}=\left(\frac{p_1}{\sqrt{p_1^2+p_2^2}},\frac{p_2}{\sqrt{p_1^2+p_2^2}}\right).$

The value of the objective function at this point is

$latex f(x_{\max})=\sqrt{p_1^2+p_2^2}.$

Case 5. The only possibilities that are left are $latex x^{(1)}=(0,0)\in b_1\cap b_2$, $latex x^{(2)}=(0,1)\in b_1\cap b_3$, $latex x^{(3)}=(1,0)\in b_2\cap b_3.$ Don't bother checking the constraint qualification for these points because a) it may fail, in which case the Kuhn-Tucker theorem does not apply, even though any of these points can be a maximum point, and b) even if it holds, none of these points may be a maximum point (the Kuhn-Tucker theorem provides just a necessary condition). Just check directly that $latex f$ at these points takes values lower than at $latex x_{\max}:$

$latex f(x^{(1)})=0,$ $latex f(x^{(2)})=p_2,$ $latex f(x^{(3)})=p_1.$

It's easy to see that $latex f(x_{\max})=\sqrt{p_1^2+p_2^2}\geq\max\{p_1,p_2\}.$

Case 6. The intersection $latex b_1\cap b_2\cap b_3$ is empty, so checking the constraint qualification condition for it is a waste of time.

The solution in Baltovic takes more than three pages.