0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You should have $-\lambda_2 x$ in the Lagrangian instead of $-\lambda_2 y$. Additionally, you also need $\lambda_2, \lambda_3 \geq 0$ for dual feasibility. Finally, you also need to impose primal feasibility (the 3 constraints on $x$ and $y$). Otherwise, I think you are on the right track (looking at the $2^3$ possible set of active constraints and solving for the variables and multipliers in each case). One thing you can do to simplify the computation is to notice that you can derive an equivalent formulation by replacing $\sqrt{x^2 + y^2} \leq 2$ with $x^2 + y^2 \leq 4$. $\endgroup$ Commented Jan 24, 2023 at 18:05
  • $\begingroup$ Thank you. How would you compute the case first and third constraint are active and second is inactive. I cannot arrive at a reasonable result? $\endgroup$ Commented Jan 24, 2023 at 18:33

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry for the late response. Thank you for your answer. $\endgroup$ Commented Jan 28, 2023 at 13:36
1
$\begingroup$

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.

enter image description here

$\endgroup$
2
  • $\begingroup$ It is probably worth mentioning that the KKT conditions are necessary for convex problems only when a constraint qualification holds (e.g., Slater's CQ, which holds for this problem). $\endgroup$ Commented Jan 24, 2023 at 21:01
  • 1
    $\begingroup$ @madnessweasley It is true, however the necessity direction seems less appealing here as the KKT point is very easy to calculate. Once found, it is sufficient for the global minimum due to convexity without extra assumptions like CQ etc $\endgroup$ Commented Jan 24, 2023 at 21:08

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.