# Why couldn't the Karush-Kuhn-Tucker optimization find the solution?

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.

• I tried to simplify the equations a bit. If you disagree feel free to roll back my edit. Oct 20, 2015 at 7:04

As @user32416 pointed out the first order stationarity conditions are not enough. Specifically it seems that you violate Slater's 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.

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.

• Yes but can you apply K-K-T to this rephrased problem? Oct 20, 2015 at 6:55
• 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. Oct 20, 2015 at 7:01
• 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. Oct 20, 2015 at 22:00

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.

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.