2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Lagrange multipliers for equality constraints aren’t sign restricted. $\endgroup$ – Brian Borchers Oct 29 '19 at 20:21
  • $\begingroup$ I'm sorry but I'm not following -- $s_3$ relates to $h_3$, which is an inequality constraint (and hence sign restricted, no?). $\endgroup$ – Sebastian S Oct 29 '19 at 20:57
  • $\begingroup$ I attempted solving this myself and found $s_3=-1/4$ which cannot be correct. Perhaps there is an error in the problem? $\endgroup$ – Math1000 Oct 29 '19 at 22:13
  • $\begingroup$ My apologies- I thought you were putting the sign restriction on the equality constraint Lagrange multipliers. Another issue here is that the sign restriction changes depending on whether you're maximizing or minimizing the objective and whether the inequality constraints are $\leq$ or $\geq$ constraints and whether you've got $\nabla f(x)$ and the $\nabla g_{i}(x)$ terms on the same side of the equation or on opposite sides.. It appears that you have the sign restriction backwards for this problem. $\endgroup$ – Brian Borchers Oct 30 '19 at 0:42
  • $\begingroup$ @Math1000 - Thanks for the second pair of eyes. $s_3 = -1/4$ is indeed my solution too. $\endgroup$ – Sebastian S Oct 30 '19 at 7:54
1
$\begingroup$

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)
| 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.