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.