Large error when solving qp with box-type constraints

[Ben]

Hi,

Many thanks for developing such a useful piece of software.

Please consider the quadratic program with box constraints on each of the variables given in the message postscript. In this problem, each variable is constrained to lie within an interval of length one. In the optimal solution to this problem, the first variable should take the value 0, hence the error in the solution produced by qp, using the default solver, in the first variable is 0.00944193 ~= 10^{-2}, an order of magnitude larger than that produced by Mosek. (This error increases as the number of variables increases.) This error appears to persist, even when the algorithm stopping parameters, given in http://abel.ee.ucla.edu/cvxopt/userguide/solvers.html#algorithm-parameters , are shrunk.

How might this error be reduced?

Kind regards,
Ben
 

import scipy as sp
import cvxopt
from cvxopt import matrix, solvers
solvers.options['reltol'] = 1e-10
solvers.options['abstol'] = 1e-10
solvers.options['feastol'] = 1e-10
M = 10
I = sp.eye(M) * 1.
G = sp.vstack([I, -I])
h = sp.r_[sp.arange(1., M + 1), -sp.arange(M)]
solution = cvxopt.solvers.qp(P=matrix(I),
                             q=matrix(sp.zeros((M, 1))),
                             G=matrix(G),
                             h=matrix(h.reshape((-1,1))))
print(sp.array(solution['x']))

     pcost       dcost       gap    pres   dres
 0:  7.3889e+01  1.0611e+02  3e+02  6e-01  4e-15
 1:  1.4603e+02  1.2431e+02  2e+01  1e-16  7e-15
 2:  1.4331e+02  1.4151e+02  2e+00  1e-16  3e-15
 3:  1.4256e+02  1.4245e+02  1e-01  9e-17  4e-15
 4:  1.4250e+02  1.4250e+02  6e-03  7e-17  4e-15
 5:  1.4250e+02  1.4250e+02  7e-04  5e-17  3e-15
 6:  1.4250e+02  1.4250e+02  1e-04  1e-16  3e-15
Optimal solution found.
[[ 0.00944193]
 [ 1.00000045]
 [ 2.00000023]
 [ 3.00000015]
 [ 4.00000011]
 [ 5.00000009]
 [ 6.00000008]
 [ 7.00000006]
 [ 8.00000006]
 [ 9.00000005]]

[Martin]

Hi,

This is the output that I get when I run your code:

     pcost       dcost       gap    pres   dres

 0:  7.3889e+01  1.0611e+02  3e+02  6e-01  4e-15

 1:  1.4603e+02  1.2431e+02  2e+01  1e-16  7e-15

 2:  1.4331e+02  1.4151e+02  2e+00  1e-16  3e-15

 3:  1.4256e+02  1.4245e+02  1e-01  9e-17  4e-15

 4:  1.4250e+02  1.4250e+02  6e-03  7e-17  4e-15

 5:  1.4250e+02  1.4250e+02  7e-04  5e-17  3e-15

 6:  1.4250e+02  1.4250e+02  1e-04  1e-16  3e-15

 7:  1.4250e+02  1.4250e+02  1e-05  5e-17  3e-15

 8:  1.4250e+02  1.4250e+02  2e-06  4e-17  3e-15

 9:  1.4250e+02  1.4250e+02  3e-07  6e-17  3e-15

10:  1.4250e+02  1.4250e+02  4e-08  7e-17  3e-15

11:  1.4250e+02  1.4250e+02  5e-09  5e-17  3e-15

Optimal solution found.

[[  7.03310887e-05]

 [  1.00000000e+00]

 [  2.00000000e+00]

 [  3.00000000e+00]

 [  4.00000000e+00]

 [  5.00000000e+00]

 [  6.00000000e+00]

 [  7.00000000e+00]

 [  8.00000000e+00]

 [  9.00000000e+00]]

Now, the objective is given by 0.5*x.T*x, and dividing 0.5*x[0]**2 by the objective value yields approximately 2.9e-11. This means that the relative error in the objective is quite small, so the magnitude of the error in x[0] is to be expected with the given tolerance.