Exercise from textbook: verify KKT conditions for a quadratic programme

Question

I am struggling with Exercise 7.3 in Cornuejols & Tutuncu's Optimization Methods in Finance (1st edition, 2006) [PDF]:

$$\begin{array}{ll} \text{minimize} & f(x) := x_1x_2 + x_1^2 + \frac{3}{2}x_2^2 + 2x_3^2 + 2x_1 + x_2 + 3x_3\\ \text{subject to} & g_1(x) := x_1 + x_2 + x_3 = 1\\ & g_2(x) := x_1 - x_2 = 0\\ & h_i(x) := x_i \geq 0 \text{ for } 1 \leq i \leq 3\end{array}$$

The exercise asks to show that $$ x^\star = (.5, .5, 0)$$ is an optimal solution by verification of the KKT-conditions.

Let $y_1, y_2$ and $s_1, s_2, s_3$ denote the multipliers corresponding to the $g_i$ and $h_i$. We have $s_1 = s_2 = 0$ because $s_ix_i = 0$. Hence the first (necessary) condition to verify is that there exist $s_3 \geq 0, y_1, y_2$ such that

$$\nabla f = y_1\nabla g_1 + y_2\nabla g_2 + s_3\nabla h_3,$$

where all gradients are evaluated at $x^\ast$.

This leads to the linear system (unless I made a mistake...):

$$ \left(\begin{matrix} 2x_1 + x_2 + 2\\ x_1 + 3x_2+1\\ 4x_3 + 3\\ \end{matrix}\right) = \left(\begin{matrix} 7/2\\ 3\\ 3\\ \end{matrix}\right) = \left( \begin{matrix} 1 & 1 & 0 \\ 1 & -1 & 0 \\ 1 & 0 & 1 \end{matrix}\right) \left( \begin{matrix} y_1\\ y_2\\ s_3 \end{matrix}\right), $$

but this has a solution $s_3 < 0$. Please help me see where I went wrong.

Answer 1

Since you cannot solve the KKT conditions for $x^*=(0.5, 0.5, 0)$, that solution is not optimal. There is an error in the assignment.

Since $Q$ is positive definite, there is just one optimal solution. With optimization software (Python code added below) I found the solution to be $\hat{x}\approx(0.47826, 0.47826, 0.04348)$. Note that $\hat{x}$ is a feasible solution because it satisfies the constraints. With this approximate solution you can easily prove that the solution $x^*$ given in the book is suboptimal, because its objective value is 2.375, whereas $\hat{x}$ has objective value 2.3695..., which is better.

import numpy
import cvxopt
Q = 2*matrix([ [1, .5, 0.0], [.5, 1.5, 0.0], [0.0, 0.0, 2.0] ])
p = matrix([2.0, 1.0, 3.0])
G = matrix([[-1.0,0.0,0.0],[0.0,-1.0,0.0],[0.0,0.0,-1.0]])
h = matrix([0.0,0.0,0.0])
A = matrix([[1.0, 1.0], [1.0, -1.0], [1.0, 0.0]])
b = matrix([1.0, 0.0])
sol=solvers.qp(Q, p, G, h, A, b)