Solving optimization problem using KKT conditions

Question

Consider the following objective:

$$\min_{x,y} 2x +y$$ subject to:

$$\sqrt{x^2+y^2} \leq 2$$

$$x\geq 0$$

$$y \geq 0.5x-1$$

The lagrangian is given by: $$ L(x,y,\lambda_1,\lambda_2,\lambda_3)=2x +y + \lambda_1 \left(\sqrt{x^2+y^2} - 2\right) - \lambda_2 x + \lambda_3(0.5x-y-1)$$

Stationarity implies: $$2 + \lambda_1 (\frac{x}{\sqrt{x^2+y^2}}) + 0.5\lambda_3 =0$$

$$1 + \lambda_2 (\frac{y}{\sqrt{x^2+y^2}})- \lambda_2 -\lambda_3 =0$$

Dual feasibility: $$\lambda_i\geq 0$$ Complementary slackness: $$\lambda_1 \left(\sqrt{x^2+y^2} - 2\right) =0$$ $$\lambda_2 (-x) =0$$ $$\lambda_3 (0.5x-y-1) =0$$

Is there a easy way to solve this or do I have to take all 9 possible combinations consisting of active/inactive constraints and $\lambda_i>0$ or $\lambda_i=0$ into account?

In every case I end up with a contradiction to any of these conditions. Only the the case, where the first and third constraint are active and $\lambda_2>0$ cannot be resolved from my side. Am I on the right track?

Answer 1

Rewriting the problem as $$\min_{x,y} \: 2x + y \\ \quad\quad \text{s.t. } x^2 + y^2 \leq 4, \\ \:\:\: x \geq 0, \\ \quad\qquad y \geq 0.5x - 1,$$ we get the Lagrangian $$L(x,y,\lambda_1,\lambda_2,\lambda_3) = 2x + y + \lambda_1 (x^2 + y^2 - 4) - \lambda_2 x + \lambda_3(0.5x - 1 - y).$$ We require the following conditions:

• Stationarity: $2 + 2\lambda_1 - \lambda_2 + 0.5\lambda_3 = 0$ and $1 + 2\lambda_1 - \lambda_3 = 0$.
• Primal feasibility: $x^2 + y^2 \leq 4$, $x \geq 0$, and $y \geq 0.5x - 1$.
• Dual feasibility: $\lambda_1, \lambda_2, \lambda_3 \geq 0$.
• Complementary slackness: $\lambda_1 ( x^2 + y^2 - 4) = 0$, $\lambda_2 x = 0$, and $\lambda_3 (0.5x - 1 - y) = 0$.

Assuming that constraints $1$ and $3$ are active, we have $\lambda_2 = 0$ from complementary slackness. Then, the stationarity conditions yield $\lambda_1 = -1.25$ and $\lambda_3 = 1$, which violates dual feasibility.

Assuming that constraints $2$ and $3$ are active, we have $\lambda_1 = 0$, $\lambda_2 = 2.5$, and $\lambda_3 = 1$. From complementary slackness, we get $x = 0$ and $y = -1$. Incidentally, this case corresponds to the minimum.

You can check the other six conditions.

Answer 2

The problem is convex, which means that any KKT point is the global minimizer. Hence, it is hardly to exist many KKT points (=many global minimizers), most likely just one, so many cases are expected to give you a contradiction. To see which case contains the KKT point you may draw a picture — the problem is two-dimensional. The picture should contain the feasibility set of constraints and several level sets of the objective function $2x+y=Const$ (the black lines). To minimize graphically is to move the level sets against the gradient $(2,1)$, i.e. from right to left, so that it is still in touch with the feasibility set. The minimum is attained at $(0,-1)$ where the constraints 2 and 3 are active. It is left to see that it is a KKT point.