8.4 Quadratic Programming

The function qp() is an interface to coneqp() for quadratic programs. It also provides the option of using the quadratic programming solver from MOSEK.

qp(P, q[, G, h [, A, b[, solver[, initvals]]]])

Solves the pair of primal and dual convex quadratic programs

                T      T                                        T     T  T  †     T     T     T     T
minimize   (1∕2)x P x+ q x                  maximize  - (1∕2)T(q + GT z + A y) P (q +G z +A  y)- h z - b y
subject to Gx ≼ h                          subject to q+ G  z + A y ∈ range(P )
           Ax = b.                                   z ≽ 0.

The inequalities are componentwise vector inequalities.

The default CVXOPT solver is used when the solver argument is absent or None. The MOSEK solver (if installed) can be selected by setting solver = ’mosek’; see section 8.8. The meaning of the other arguments and the return value is the same as for coneqp() called with dims = {’l’: G.size[0], ’q’: [], ’s’: []}.

When the solver = ’mosek’ is used the initial values are ignored, and the ’status’ string in the solution dictionary can take four possible values: ’optimal’, ’unknown’. ’primal infeasible’, ’dual infeasible’.

’primal infeasible’
This means that a certificate of primal infeasibility has been found. The ’x’ and ’s’ entries are None, and the ’z’ and ’y’ entries are vectors that approximately satisfy
GT z + AT y = 0,  hTz +bTy = - 1,   z ≽ 0.

’dual infeasible’
This means that a certificate of dual infeasibility has been found. The ’z’ and ’y’ entries are None, and the ’x’ and ’s’ entries are vectors that approximately satisfy
            T
P x = 0,   q x = - 1,   Gx + s = 0,   Ax = 0,   s ≽ 0.

As an example we compute the trade-off curve on page 187 of the book Convex Optimization, by solving the quadratic program

minimize   - ¯pTx + μxTSx
subject to 1Tx = 1, x ≽ 0

for a sequence of positive values of mu. The code below computes the trade-off curve and produces two figures using the Matplotlib package.

PIC PIC

from math import sqrt  
from cvxopt.base import matrix  
from cvxopt.blas import dot  
from cvxopt.solvers import qp  
import pylab  
 
# Problem data.  
n = 4  
S = matrix([[ 4e-2,  6e-3, -4e-3,    0.0 ],  
            [ 6e-3,  1e-2,  0.0,     0.0 ],  
            [-4e-3,  0.0,   2.5e-3,  0.0 ],  
            [ 0.0,   0.0,   0.0,     0.0 ]])  
pbar = matrix([.12, .10, .07, .03])  
G = matrix(0.0, (n,n))  
G[::n+1] = -1.0  
h = matrix(0.0, (n,1))  
A = matrix(1.0, (1,n))  
b = matrix(1.0)  
 
# Compute trade-off.  
N = 100  
mus = [ 10**(5.0*t/N-1.0) for t in xrange(N) ]  
portfolios = [ qp(mu*S, -pbar, G, h, A, b)[’x’] for mu in mus ]  
returns = [ dot(pbar,x) for x in portfolios ]  
risks = [ sqrt(dot(x, S*x)) for x in portfolios ]  
 
# Plot trade-off curve and optimal allocations.  
pylab.figure(1, facecolor=’w’)  
pylab.plot(risks, returns)  
pylab.xlabel(’standard deviation’)  
pylab.ylabel(’expected return’)  
pylab.axis([0, 0.2, 0, 0.15])  
pylab.title(’Risk-return trade-off curve (fig 4.12)’)  
pylab.yticks([0.00, 0.05, 0.10, 0.15])  
 
pylab.figure(2, facecolor=’w’)  
c1 = [ x[0] for x in portfolios ]  
c2 = [ x[0] + x[1] for x in portfolios ]  
c3 = [ x[0] + x[1] + x[2] for x in portfolios ]  
c4 = [ x[0] + x[1] + x[2] + x[3] for x in portfolios ]  
pylab.fill(risks + [.20], c1 + [0.0], ’#F0F0F0’)  
pylab.fill(risks[-1::-1] + risks, c2[-1::-1] + c1, facecolor = ’#D0D0D0’)  
pylab.fill(risks[-1::-1] + risks, c3[-1::-1] + c2, facecolor = ’#F0F0F0’)  
pylab.fill(risks[-1::-1] + risks, c4[-1::-1] + c3, facecolor = ’#D0D0D0’)  
pylab.axis([0.0, 0.2, 0.0, 1.0])  
pylab.xlabel(’standard deviation’)  
pylab.ylabel(’allocation’)  
pylab.text(.15,.5,’x1’)  
pylab.text(.10,.7,’x2’)  
pylab.text(.05,.7,’x3’)  
pylab.text(.01,.7,’x4’)  
pylab.title(’Optimal allocations (fig 4.12)’)  
pylab.show()