<p>This is an ill-posed question. Even without going through KKT, your constraint $(x + y - 2)^2 \le 0$, since the left-hand side is a square, means that the only solution that is feasible is the one where the equality binds; i.e. $(x + y - 2)^2 = 0$, or that $|x + y - 2| = 0$ -- of which what you say that $x = y = 1$ is a solution. </p>

CC BY-SA 3.0
2015-10-20T06:55:46.907Z
Yes but can you apply K-K-T to this rephrased problem?
Giskard
CC BY-SA 3.0
2015-10-20T07:01:44.327Z
You're only including the first order stationarity conditions here. But you're completely ignoring the complementary slackness and primal feasibility conditions. Thus what you'd written there is not even the full KKT formulation.
user32416
CC BY-SA 3.0
2015-10-20T22:00:41.393Z
Thank you all for your constructive criticism and help! My prof said that this problem wasn't well defined, because he wanted to represent the importance of Slater's condition.
Übel Yildmar
CC BY-SA 3.0
2015-10-20T06:51:39.980Z
2015-10-20T06:51:39.980Z
user32416
<p>Some confusion and incorrect statements in the answers already given, including the "accepted" answer. (E.g. obvious distinctions between necessity and sufficiency of different conditions for KKT are mixed up.)</p>

<p>There are different formulations of KKT theorem. 
The KKT Theorems one might consider for your example are the following.</p>

<p>For notational simplicity, <span class="math-container">$(x,y)$</span> will be replaced by <span class="math-container">$x$</span>.
For the constrained optimization problem
<span class="math-container">$$
\max_{g(x) \leq 0} f(x),      \quad (*)
$$</span>
consider the KKT conditions</p>

<p><span class="math-container">\begin{align}
\mbox{(i)  } \nabla f &amp;= \lambda \nabla g, \; \mbox{for some } \lambda \geq 0 ,   \\
\mbox{(ii) } \lambda g &amp;= 0 \mbox{ (complementary slackness) }.
\end{align}</span></p>

<p><strong>Theorem (General KKT)</strong>
If <span class="math-container">$x$</span> is a local maximum of <span class="math-container">$(*)$</span> where <span class="math-container">$\nabla g(x) \neq 0$</span>, then (i) and (ii) holds at <span class="math-container">$x$</span>.</p>

<p>The condition <span class="math-container">$\nabla g(x) \neq 0$</span> is called a "constraint qualification" condition.
In other words, the KKT conditions (i) and (ii) are <em>necessary</em> conditions for <em>local</em>
maxima where constraint qualification holds. It says nothing about global maxima.</p>

<p>Even a local maxima where constraint qualification fails need not lie in the solution set of (i) and (ii).</p>

<p>For your example, constraint qualification fails at the global maxima <span class="math-container">$x^* = (1,1)$</span>, <span class="math-container">$\nabla g(x^*) = 0$</span>. So General KKT doesn't apply.</p>

<p><strong>Theorem (KKT Under Concavity)</strong>
Suppose <span class="math-container">$f$</span> is concave and <span class="math-container">$g$</span> is convex. If (i) and (ii) holds at <span class="math-container">$x$</span>, then <span class="math-container">$x$</span> is a global maximum of <span class="math-container">$(*)$</span>.</p>

<p>In other words, when <span class="math-container">$f$</span> is concave and <span class="math-container">$g$</span> is convex, then (i) and (ii) are <em>sufficient</em> condition for <em>global</em> maximum. </p>

<p>In your example, <span class="math-container">$f$</span> is concave and <span class="math-container">$g$</span> is convex. But the solution set of (i) and (ii), with <span class="math-container">$g \leq 0$</span>, is empty---these are vacuous conditions. So KKT Under Concavity doesn't apply.</p>

