In a previous post of mine, I talked about CVXOPT Programming. In this one, we’ll introduce cone programming. So first things first. Cone programming is a term (short for second-order cone program (SOCP)) is a convex optimization problem of the following form
where matrices fall in and vectors . On the other hand, vectors and . Also . Finally, and .
SOCPs are easily solved on CVXOPT using the socp solver found in the solvers module of CVXOPT. Please refer to the video for a step-by-step tutorial.
On the other hand, Quadratically Constrained Quadratic Programs (a.k.a QCQPs) are a bit tricky. QCQPs are optimization problems in which both the objective function and the constraints are quadratic functions, i.e.
where all matrices are given matrices. The QCQP problem is convex if matrices are positive semi-definite. Note that a QCQP boils down to a QP (Quadratic Program) when matrices are zero matrices. If in addition to the aforementioned statements, we also have , then the problem is an LP (Linear Program).
That’s enough background to get you going with QCQPs. Turns out that CVXOPT does not have a “QCQP” solver. On the bright side, we can cast a QCQP as an SOCP enabling us to solve QCQPs via the SOCP solver of CVXOPT. How do we do that ? Well minimizing the cost of the QCQP, i.e. minimizing is the same as minimizing an upper bound of as
We will now make use of an important theorem of positive semi-definite matrices, that is
Theorem 1: Let be a positive semidefinite matrix in . Then there is exactly one positive semidefinite matrix such that .
Actually, the above theorem is very intuitive. It’s a generalization of something you learned back in high school. It’s a matrix way of saying that every non-negative number admits a square root . So making use of the matrix square root decomposition, we will write down the square root decompositions of all matrices as
We shall also decompose ‘s as
So we get
Now let us include the term in the first constraints as
Similarly, we include the term in the last constraint as
Why did we do that ? Well, notice that
This means that
The problem in equation (11) is really close to that of (1). The only thing that is a bit “annoying” is the . To bypass this problem, we bound by a user-defined parameter as
The above problem is an SOCP as
So, in short, by choosing the above variables, we can go from a QCQP to an SOCP and hence solve the former on CVXOPT. The lecture uses Jupyter notebook on my favorite Google Chrome browser.