8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I tried to simplify the equations a bit. If you disagree feel free to roll back my edit. $\endgroup$ – Giskard Oct 20 '15 at 7:04
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yes but can you apply K-K-T to this rephrased problem? $\endgroup$ – Giskard Oct 20 '15 at 6:55
  • 1
    $\begingroup$ 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. $\endgroup$ – user32416 Oct 20 '15 at 7:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Übel Yildmar Oct 20 '15 at 22:00
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Some confusion and misleading statements in the answers given. There are different formulations of KKT theorem. Some are relevant to your (counter-)example and some are not.

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}

Some KKT Theorems one might consider for your example are the following.

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.

$\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.