<p><strong>Theorem (KKT Under Concavity and Slater's Condition)</strong>
Suppose <span class="math-container">$f$</span> is concave, <span class="math-container">$g$</span> is convex, and Slater's condition (<span class="math-container">$\{g &lt;0 \}$</span> is non-empty) holds . If (i) and (ii) holds at <span class="math-container">$x$</span>, then <span class="math-container">$x$</span> is a global maximum of <span class="math-container">$(*)$</span>.</p>

<p>In other words, under Slater's condition (i) and (ii) are now <em>necessary</em> for global maximum. </p>

<p>In your example, Slater's condition doesn't hold. Indeed, the KKT conditions (i) and (ii) cannot be necessary---because, we know (either by Weierstrass, or just by inspection as you have done) a solution to <span class="math-container">$(*)$</span> exists while (i) and (ii) has no solution in <span class="math-container">$\{ g \leq 0 \}$</span>.</p>

<p>Slater's condition is also a kind of constraint qualification. It is <em>not</em> related to complementary slackness. You can convert the original problem <span class="math-container">$(*)$</span> to one with equality constraint and apply Theorem of Lagrange, instead of KKT, but then it does <em>not</em> make sense to speak of Slater's condition.</p>

<p>It is also not correct to say that the problem is ill-posed.
A maximization problem is <em>ill-posed</em> if it does not have a solution. In this case, <span class="math-container">$(*)$</span> is clearly well-posed. The issue is applicability of KKT theorems.</p>

<p>In summary, inspecting the precise statements of various KKT theorems tells you KKT results do not apply to the given (counter-)example.</p>

CC BY-SA 4.0
2019-11-17T05:31:10.333Z
2020-05-29T20:57:07.170Z
2020-05-29T20:57:07.170Z
Michael
<p>As already noted, the constraint is such that it turns itself into an <em>equality</em> constraint. Your problem then is simplified to</p>

<p>$$\max_{x,y} (xy) \;\;\; s.t.\;\; x+y-2=0$$</p>

<p>Rearrange the constraint and substitute for $y$ to obtain the single variable unconstrained problem</p>

<p>$$\max_{x} (2x-x^2)$$</p>

<p>This provides immediately the solution $x=1$ and so also $y=1$.</p>

<p>Using the Karush-Kuhn-Tucker conditions on the original problem, may be good practice in order to see for yourself that the <strong>complementary slackness</strong> condition must also hold (and "Slater's condition" is one of the formulations of it), but Occam's razor would require that the problem should be actually solved as above.</p>

CC BY-SA 3.0
2015-10-20T17:50:50.357Z
2015-10-20T17:50:50.357Z
Alecos Papadopoulos
<p>As @user32416 pointed out the first order stationarity conditions are not enough. Specifically it seems that you violate <a href="https://en.wikipedia.org/wiki/Slater%27s_condition" rel="noreferrer">Slater's condition</a>, which states that "the feasible region must have an interior point". There are no $x,y$ for which 
$$(x+y-2)^2 &lt; 0.$$</p>

<p>If you rephrase the problem to
$$\max (xy)$$
$$x+y-2 = 0$$
$$x,y \geq 0$$
Slater's condition is met (for linear conditions no interior points are necessary) and you can apply Karush-Kuhn-Tucker.</p>

CC BY-SA 3.0
2015-10-20T06:42:13.723Z
2015-10-20T09:12:55.247Z
2015-10-20T09:12:55.247Z
Giskard
<p>I have the following utility maximization problem:
$$\max (xy)$$
$$(x+y-2)^2 \leq 0$$
Conditions:
$$y-2\lambda (x+y-2) =0$$
$$x-2\lambda (x+y-2) =0$$
$$\lambda(x+y-2)^2=0$$</p>

<p>When I set $\lambda&gt;0$, I get:
$$(x+y-2)^2=0 \Rightarrow (x+y-2) = 0$$
$$y-2\lambda (x+y-2) = y = 0$$
$$x-2\lambda (x+y-2) = x = 0$$</p>

<p>But the obvious solution is $x=y=1$.</p>

<p>When I set $$\lambda=0$$ that's not a case with a valid solution either. Is the constraint too low? What is the explanation to this?</p>

<p>I would greatly appreciate your help.</p>

CC BY-SA 3.0
2015-10-20T07:04:37.370Z
I tried to simplify the equations a bit. If you disagree feel free to roll back my edit.
Giskard
<utility><optimization>
Why couldn't the Karush-Kuhn-Tucker optimization find the solution?
Übel Yildmar
# Why couldn't the Karush-Kuhn-Tucker optimization find the solution?

(Asked by: username_0 on 2015-10-20)

I have the following utility maximization problem:
$$\max (xy)$$
$$(x+y-2)^2 \leq 0$$
Conditions:
$$y-2\lambda (x+y-2) =0$$
$$x-2\lambda (x+y-2) =0$$
$$\lambda(x+y-2)^2=0$$

When I set $\lambda>0$, I get:
$$(x+y-2)^2=0 \Rightarrow (x+y-2) = 0$$
$$y-2\lambda (x+y-2) = y = 0$$
$$x-2\lambda (x+y-2) = x = 0$$

But the obvious solution is $x=y=1$.

When I set $$\lambda=0$$ that's not a case with a valid solution either. Is the constraint too low? What is the explanation to this?

I would greatly appreciate your help.

**Tags:** utility, optimization

> **Comments:**
> **username_1**: I tried to simplify the equations a bit. If you disagree feel free to roll back my edit.  

---

## 4 answers

### Answer by username_1 on 2015-10-20. Score: 7 | Accepted answer

As @username_2 pointed out the first order stationarity conditions are not enough. Specifically it seems that you violate [Slater's condition](https://en.wikipedia.org/wiki/Slater%27s_condition), which states that "the feasible region must have an interior point". There are no $x,y$ for which
$$(x+y-2)^2 < 0.$$

If you rephrase the problem to
$$\max (xy)$$
$$x+y-2 = 0$$
$$x,y \geq 0$$
Slater's condition is met (for linear conditions no interior points are necessary) and you can apply Karush-Kuhn-Tucker.


---

### Answer by username_2 on 2015-10-20. Score: 6

This is an ill-posed question. Even without going through KKT, your constraint $(x + y - 2)^2 \le 0$, since the left-hand side is a square, means that the only solution that is feasible is the one where the equality binds; i.e. $(x + y - 2)^2 = 0$, or that $|x + y - 2| = 0$ -- of which what you say that $x = y = 1$ is a solution.

> **Comments:**
> **username_1**: Yes but can you apply K-K-T to this rephrased problem?  
> **username_2**: You're only including the first order stationarity conditions here. But you're completely ignoring the complementary slackness and primal feasibility conditions. Thus what you'd written there is not even the full KKT formulation.  
> **username_0**: Thank you all for your constructive criticism and help! My prof said that this problem wasn't well defined, because he wanted to represent the importance of Slater's condition.  

---

### Answer by username_3 on 2019-11-17. Score: 5

Some confusion and incorrect statements in the answers already given, including the "accepted" answer. (E.g. obvious distinctions between necessity and sufficiency of different conditions for KKT are mixed up.)

There are different formulations of KKT theorem.
The KKT Theorems one might consider for your example are the following.

For notational simplicity, $(x,y)$ will be replaced by $x$.
For the constrained optimization problem
$$
\max\_{g(x) \leq 0} f(x), \quad (\*)
$$
consider the KKT conditions

\begin{align}
\mbox{(i) } \nabla f &= \lambda \nabla g, \; \mbox{for some } \lambda \geq 0 , \\
\mbox{(ii) } \lambda g &= 0 \mbox{ (complementary slackness) }.
\end{align}

**Theorem (General KKT)**
If $x$ is a local maximum of $(\*)$ where $\nabla g(x) \neq 0$, then (i) and (ii) holds at $x$.

The condition $\nabla g(x) \neq 0$ is called a "constraint qualification" condition.
In other words, the KKT conditions (i) and (ii) are *necessary* conditions for *local*
maxima where constraint qualification holds. It says nothing about global maxima.

Even a local maxima where constraint qualification fails need not lie in the solution set of (i) and (ii).

For your example, constraint qualification fails at the global maxima $x^\* = (1,1)$, $\nabla g(x^\*) = 0$. So General KKT doesn't apply.

**Theorem (KKT Under Concavity)**
Suppose $f$ is concave and $g$ is convex. If (i) and (ii) holds at $x$, then $x$ is a global maximum of $(\*)$.

In other words, when $f$ is concave and $g$ is convex, then (i) and (ii) are *sufficient* condition for *global* maximum.

In your example, $f$ is concave and $g$ is convex. But the solution set of (i) and (ii), with $g \leq 0$, is empty---these are vacuous conditions. So KKT Under Concavity doesn't apply.

**Theorem (KKT Under Concavity and Slater's Condition)**
Suppose $f$ is concave, $g$ is convex, and Slater's condition ($\{g <0 \}$ is non-empty) holds . If (i) and (ii) holds at $x$, then $x$ is a global maximum of $(\*)$.

In other words, under Slater's condition (i) and (ii) are now *necessary* for global maximum.

In your example, Slater's condition doesn't hold. Indeed, the KKT conditions (i) and (ii) cannot be necessary---because, we know (either by Weierstrass, or just by inspection as you have done) a solution to $(\*)$ exists while (i) and (ii) has no solution in $\{ g \leq 0 \}$.

Slater's condition is also a kind of constraint qualification. It is *not* related to complementary slackness. You can convert the original problem $(\*)$ to one with equality constraint and apply Theorem of Lagrange, instead of KKT, but then it does *not* make sense to speak of Slater's condition.

It is also not correct to say that the problem is ill-posed.
A maximization problem is *ill-posed* if it does not have a solution. In this case, $(\*)$ is clearly well-posed. The issue is applicability of KKT theorems.

In summary, inspecting the precise statements of various KKT theorems tells you KKT results do not apply to the given (counter-)example.


---

### Answer by username_4 on 2015-10-20. Score: 2

As already noted, the constraint is such that it turns itself into an *equality* constraint. Your problem then is simplified to

$$\max\_{x,y} (xy) \;\;\; s.t.\;\; x+y-2=0$$

Rearrange the constraint and substitute for $y$ to obtain the single variable unconstrained problem

$$\max\_{x} (2x-x^2)$$

This provides immediately the solution $x=1$ and so also $y=1$.

Using the Karush-Kuhn-Tucker conditions on the original problem, may be good practice in order to see for yourself that the **complementary slackness** condition must also hold (and "Slater's condition" is one of the formulations of it), but Occam's razor would require that the problem should be actually solved as above.


---

