2
$\begingroup$

Consider the following problem $$\max \Big(x_1-\frac{9}{4}\Big)^2+\big(x_2-2\big)^2$$ $$s.t.\quad x_2-x_1^2\ge0\\ x_1+x_2\le 6\\x_1,x_2\ge0$$

  1. Write the KKT optimality conditions and verify that these conditions hold true at the point $\overline x = (3/2,9/4)^t.$

  2. Interpret the KKT conditions at $\overline x$ graphically.

  3. Show that $\overline x$ is indeed the unique global optimal solution.

My solution

  1. The KKT conditions: consider the problem $$\min -\Big(x_1-\frac{9}{4}\Big)^2-\big(x_2-2\big)^2$$ $$s.t.\quad -x_2+x_1^2\le0\\ x_1+x_2-6\le 0\\x_1,x_2\ge0$$ $\overline x$ feasible, $I=\{i:u_ig_i(\overline x)=0\}$

And there exists scalars $u_i\ge0$ not all zero such that $$\nabla f(\overline x)+\sum_{i\in I}u_i\nabla g_i(\overline x)=0$$

Is this a correct answer for 1.?

I checked if the point $\overline x = (3/2,9/4)^t$ is KKT but it's not, (when solving the system, the scalars $u_i$ were all negative)

  1. I draw the level curves $\Big(x_1-\frac{9}{4}\Big)^2+\big(x_2-2\big)^2$ and I also draw the feasible region and I could see $\overline x = (3/2,9/4)^t$ is a minimum.

I'm not sure if what I did here it's considered correct solution of 2.

  1. We can not consider $\overline x = (3/2,9/4)^t$ as unique global optimal solution because it's not even optimal solution.

Could you please check if what I did here to solve the exercise it's correct?

Any comment or sugguestion is very welcome.

Thank you in advance for your help

$\endgroup$
  • $\begingroup$ Can you write out the gradients you computed for part (1) and show how you derived the negative $u_i$? $\endgroup$ – David M. Jun 23 '18 at 12:41
  • $\begingroup$ @DavidM. yes, the gradients evaluated in $\overline x$ are $\nabla f(\overline x)=(-3+9/2,-9/2+4)^t,\nabla g_1(\overline x)=(3,-1)^t,\nabla g_2(\overline x)=(1,1)^t$. Solving the system $\nabla f(\overline x)+u_1\nabla g_1(\overline x)+u_2\nabla g_2(\overline x)=0$ gives negative $u_i$ $\endgroup$ – user441848 Jun 23 '18 at 18:10
  • $\begingroup$ @DavidM. $u_1=-1/2$ and $u_2=0$ $\endgroup$ – user441848 Jun 23 '18 at 18:13
1
$\begingroup$

You seem to be forgetting the constraints $x_1,x_2\geqslant0$. Including these, the gradients of the four constraints are

$$ \begin{pmatrix}2x_1\\-1\end{pmatrix}, \begin{pmatrix}1\\1\end{pmatrix},\begin{pmatrix}-1\\0\end{pmatrix},\begin{pmatrix}0\\-1\end{pmatrix}. $$

The gradient of the objective function (using the minimization form you gave) is

$$ \begin{pmatrix}-2x_1+(9/2)\\-2x_2+4\end{pmatrix}. $$

For the point $(3/2\ 9/4)^\text{T}$, the stationarity conditions become

$$ \underbrace{\begin{pmatrix}3&1&-1&0\\-1&1&0&-1\end{pmatrix}}_{\displaystyle\equiv A}\begin{pmatrix}\mu_1\\\mu_2\\\mu_3\\\mu_4\end{pmatrix}=\underbrace{\begin{pmatrix}-3/2\\1/2\end{pmatrix}}_{\displaystyle \equiv b} $$

and dual feasibility says that $\mu\geqslant0$. However, only the first constraint is binding, and hence CS tells us that $\mu_2=\mu_3=\mu_4=0$. Hence our system reduces to

$$ \begin{pmatrix}3\\-1\end{pmatrix}\mu_1=\begin{pmatrix}-3/2\\1/2\end{pmatrix}, $$

which has the unique solution $\mu_1=-1/2$, which does not satisfy dual feasibility (you could use Farkas' lemma to prove this system has no non-negative solution--this would be perhaps more "optimization flavored". I came up with the dual certificate $y=(-1\ -1)$).

Is this a correct answer for 1.?

Don't forget primal and dual feasibility, and complementary slackness!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ To your last line in your answer, isn't this $\nabla f(\overline x)+\sum_{i\in I}u_i\nabla g_i(\overline x)=0$ dual feasibility condition? $\endgroup$ – user441848 Jun 25 '18 at 5:28
  • $\begingroup$ @user441848 That’s the stationarity condition. Dual feasibility for this problem is $u_i\ge0$. $\endgroup$ – David M. Jun 25 '18 at 11:35
  • $\begingroup$ But I did write them, when I wrote there exists scalars bigger than zero. $\endgroup$ – user441848 Jun 25 '18 at 18:28
  • $\begingroup$ @user441848 I see. Just making sure everything is there & clear $\endgroup$ – David M. Jun 25 '18 at 18:30
  • 1
    $\begingroup$ The idea is definitely correct, just a matter of precision $\endgroup$ – David M. Jul 1 '18 at 4:25
1
$\begingroup$

Analyzing the in the attached plot the points $\{A,B,C,D,E\}$ for the maximization problem,

enter image description here

$$ \left( \begin{array}{cccc} label & x & y & f(x,y)\\ A & 0 & 6 & \frac{337}{16} \\ B & 2 & 4 & \frac{65}{16} \\ C & \frac{3}{2} & \frac{9}{4} & \frac{5}{8} \\ D & 0 & 0 & \frac{145}{16} \\ E & 0 & 2 & \frac{81}{16} \\ \end{array} \right) $$

we can observe that the points $\{A,D,E\}$ are feasible solutions because $\nabla f$ (in black) at those points is a positive combination over the restriction's gradients (in red). The points $\{B, C\}$ are not feasible solutions for the maximization problem. Finally we choose point $A$ as the maximum. Those positive combinations are described as

$$ \nabla f = \sum_{k\in S}\lambda_k\nabla g_k $$

with $\lambda_k \ge 0$ not all null for $k\in S$ where $S$ is the set of active restrictions on the point.

| cite | improve this answer | |
$\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.