Fail to solve QP although P is positive semidefinite

72 views
Skip to first unread message

Stephane Caron

unread,
Aug 10, 2015, 12:00:34 AM8/10/15
to CVXOPT
Hi there,

I have what seems to be a bug in CVXOPT 1.1.7: in the script attached, the 10x10 matrix P is positive semidefinite (all its eigenvalues are > 0) but the solver fails with

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

What's more, if I only take P's symmetric part (the antisymmetric part does not affect the objective anyway), i.e.

P = .5 * (P + P.T)

Then the solver finds a solution. What's going on here?

All the best,

cvxbug.py

Rms Danaraj

unread,
Oct 19, 2015, 1:04:53 PM10/19/15
to CVXOPT

****
The reason is P is not symmetric!!!!!!!!!!!!!!

 P-P.T
array([[ 0.        ,  0.        ,  0.3924    ,  0.7848    ,  1.15153704,
         1.46694816,  1.70704875,  1.85121094,  1.88373214,  1.79518415],
       [ 0.        ,  0.        ,  0.        ,  0.3924    ,  0.7848    ,
         1.15153704,  1.46694816,  1.70704876,  1.85121095,  1.88373214],
       [-0.3924    ,  0.        ,  0.        ,  0.        ,  0.3924    ,
         0.7848    ,  1.15153704,  1.46694816,  1.70704876,  1.85121095],
       [-0.7848    , -0.3924    ,  0.        ,  0.        ,  0.        ,
         0.3924    ,  0.7848    ,  1.15153704,  1.46694816,  1.70704876],
       [-1.15153704, -0.7848    , -0.3924    ,  0.        ,  0.        ,
         0.        ,  0.3924    ,  0.7848    ,  1.15153704,  1.46694816],
       [-1.46694816, -1.15153704, -0.7848    , -0.3924    ,  0.        ,
         0.        ,  0.        ,  0.3924    ,  0.7848    ,  1.15153704],
       [-1.70704875, -1.46694816, -1.15153704, -0.7848    , -0.3924    ,
         0.        ,  0.        ,  0.        ,  0.3924    ,  0.7848    ],
       [-1.85121094, -1.70704876, -1.46694816, -1.15153704, -0.7848    ,
        -0.3924    ,  0.        ,  0.        ,  0.        ,  0.3924    ],
       [-1.88373214, -1.85121095, -1.70704876, -1.46694816, -1.15153704,
        -0.7848    , -0.3924    ,  0.        ,  0.        ,  0.        ],
       [-1.79518415, -1.88373214, -1.85121095, -1.70704876, -1.46694816,
        -1.15153704, -0.7848    , -0.3924    ,  0.        ,  0.        ]]

But P+P.T is symmetric!!!
(P+P.T)-(P+P.T).T
array([[ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.]])
Thank you

Rms Danaraj

unread,
Oct 19, 2015, 2:23:11 PM10/19/15
to CVXOPT
The definition o Quadratic program it self requires Q should be a symmetric positive definite matrix ,

https://en.wikipedia.org/wiki/Quadratic_programming

The quadratic programming problem with n variables and m constraints can be formulated as follows.[1] Given:

  • a real-valued, n-dimensional vector c,
  • an n × n-dimensional real symmetric matrix Q,
  • an m × n-dimensional real matrix A, and
  • an m-dimensional real vector b,

the objective of quadratic programming is to find an n-dimensional vector x, that

minimizes \tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}
subject to







 A \mathbf{x} \leq \mathbf{b}.

More information refer here

https://www.math.washington.edu/~burke/crs/408/notes/qp/qp1.pdf



Reply all
Reply to author
Forward
0 new messages