0
$\begingroup$

I don't have a solid background about using a KKT theorem. So, I want to check my answer is correct or not.

The problem is the following :

Minimize $f = x+y$ subject to $(x-1)^2 + y^2 \leq 1$, $(x+1)^2 + y^2 \leq 1$, where $(x,y) \in R^2$. Show that the optimal solution $(x,y)$ does not satisfy the conditions of the Karush–Kuhn–Tucker theorem. Explain what hypotheses of the theorem are violated, and why.

My attempt : Let $g_1$ be $(x-1)^2 + y^2 -1$ and $g_2$ be $(x+1)^2 +y^2 -1$. Since there is only one point in this feasible region, namely, $(0,0)$, we can suppose that this point is optimal solution for this convex optimization problem.

By the KKT of gradient form, we already know that $\bigtriangledown f(0, 0)+ \bigtriangledown g_1(0,0) + \bigtriangledown g_2(0,0) = (0,0)$. But, this is impossible in this convex programming problem. Thus, it does not satisfy this condition of KKT gradient form.

Is my attempt correct idea? I'm not sure.

$\endgroup$
  • $\begingroup$ $(x+y)^2=x^2+y^2 +2xy$, $(x-1)^2 +y^2-1=x^2 +y^2-2x≤ 0$. Subtracting these relations we get:$(x+y)^2 ≥ 2xy +2x$ , at$ x=0$ and$ y=0$, $ x+y=0$ .Now $(x+1)^2 +y^2-1=x^2+y^2+2x≤0$. Subtracting from first equation we get $(x+y)^2≥2xy-2x$. $x=y=0$ and $x=y=1$ can be the results. So the minimum of x+y can be between 0 and 1 $\endgroup$ – sirous Nov 4 '17 at 5:40
0
$\begingroup$

My guess is that the constraint qualification is not satisfied in this example. You do not mention what constraint qualification (CQ) you are considering in the KKT conditions. For instance, Slater's condition is not satisfied in your example since there is no strictly feasible point, as $g_i(0, 0) = 0$ for $i = 1, 2$ and $(0, 0)$ is the only point in the feasible region.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.