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?
Best Answer
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:
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.