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.

Trackbacks/Pingbacks

  1. Quantocracy's Daily Wrap for 11/19/2017 | Quantocracy - […] Transforming a QP Problem to an SOCP Problem [Numerical Method] […]

Submit a Comment

Your email address will not be published. Required fields are marked *