Raising the bar constraint qualification Archives

Dec 17

The right solution to Example 6.5

The right solution to Example 6.5

The treatment of Example 6.5 in Baltovic's guide is confusing. The exposition indicates a problem but does not provide the explanation. Before reading this post try to solve the exercise on your own following the economical way.

Example 6.5. Consider the cost-minimisation problem of a consumer:

minimise $f(x_1,x_2)=w_1x_1+w_2x_2$ subject to $h_1(x_1,x_2)=x_1\geq 0$ , $h_2(x_1,x_2)=x_2\geq 0$ , $h_3(x_1,x_2)=x_1^2+x_2^2\geq 1.$

Don't forget that in case of minimization the lambdas in the Lagrangian should be taken with negative signs. It is assumed that $w_1,w_2>0.$

Case 1. Internal solutions are impossible because the first order conditions for $f$ give $w_1=w_2=0.$

Denote the boundaries $b_1=\{x_1=0\},$ $b_2=\{x_2=0\},$ $b_3=\{x_1^2+x_2^2=1\}.$ The Kuhn-Tucker conditions are:

(1) $\lambda_1\geq 0,$ $x_1\geq 0$ , $\lambda_1x_1=0$

(2) $\lambda_2\geq 0$ , $x_2\geq 0$ , $\lambda _2x_2=0$

(3) $\lambda_3\geq 0$ , $1\leq x_1^2+x_2^2,$ $\lambda_3(x_1^2+x_2^2-1)=0$

(4) $w_1-\lambda_1-2\lambda_3x_1=0$

(5) $w_2-\lambda_2-2\lambda_3x_2=0$

The constraint qualification condition is obviously satisfied for $b_1,b_2,b_3$ considered separately.

Case 2. $x$ belongs to $b_{1}$ only. Then $x$ does not belong to $b_{2}$ and $b_{3}$ and from complementary slackness $\lambda_2=\lambda_3=0.$ Then from (5) $w_2=0,$ which is nonsense.

Case 3. Similarly, if $x$ belongs to $b_2$ only, then $w_1=0,$ which is impossible.

Case 4. $x$ belongs to $b_3$ only. Then $x_1,x_2>0$ and from complementary slackness $\lambda_1=\lambda_2=0.$ (3)-(5) simplify to $x_1^2+x_2^2=1$ , $w_1-2\lambda_3x_1=0$ , $w_2-2\lambda_3x_2=0.$ The solution to this system is

$x^{(0)}=\left(\frac{w_1}{\sqrt{w_1^2+w_2^2}},\frac{w_2}{\sqrt{w_1^2+w_2^2}}\right),$ $\lambda=\frac{\sqrt{w_1^2+w_2^2}}{2}$

and the value of the objective function at this point is

$f(x^{(0)})=\sqrt{w_1^2+w_2^2}.$

Case 5. The only possibilities left are $x^{(1)}=(0,1)\in b_1\cap b_3,$ $x^{(2)}=(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 minimum point, and b) even if it holds, none of these points may be a minimum point (the Kuhn-Tucker theorem provides just a necessary condition). Just check directly the values of $f$ at these points:

$f(x^{(1)})=w_2,$ $f(x^{(2)})=w_1.$

Since $w_1,w_2$ are strictly positive, we see that $f(x^{(0)})=\sqrt{w_1^2+w_2^2}>\max\{w_1,w_2\}.$ Thus, $f(x^{(1)})$ is the minimum if $w_2<w_1,$ $f(x^{(2)})$ is the minimum if $w_2>w_1$ and we have two minimum points in case of a tie $w_2=w_1.$

Conclusion: the Kuhn-Tucker does work in this case!

Tags: complementary slackness, constraint qualification, cost-minimisation problem, Kuhn-Tucker conditions, solution to Example 6.5

Dec 17

The economical way to use the Kuhn-Tucker theorem

category: MT3042 Optimisation theory, Optimisation theory no comments

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 $f(x_1,x_2)=p_1x_1+p_2x_2$ subject to $x_1\geq 0$ , $x_2\geq 0$ , $x_1^2+x_2^2\leq 1$ .

$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 $\frac{\partial f}{\partial x_1}=0,\frac{\partial f}{\partial x_2}=0$ give $p_1=p_2=0,$ which is impossible.

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

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

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

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

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

(6.7) $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 $b_1,b_2,b_3$ considered separately.

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

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

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

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

This system can be easily solved to give the maximizing point

$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

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

Case 5. The only possibilities that are left are $x^{(1)}=(0,0)\in b_1\cap b_2$ , $x^{(2)}=(0,1)\in b_1\cap b_3$ , $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 $f$ at these points takes values lower than at $x_{\max}:$