Transforming a QP Problem to an SOCP Problem

A Quadratic Programming problem (QP) in the form of

\begin{aligned} & \underset{x}{\text{minimize}} & & \frac{1}{2} x^T H x + p^T x \\ & \text{subject to} \\ & & & A_{eq} x = b_{eq} \\ & & & A x \geq b \end{aligned}

where H \in \Re^{n \times n}, A \in \Re^{m \times n}, p, x \in \Re^n, b \in \Re^m , can be transformed to a Second-Order Cone Programming (SOCP) problem in the form of

\begin{aligned} & \underset{x}{\text{minimize}} & & f^T x \\ & \text{subject to} \\ & & & \left \| A_i x + b_i \right \|_2 \leq c_i^T x + d_i, \; i = 1, \ldots, m \end{aligned}

Consider y = \left \| F x - c \right \|, and

\begin{aligned} y^2 & = \left \| F x - c \right \|^2 \\ & = (F x - c)^T (F x - c) \\ & = x^T F^T F x - 2 c^T F x + c^T c \end{aligned}

As c^T c is non-negative, minimizing x^T F^T F x - 2 c^T F x is equivalent to minimizing y^2, and hence is equivalent to minimizing y.

If we have H = 2 F^T F and p = -2 F^T c, then the objective function in QP \frac{1}{2} x^T H x + p^T x can be written as x^T F^T F x - 2 c^T F x . We can thus minimize y.

Thus, the QP problem can now be written as

\begin{aligned} & \underset{y}{\text{minimize}} & & y \\ & \text{subject to} \\ & & & \left \| F x - c \right \| \leq y \\ & & & A_{eq} x = b_{eq} \\ & & & A x \geq b \end{aligned}

As H, by definition of QP, is symmetric, a symmetric F can be found such that \frac{H}{2} = F^T F = F^2. If the QP is assumed to be a convex QP, H is positive semidefinite, applying Cholesky factorization gives \frac{H}{2} = U^T U (or L L^T). In this case, F = U (or L^T).

Next, as \left \| \cdot \right \|_2 is always non-negative, the equality constraint A_{eq} x = b_{eq} can be written as

\left \| A_{eq} x - b_{eq} \right \| \leq 0

Finally, each row in the inequality constraint A x \geq b can be written as

a_i x - b_i \geq 0, \; i = 1, \ldots, m

where a_i is the i-th row of A, and b_i is the i-th element of b.

Therefore, a QP problem can be transformed to an equivalent SOCP problem in the following way. We need to introduce a few variables first.

  • y = x_{n+1}
  • c = -\frac{1}{2} F^{-T} p

\begin{aligned} & \underset{x}{\text{minimize}} & & f^T x \\ & \text{subject to} \\ & & & \left \| A_1 x + b_1 \right \|_2 \leq c_1^T x + d_1 \\ & & & \left \| A_2 x + b_2 \right \|_2 \leq c_2^T x + d_2 \\ & & & \left \| A_3 x + b_3 \right \|_2 \leq c_3^T x + d_3 \\ & & & \vdots \\ & & & \left \| A_{m+2} x + b_{m+2} \right \|_2 \leq c_{m+2}^T x + d_{m+2} \\ & \text{where} \\ & & f & = (0, \ldots, 0, 1)^T \\ & & x & = (x_1, \ldots, x_n, x_{n+1})^T \\ & & A_1 & = \left [ F, 0 \right ], b_1 = \frac{1}{2} F^{-T} p, c_1 = (0, \ldots, 0, 1)^T, d_1 = 0, \left (\frac{H}{2} \right ) = F^T F \\ & & A_2 & = \left [ A_{eq}, 0 \right ], b_2 = -b_{eq}, c_2 = 0, d_2 = 0 \\ & & A_{i+2} & = 0, b_{i+2} = 0, c_{i+2} = \text{the i-th row of }A, d_{i+2} = -(\text{the i-th element of }b), \; i = 1, \ldots, m \\ & & & f, x, c_1, \ldots, c_{m+2} \in \Re^{n+1} \end{aligned}

The sub-vector with the first n elements in the solution of the transformed SOCP problem is the solution of the original QP problem.

SuanShu has implementations to solve both SOCP and QP problems.

Using SuanShu on Amazon EC2

Cloud computing is very popular nowadays. Delegating your CPU-intensive computation (or simulation) to the cloud seems to be a smart choice. Many of our users asked if SuanShu can be run on Amazon’s Elastic Compute Cloud (EC2), because SuanShu license requires a MAC address and they have no control on which machine being used when they launch an EC2 instance. Here comes a good news! Amazon Web Service (AWS) now supports Elastic Network Interface (ENI), by which you can bind your EC2 instance to a specified network interface. Therefore, you can license your SuanShu against the MAC address of the ENI, and launch an instance with the same ENI and MAC address. For details, please visit the blog here. User guide for ENI can also be found here.