Help solving Convex Optimization problem using KKT conditions?

Question

Link to problem although I've still written the problem here.

https://i.stack.imgur.com/6N8NN.jpg $$\ x \in \mathbb{R}^2$$ $$\ \text{minimize } f_0(x) =2x_1^2 + 4x_2^2 - 15x_1 - 30x_2 - 4x_1x_2$$ $$\ \text{subject to: } f_1(x) =x_1 \geq 0 $$ $$\ f_2(x) =x_2 \geq 0 $$ $$\ f_3(x) =x_1 + 2x_2 - 30 \leq 0 $$ $$\ Lagrangian:$$ $$\ \mathcal{L}(x,\lambda) = f_0(x) + \sum_{i=1}^3 \lambda_if_i(x)$$

So in this problem, I know that slater's condition holds, so strong duality is attained. But I need help to solve for the primal and dual variables after listing down all the KKT conditions. The first three are for Primal feasibility, next three are for dual feasibility, next three are complimentary slackness conditions and last two are components of the gradient of the Lagrangian which are equated to zero. The following are the KKT conditions : $$\ x_1 \geq 0$$ $$\ x_2 \geq 0$$ $$\ x_1 + 2x_2 - 30 \leq 0 $$ $$\ \lambda_1 \geq 0$$ $$\ \lambda_2 \geq 0$$ $$\ \lambda_3 \geq 0$$ $$\ \lambda_1x_1 = 0$$ $$\ \lambda_2x_2 = 0$$ $$\ \lambda_3(x_1 + 2x_2 - 30) = 0$$ $$\ 4x_1 - 15 - 4x_2 - \lambda_1 + \lambda_3 = 0 $$ $$\ 8x_2 - 30 - 4x_1 - \lambda_2 + \lambda_3 = 0 $$

Answer 1

We define the Lagrangian $$ \mathcal{L}(x_1, x_2, \lambda_1, \lambda_2) = f_0(x_1, x_2) - \lambda_1 f_1(x_1, x_2) - \lambda_2 f_2(x_1, x_2) - \lambda_3 f_3(x_1, x_2) $$ Suppose now that all constraints are active. Under Slater's, the 1st order necessary KKT conditions state that $$ \begin{align} \partial_{x_1} \mathcal{L} = 0 \\ \partial_{x_2} \mathcal{L} = 0 \\ \partial_{\lambda_1} \mathcal{L} = 0 \\ \partial_{\lambda_2} \mathcal{L} = 0 \\ \partial_{\lambda_3} \mathcal{L} = 0 \end{align} $$ Now let's see what the solutions to this would look like. These are stated as \begin{align} 4 x_1 - 15 - 4 x_2 - \lambda_1 + \lambda_3 = 0 \\ 8 x_2 -30 - 4 x_1 - \lambda_2 + 2\lambda_3 = 0 \\ x_1 = 0 \\ x_2 = 0 \\ 30 - x_1 - 2x_2 = 0 \end{align} but clearly the three last equations cannot be satisfied. Thus the problem is not minimized with three active constraint.

---

Suppose now only two constraints are satisfied. Considering first constraint 1 and 2, this yields \begin{align} 4 x_1 - 15 - 4 x_2 - \lambda_1 = 0 \\ 8 x_2 -30 - 4 x_1 - \lambda_2 = 0 \\ x_1 = 0 \\ x_2 = 0 \\ \end{align} which is a linear system and is satisfied iff $x_1 = 0, x_2 = 0, \lambda_1 = -15, \lambda_2 = -30$. But Lagrange multipliers should be positive.

We continue with constraint 1 and 3 \begin{align} 4 x_1 - 15 - 4 x_2 - \lambda_1 + \lambda_3 = 0 \\ 8 x_2 -30 - 4 x_1 + 2\lambda_3 = 0 \\ x_1 = 0 \\ 30 - x_1 - 2x_2 = 0 \end{align} which is satisfied for $x_1 = 0, x_2 = 15, \lambda_3 = 75, \dots$. $$ f(0, 15) = 450 > f(1, 1) = -43 $$ So this is not our minimizer

We continue with constraint 2 and 3 \begin{align} 4 x_1 - 15 - 4 x_2 + \lambda_3 = 0 \\ 8 x_2 -30 - 4 x_1 - \lambda_2 + 2\lambda_3 = 0 \\ x_2 = 0 \\ 30 - x_1 - 2x_2 = 0 \end{align} which is satisfied for $x_1 = 30, x_2 = 0, \lambda_3 = -105$. As lagrange multiplier should be positive this is not our solution either.

---

Suppose now only one constraint is active, \begin{align} 4 x_1 - 15 - 4 x_2 - \lambda_1 = 0 \\ 8 x_2 -30 - 4 x_1 = 0 \\ x_1 = 0 \\ \end{align} which yields $x_1 = 0, x_2 = 15/4, \lambda_1 = -75/4$. As before this is not our solution

OR

\begin{align} 4 x_1 - 15 - 4 x_2 = 0 \\ 8 x_2 -30 - 4 x_1 - \lambda_2 = 0 \\ x_2 = 0 \\ \end{align} which yields $x_1 = 15/4, x_2 = 0, \lambda_2 = -45$. As before this is not our solution

OR

\begin{align} 4 x_1 - 15 - 4 x_2 + \lambda_3 = 0 \\ 8 x_2 -30 - 4 x_1 + 2\lambda_3 = 0 \\ 30 - x_1 - 2x_2 = 0 \end{align} which yields $x_1 = 12, x_2 = 9, \lambda_3 = 3$. We inspect $$ f(12, 9) = -270 $$ So clearly a good candidate.

---

Finally we check that the problem is not solved for all constraints inactive, \begin{align} 4 x_1 - 15 - 4 x_2 = 0 \\ 8 x_2 -30 - 4 x_1 = 0 \\ \end{align} which yields $x_1 = 15, x_2 = 45/4$. However this solution is not satisfied by the constraints.

---

To summarize: We considered possible combinations of active constraints and solved the KKT conditions for the (1 + 3 + 3) = 7 different scenario. In all the cases the KKT conditions are linear systems. In the 7 different scenario there are only 2 candidates, $(0, 15)$ and $(12, 9)$. The value attained at $(12, 9)$ is the smallest and we thus conclude that this is the solution to the problem. Wolfram Alpha agrees with me.