Help with a simple convex problem

[Anuj]

I am trying to solve the following simple optimization probem:

min x.T * S * x

s.t. c - sum(log(x)) <=0

over R_+^n.

where S is a positive-semidefinite matrix. The idea is to minimize
variance subject to sufficiant diversification in a simiple mean
variance problem.

If I look at the FOCs.

(S*x)_i = lambda * 1/x_i. i.e.

x_i * (S*x)_i = constant across i

The solition I obtain does not satisfy this condition!

Code:

from cvxopt import solvers, matrix, spdiag, log
import aqr.gaa.api as api
def opterc(Sigma,c):
m, n = Sigma.size
def F(x=None, z=None):
if x is None: return 1, matrix(1.0, (n,1))
if min(x) <= 0.0: return None
f = matrix([x.T*Sigma*x, c-sum(log(x))])
Df = matrix([(Sigma*x).T, -(x**-1).T])
if z is None: return f, Df
H = z[0]*Sigma + z[1]*spdiag(z[1] * x**-2)
return f, Df, H
#solvers.options['show_progress'] = False
return solvers.cp(F)

Sigma = matrix([[1.0,0.0,0.0],
[0.0,16.0,0.0],
[0.0,0.0,9.0]])
sol = opterc(Sigma,1.0)
z=sol['x']
print spdiag(z)*Sigma*z

In [103]:
pcost dcost gap pres dres
0: 0.0000e+00 2.7000e+01 2e+00 1e+00 1e+00
1: 3.2490e+00 1.6965e+01 6e-01 5e-01 6e-01
2: 1.7725e+01 2.6325e+01 5e-01 2e-01 7e-02
3: 2.1758e+01 2.8745e+01 8e-02 2e-01 3e-01
4: 2.6774e+01 3.0533e+01 2e-02 1e-01 8e-01
5: 3.0056e+01 3.0703e+01 2e-04 2e-02 6e-01
6: 3.0684e+01 3.0697e+01 3e-06 5e-04 8e-02
7: 3.0685e+01 3.0675e+01 5e-08 4e-04 6e-02
8: 3.0667e+01 3.0660e+01 5e-10 3e-04 5e-02
9: 3.0654e+01 3.0649e+01 6e-12 2e-04 4e-02
10: 3.0646e+01 3.0642e+01 6e-14 1e-04 3e-02
11: 3.0640e+01 3.0637e+01 6e-16 9e-05 3e-02
12: 3.0636e+01 3.0634e+01 6e-18 5e-05 2e-02
Terminated (singular KKT matrix).
[ 1.04e+01]
[ 9.91e+00]
[ 1.03e+01]

I was expect the three entries above to be eqaul to each other. But
sol indicate that the solution is not optimal.

Out[104]:
{'dual infeasibility': 0.024652853796050086,
'dual objective': 30.634396229638021,
'dual slack': 0.99999999999999967,
'gap': 6.0856024054441434e-18,
'primal infeasibility': 5.3460771474092989e-05,
'primal objective': 30.635774727930908,
'primal slack': 3.9253723306845469e-19,
'relative gap': 1.9865259820451345e-19,
'sl': <0x1 matrix, tc='d'>,
'snl': <1x1 matrix, tc='d'>,
'status': 'unknown',
'x': <3x1 matrix, tc='d'>,
'y': <0x1 matrix, tc='d'>,
'zl': <0x1 matrix, tc='d'>,
'znl': <1x1 matrix, tc='d'>}

This seems like well studies problem (interior point methods using log
barriers etc).

Would appriciate any help.

Thanks,
A

[Anuj]

Sorry people, I had typed the hessian incorrectly.

H = z[0]*Sigma + z[1]*spdiag(z[1] * x**-2)

should be replaced with

H = z[0]*Sigma + z[1]*spdiag( x**-2)

Things are looking much better now.