# Formulate dual problem using Lagrange multipliers

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?

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