Quadratic Programming with Python and CVXOPT

1 Quadratic Programming with Python and CVXOPTThis guide assumes that you have already installed the NumPy and CVXOPT packagesfor your Python distribution. You can check if they are installed by importing them:import numpyimport cvxoptLet us first review the standard form of a QP (following CVXOPT notation):minx12x>P x+q>xsubject toGx hAx=bNote thatx>denotes the transpose ofx, andGx hmeans that the inequality is takenelement-wise over the vectorsGxandh. The above objective function is convex if and onlyifPis positive-semidefinite, which is the realm we are concerned CVXOPT QP framework expects a problem of the above form, defined by the pa-rameters{P, q, G, h, A, b};Pandqare required, the others are optional. Alternate QPformulations must be manipulated to conform to the above form; for example, if the in-equality constraint was expressed asGx h, then it can be rewritten Gx h.

2 Also, tospecify lower and upper bounds onx, an identity matrix can form part ofG, sincex uisequivalent toIx u. Note thatxitself is not provided to the solver, since it is an internalvariable being optimized over. In particular, this means that the solver has no explicit knowl-edge ofxitself; everything is implicity defined by the supplied parameters. It is essentialthat the same variable order is maintained for the relevant parameters ( ,qi, hi, bishouldcorrespond to variablexi).1 Non-convexity implies the existence of local optima, making it difficult to find global us consider a simple example:minx,y12x2+ 3x+ 4ysubject tox, y 0x+ 3y 152x+ 5y 1003x+ 4y 80 First, we rewrite the above in the given standard form:minx,y12[xy]>[1 00 0][xy]+[34]>[xy] 100 1 1 32534 [xy] 00 1510080 By inspection, the variable is defined by[xy], and the parametersP, q, G, hare how we collapsed all inequality constraints into a singleGmatrix of the standard there are no equality constraints, we do not need to provide the emptyA, b.

3 Notethat even thoughy2did not appear in the original objective, we had to include it with zerocoefficients inPbecause the solver parameters must be defined using the full set of if certain variables only appear in constraints, they will still need to be expressed withzero coefficients in the objective parameters, andvice us first define the above parameters in Python . CVXOPT supplies its own matrixobject; all arguments given to its solvers must be in this matrix type. There are two waysto do this. The first is to define the matrix directly with (potentially nested) lists:from CVXOPT import matrixP = matrix([[ , ],[ , ]])q = matrix([ , ])G = matrix([[ , , , , ],[ , , , , ]])h = matrix([ , , , , ])2 Observe how we defined the lists to contain real numbers (doubles) instead of integers,and thatGwas defined by its columns instead of its rows.

4 The CXVOPT solver only acceptsmatrices containing doubles, and if a list containing only integers was supplied to the matrixconstructor, it will create an integer matrix and eventual lead to a cryptic alternative way, perhaps more convenient if you are familiar with NumPy, is to firstcreate the matrices in NumPy, then call the CVXOPT matrix constructor on them:import numpyfrom CVXOPT import matrixP = matrix( ([1,0]), tc= d )q = matrix( ([3,4]), tc= d )G = matrix( ([[-1,0],[0,-1],[-1,-3],[2,5],[3,4]]), tc= d )h = matrix( ([0,0,-15,100,80]), tc= d )Here we created integer NumPy arrays and matrices because we used thetc= d option toexplicitly construct a matrix of doubles (this could work for the previous example as well).The hard work is mostly over now!

5 As you will often find, formulating the problem isusually the hard step. Invoking a solver is straightforward:from CVXOPT import solverssol = (P,q,G,h)That s it! If you hadA, bas well, you would call:sol = (P,q,G,h,A,b)You can even specify more options, such as the solver used and initial values to try. See theCVXOPT QP documentation in the references on the final properties about the solution can be extracted from thesolvariable (dictionary).In particular, the status , x , and primal objective are probably the most impor-tant. Ifstatusisoptimal, then the latter two give the optimal solution and its objectivevalue. You can access these fields as you would with a regular Python dictionary:sol[ x ] # [ , +00]sol[ primal objective ] # can verify2thatx = 0, y = 5, with an optimal value is crucial to verify the solution!

6 Don t just trust what the solver gives back to you!3 The code is reproduced below for your convenience:# Import the necessary packagesimport numpyfrom CVXOPT import matrixfrom CVXOPT import solvers# Define QP parameters (directly)P = matrix([[ , ],[ , ]])q = matrix([ , ])G = matrix([[ , , , , ],[ , , , , ]])h = matrix([ , , , , ])# Define QP parameters (with NumPy)P = matrix( ([1,0]), tc= d )q = matrix( ([3,4]), tc= d )G = matrix( ([[-1,0],[0,-1],[-1,-3],[2,5],[3,4]]), tc= d )h = matrix( ([0,0,-15,100,80]), tc= d )# Construct the QP, invoke solversol = (P,q,G,h)# Extract optimal value and solutionsol[ x ] # [ , +00]sol[ primal objective ] # : # Quadratic -programmingSection about QP in CVXOPT user s guide. The example here is not very illuminating; seethe second reference below.

7 The section on linear cone programs at the top of the pageexplains what the fields in the solution dictionary simple QP example in