Converting from QP to SOCP

Question

I want to convert the following problem into SOCP form:

$minimize \quad$ $x^TAx+a^Tx$:

$subject$ $to \quad$ $Bx \leq b$

The approach I am taking is introducing new variables, $u$ and $v$, such that:

$u=x^TAx$ and $v=a^Tx$.

Then, our problem becomes:

$minimize \quad$ $u+v$:

$subject$ $to \quad$ $Bx \leq b$, $u \leq x^TAx$ and $v \leq a^Tx$.

Among these 3 constraints, the first and the third are linear, so we can let them be as they are. Only the second constraint needs to be converted into 2-norm form somehow, which I am not able to get how to do. Could anyone kindly tell me how to do that conversion? Would I need to introduce more new variables, or does it involve using some formula or trick that I can't seem to think of?

Answer 1

This only works if $A$ is positive definite. In this case, just drop the quadratic part and obtain $$\begin{array}{rcl} \min\limits_{x,y} && y + a^Tx\\ st && Bx\leq b\\ && x^TAx \leq y \end{array}$$ Then, we play a long circuitous game with this last constraint where $$\begin{array}{rl} &y\geq x^TAx\\ \Longrightarrow& 0\geq x^TAx - y\\ \Longrightarrow& 0\geq 4x^TAx - 4y\\ \Longrightarrow& 0\geq 4x^TAx + (1-y)^2-(1+y)^2\\ \Longrightarrow& (1+y)^2\geq 4x^TAx + (1-y)^2\\ \Longrightarrow& (1+y)^2\geq 4x^TAx + (1-y)^2, 1+y\geq 0\\ \end{array}$$ where the extra constraint, $1+y\geq 0$, can be added since $y\geq 0$ since $x^TAx\geq 0$ since $A\succ 0$ and $y\geq x^TAx$. Anyway, then we have $$\begin{array}{rl} \Longrightarrow& 1+y\geq \sqrt{4x^TAx + (1-y)^2}, 1+y\geq 0\\ \Longrightarrow& 1+y\geq \sqrt{4x^TU^TUx + (1-y)^2}, 1+y\geq 0 \end{array}$$ where we use the Choleski factorization $A=U^TU$ since $A\succ 0$. Then,

$$\begin{array}{rl} \Longrightarrow& 1+y\geq \left\|\begin{bmatrix}2Ux\\1-y\end{bmatrix}\right\|, 1+y\geq 0\\ \Longrightarrow& \begin{bmatrix}1+y\\2Ux\\1-y\end{bmatrix}\succeq_Q 0\\ \end{array}$$ Putting this all together, we have $$\begin{array}{rcl} \min\limits_{x,y} && y + a^Tx\\ st && Bx\leq b\\ && \begin{bmatrix}1+y\\2Ux\\1-y\end{bmatrix}\succeq_Q 0 \end{array}$$

Answer 2

I'll assume $A$ is positive semidefinite. Let $A = L L^T$ be the Cholesky factorization of $A$. Your optimization problem can be reformulated as

\begin{align} \operatorname{minimize}_{x,u,y} & \quad y + a^T x \\ \text{subject to} & \quad Bx \leq b \\ & \quad u^T u \leq y \\ & \quad u = L^T x. \end{align} We are nearly done, because we only need to express the constraint $u^T u \leq y$ as a second-order cone constraint, and there is a "well known" trick that allows us to do this. (It's not really well known at all, but it is taught in Vandenberghe's 236b class.)

The trick is explained in problem 4.26 (entitled "Hyperbolic constraints as SOC constraints") in Boyd and Vandenberghe. This problem points out that $$ u^T u \leq y z, \, y \geq 0, \, z \geq 0 \iff \left \| \begin{bmatrix} 2u \\ y - z \end{bmatrix} \right \|_2 \leq y + z, \, y \geq 0, \, z \geq 0. $$ It follows that our optimization problem can be reformulated as \begin{align} \operatorname{minimize}_{x,u,y,z} & \quad y + a^T x \\ \text{subject to} & \quad Bx \leq b \\ & \quad \left \| \begin{bmatrix} 2u \\ y - z \end{bmatrix} \right \|_2 \leq y + z\\ & \quad z = 1 \\ & \quad u = L^T x. \end{align} This is a second-order cone program.