Solving Quadratic Convex optimization problems in Python

Optimization is THE block that you need to solve many problems. From raw material management of the factory in the 19th century to decide which rider gets assigned to what customers in digital food tech app company, optimization is prevalent everywhere every time.

Quadratic optimization problems are of special types where the objective function is having quadratic form.

Quadratic convex problem: Standard form

Here, P, q, r, G, h, A and b are the matrices. h, b are 1D vectors. Typically we skip r(constant bias term) as that does not change the solution.

We will take an example and see how can we use ready solvers to solve QP problem. Suppose the problem is like:

x₁ > 0 , x₂ > 0 can be written as -x₁ < 0 , -x₂ < 0 to bring it to standard form. Here x will be [x₁ x₂]

Matrix equation of the objective function

When we compare the above equation with the standard form, we have p1 = 3, p4 = 4 and so on.. Final matrices will look like

(1/2)xᵀ P x + qᵀ x is a degree two expression in x, making it quadratic. Inequalities and equality constraints are all affine.

Note that there is a multiplier (1/2) in the definition of the standard form. CVXOPT library, however, does not expect that in its solver. Also, the variables expected by cvxopt need to be float so ensure writing 3 as 3.0.