CVXOPT failing for simple quadratic programming problem - any help appreciated

[gar...@mustardsystems.com]

Hi there,

I'm using CVXOPT in Python to try to solve a fairly simple quadratic programming problem. I'm finding that it works perfectly for some values of my parameters, but fails for others.

Shown below (and attached) is a very simple example, cvxopt.solvers.qp fails for the 2nd of these three examples, reaching its max iterations and failing to find an optimal solution. It works perfectly on the 1st and 3rd example. All three examples are very similar in nature, as you can see by eyeballing the input matrices.

I'd love to understand why CVXOPT is failing to solve the 2nd problem accurately. Any help would be greatly appreciated.

Thanks,

Gareth

import numpy as np

from cvxopt.solvers import qp

from cvxopt import matrix

print '-'*70

print 'Case 1:'

P = np.array([[ 0.0084,  0.003 ],

              [ 0.003,   0.0017]])

q = np.array([[-0.36],

              [-0.02]])

G = np.array([[ 1.,  0.],

              [ 0.,  1.]])

h = np.array([[ 500.],

              [ 500.]])

results = qp(

    matrix(P),

    matrix(q),

    matrix(G),

    matrix(h),

)

print results # Works fine, {'status': 'optimal'}

print results['x']

print 'Works fine'

print '-'*70

print 'Case 2:'

P = np.array([[ 0.0042 ,  0.0015 ],

              [ 0.0015 ,  0.00085]])

q = np.array([[-0.48],

              [-0.06]])

G = np.array([[ 1.,  0.],

              [ 0.,  1.]])

h = np.array([[ 500.],

              [ 500.]])

results = qp(

    matrix(P),

    matrix(q),

    matrix(G),

    matrix(h),

)

print results # Fails, reaches max_iter, {'status': 'unknown'}

print '***Fails***'

print '-'*70

print 'Case 3:'

P = np.array([[ 0.0021  ,  0.00075 ],

              [ 0.00075 ,  0.000425]])

q = np.array([[-0.54],

              [-0.08]])

G = np.array([[ 1.,  0.],

              [ 0.,  1.]])

h = np.array([[ 500.],

              [ 500.]])

results = qp(

    matrix(P),

    matrix(q),

    matrix(G),

    matrix(h),

)

print results # Works fine, {'status': 'optimal'}

print results['x']

print 'Works fine'

[Martin]

The issue is that your problem is poorly scaled. Try scaling G and h so that the elements in h are equal to 1.0, i.e.,

G = np.array([[ 0.002,  0.],

              [ 0.,  0.002]])

h = np.array([[ 1.],

              [ 1.]])

This results in the following output:

Case 2:

     pcost       dcost       gap    pres   dres

 0: -4.7167e+01 -4.9993e+01  3e+00  6e-17  8e-03

 1: -4.7182e+01 -4.7211e+01  3e-02  2e-16  8e-05

 2: -4.7182e+01 -4.7182e+01  3e-04  1e-16  8e-07

 3: -4.7182e+01 -4.7182e+01  3e-06  1e-16  8e-09

Optimal solution found.

[gar...@mustardsystems.com]

Hi Martin, that's fantastic, thanks so much, I'll give that a try!

Best

Gareth