# How to solve this polynomial optimization problem using KKT conditions?

I am trying to find a general recipe for a nonlinear constrained optimization problems. Please correct where wrong or where parts are missing.

\begin{aligned} &\min &f(x,y)&=xy+y^3\\ &\text{such that }&x &\geq y^2\\ &&x+y&\leq 2 \end{aligned}

Write in standard maximization problem form

\begin{aligned} &\max &&-xy-y^3\\ &\text{such that }&y^2-x &\leq 0\\ &&x+y&\leq 2 \end{aligned}

Find feasible points where Kuhn-Tucker CQ (constraint qualification) does not hold.

$$\text{gradient 1st constraint: } (-1, 2y)\\ \text{gradient 2nd constraint: } (1,1)$$

gradient 1st constraint is never linearly dependent. (never equal to $(0,0)$ for any $y$)

gradient 2nd constraint is never linearly dependent.

Both gradients of constraints are linearly dependent if $y=-\frac{1}{2}$

Note that the 2nd constraint in this case is binding if $x=2\frac{1}{2}$. Then the 1st constraint is not binding: $y^2-x=\frac{1}{4}-2\frac{1}{2}\neq 0$. As CQ qualification does only apply to binding constraints (and it is not binding here), we conclude CQ holds for all feasible points.

What do you do if you find a feasible point where CQ does not hold? (where the point is binding for all(?) constraints)

If there are more than 2 contraints, do you check them pairwise too?

Write down the KT conditions

First write down the Lagrangian: $\mathcal{L}=-xy-y^3-\lambda(y^2-x)-\mu(x+y-2)$

Take partial derivatives, set them equal to $0$

\begin{aligned} \text{KT conditions: }&-y +\lambda-\mu&=0\\\ &-x-3y^2-2\lambda y-\mu&=0\\ &\lambda,\mu&\geq 0\\ &\lambda(y^2-x)&=0\\ &\mu(x+y-2)&=0 \end{aligned}

Find all points satisfying the KT conditions

Especially the 3rd constraint is important, it induces 4 cases:

(a) $\lambda =0,\mu=0$

(b) $\lambda =0,\mu>0$

(c) $\lambda>0, \mu=0$

(d) $\lambda>0, \mu>0$

(a): $\lambda =0,\mu=0\stackrel{eq. 1}{\implies} y=0\stackrel{eq. 2}{\implies}x=0$ which satisfy all conditions.

(b):$\lambda =0,\mu>0\stackrel{eq. 5}{\implies}x+y=2\iff -x = y-2$. Also $eq. 1$ implies $y=-\mu$. We substitute this in the 2nd equation. $y-2-3y^2+y=0$, solving this gives,

$$3y^2-2y+2=0\implies y=\frac{2\pm\sqrt{4-24}}{6}\notin\mathbb{R}\text{ contradiction}$$

(c) $\lambda>0, \mu=0\stackrel{eq. 4}{\implies} y^2-x=0\implies -x=-y^2$. Also $eq. 1$ implies $\lambda = y$. Plug this in $eq. 2$ gives,

$$-y^2-3y^2-2y^2=0\iff y=0, \text{ contradiction as }y=\lambda>0$$

(d) $\lambda>0, \mu>0$, implies $y^2-x=0\implies x=y^2$ and $x+y-2=0$. Plug in the first in the second equation here, $y^2 + y - 2=0$

$$y^2+y-2=0\implies y=\frac{1}{2}(-1\pm\sqrt{9})=1\text{ or } 2.$$

Then $x=1$ or $4$. Thus $(x,y)=(1,1)\text{ or }(4,-2)$.

Let $(x,y)=(1,1)$, $\lambda-\mu=1\implies \lambda=1+\mu$. Plug in into $eq. 2$

$$-1-3-2\lambda-\mu=0\\ \mu=-2 \text{ contradiction as }\mu>0$$

Let $(x,y)=(4,-2)$, then $-\mu=-2-\lambda$ substituting gin $eq. 2$ gives $\lambda=6,\mu=8$

We now have 2 points: $(0,0)$ with $\lambda=0, \mu=0$ and $(4,-2)$ with $\lambda=6, \mu=8$

Apply Extreme Value Theorem (EVT) if possible

The feasible set is compact and $xy+y^3$ is continuous so EVT applies.

$$f(0,0)=0, \quad f(4,-2)=-16\implies \min \text{ at } (4,-2)$$

Done. (questions are in italic)

When applying the necessary KKT condition you need to work out the following:

1. Prove that the optimum exists using EVT. Sometimes when the set is not compact you may do some tricks (by cutting off the set points that are not important for optimization) to find an equivalent problem with a compact set.
2. List all "pathological" points i.e. points where the CQ condition is not satisfied.
3. List all KKT points.
4. Pick the candidate from 2,3 that gives the optimal value of the objective function.

Thus, if you find a point where the gradients to binding constraints do not satify the CQ condition, you just add those to the list of candidates to test in 4. If there are more than 2 constraints, for example, if you have three constraints, then you need to test $2^3-1$ cases: $3$ when only one is binding, $3$ when two of them are binding and $1$ case when all three are binding. For $n$ constraints, it is $2^n-1$ cases to check, in general. It is approximately the same procedure that you used in KKT cases (a), (b), (c), (d).

• Clear, thank you so much! I'm not sure what "pathological points" mean in this context. – Zohaad Fazal Jan 8 '18 at 16:21
• Also, I think the KKT cases in (a), (b), (c), (d) would be $2^n$ cases (it is binary for activating constraints). For CQ it is $2^n -1$. – Zohaad Fazal Jan 8 '18 at 16:29
• @ZohaadFazal "Pathological" points = where a CQ condition (there are different CQ) is violated. – A.Γ. Jan 8 '18 at 16:43
• @ZohaadFazal Yes, $2^n$ for KKT and $2^n-1$ for CQ. It becomes expensive for many constraints, even numerically (like the active set method). – A.Γ. Jan 8 '18 at 16:56

If $(x,y)=(4,-2)$ we get a value $-16$.

We'll prove that it's a minimal value.

Indeed, our conditions give $$y+y^2\leq x+y\leq2,$$ which gives $$-2\leq y\leq1.$$

Also, it's obvious that $x\geq0.$

Thus, $$xy+y^3\geq -2x+y^3\geq-2(2-y)+y^3=y^3+2y-4\geq-16$$ and we are done!

• How did you obtain $(x,y)=(4,-2)$? Also, we're supposed to solve this using KKT-conditions. – Zohaad Fazal Jan 8 '18 at 14:21
• From $-2\leq y\leq1$. I tried $y=1$ and $y=-2$ and the last was valid. – Michael Rozenberg Jan 8 '18 at 14:23
• This answer, though correct, would not pass on my exam if the problem says solve using KKT conditions. The point is not to find the optimal solution, the point is to show that you have learned KKT method. – A.Γ. Jan 8 '18 at 15:51
• @A.Γ. Is the point to show that the OP learned the KKT method, or that a poster on Mathematics Stack Exchange learned the KKT method? – Mark L. Stone Jan 8 '18 at 16:37
• @MarkL.Stone Both - if they take the exam I was talking about. – A.Γ. Jan 8 '18 at 17:04