Rank(A) < p or Rank([P; A; G]) < n error

[Murat Mut]

Hi all,

For the cvxopt QP solver, I tried a positive-semidefinite(PSD) quadratic term with just one constraint. The solver gives Rank(A) < p or Rank([P; A; G]) < n error. Here is my QP(also attached as .py file):

u = np.array([[1.],[1.],[1.],[1.],[1.]]) # 1x5 matrix

Q_np = np.dot(u, u.transpose())  

Q = cvxopt.matrix(np.tril(Q_np)) # Q is a 5x5 PSD matrix of rank 1

G = cvxopt.matrix(np.array([0.,0.,0.,0.,1.]).astype('d')).trans() 

h = cvxopt.matrix(np.ones(1).astype('d'))

# one constraint, x5<=1

c = cvxopt.matrix(np.ones(5))

sol = cvxopt.solvers.qp(Q,c, G, h)

When I go to to the source code (cvxopt 1.1.8) in misc.py, line 1445, 

if type(F['S']) is matrix: 

    lapack.potrf(F['S'])  

>>> np.array(F['S'])

gives a non-symmetric matrix. (I think lapack potrf takes only the lower triangular part, so being non-symmetric should be OK )

array([[ 1.,  0.,  0.,  0.,  0.],

       [ 1.,  1.,  0.,  0.,  0.],

       [ 1.,  1.,  1.,  0.,  0.],

       [ 1.,  1.,  1.,  1.,  0.],

       [ 1.,  1.,  1.,  1.,  2.]])

So I believe the solver recognizes that the problem(with that constraint) is not PD, and tries to correct this by adding G'G to it. However, F['S'] is still not PD , so lapack function potrf cannot be applied. 

So it seems cvxopt does not handle the PSD QP, is that the case? Is there another way to model the problem? Also I could make change in the source code for myself if you could give me a quick fox for that.

Thank you for your help in advance.

Murat 

[Martin]

If you take a look at the coneqp documentation, you'll see that it is required that Rank(A) < p or Rank([P; A; G]) < n. Your problem clearly does not satisfy this condition since P is rank 1 and G has a single row. You can either reformulate your problem as a second-order cone program or you could use the LDL KKT-solver with regularization:

sol = cvxopt.solvers.qp(Q, c, G, h, kktsolver='ldl', options={'kktreg':1e-9})

[Murat Mut]

Awesome, it worked although I had to hard-code kktsolver='ldl' in qp function, I am not sure it reads the options correctly. Thank you Martin for the prompt response! 

I have another question. In my case, almost all my problems (larger scale) will have Rank([P; A; G]) < n. It seems that ldl decomposition is significantly slower than lapack Cholesky decompisition. If I formulate the problem as a second-order cone program, would the solver work without using kktsolver='ldl' option? In fact, not only I have Rank([P; A; G]) < n, but also G is not full rank, i.e., G has linearly dependent columns. 

A second thing is if I make kktreg larger than 1e-9, the solver couldn't find an optimal solution. So I was wondering about the logic behind 1e-9.

Thanks a lot!

Murat

[Murat Mut]

Sorry, I meant to write below

 " but also G is not full rank, i.e., G has linearly dependent rows. "  

[Martin]

No, 1e-9 is arbitrary. The regularization option is experimental and undocumented. The best thing to do is to reformulate your problem so that the rank requirement is satisfied.

If you are an old version of CVXOPT, you can set the options via cvxopt.solvers.options instead of passing the options as a dictionary to the QP solver.