The problem asks for me to minimize $f(x) = -8x_1 + x_2$ subject to $x_2 \leq 8$ and $(x_1-4)^2 - x_2 \leq 8$. I found $L(x_1, x_2, \lambda) = -8x_1 + x_2 + \lambda_1(x_2-9) + \lambda_2((x_1-4)^2 - x_2 \leq 8)$

I had some trouble with this, but think I am on the right track. By taking the partial derivatives I obtained: $-8 + 2\lambda_1(x_1 -4) =0$ and $1+\lambda_1 - \lambda_2 = 0$ as well as $\lambda_1(x_2 - 8) = 0$ and $\lambda_2((x_1-4)^2 - x_2 - 8) = 0$ from the slackness condition.

From here I got we need either $\lambda_1 =0$ or $x_2 = 8$ and $\lambda_2 = 0 or (x_1-4)^2 - x_2 = 8$. I'm not sure what to do from here. Exploring all options is confusing because if $\lambda_1 = 0$ then everything else is up in the air. I believe that we will need both constraints to be active, i.e. $x_2 = 8$ and $(x_1-4)^2 - x_2 = 8$, which will give (8,8) as the optimal solution (because f convex and KTT).

From here, I have found that the tangent cone to the feasible set at (8,8) is $\big\{ \alpha(-1,0)+\beta(-1,-8) \mid \alpha\geq 0,\beta\geq 0\big\}.$

Now I am having trouble solving the dual problem. I know the goal is to find $\max_\lambda min_{x_1,x_2} L(x_1,x_2, \lambda)$, but I am stuck here.

The problem asks me to formulate the dual problem, find if the duality relation holds, and find the optimal value of the dual problem?

  • $\begingroup$ The problem $min_{x} L(x,\lambda)$ seems easy since $L$ is just quadratic, right? $\endgroup$ – LinAlg Nov 6 '18 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.