5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Wow! But the important part to know for anyone solving these kind of problems is, how did you know you need to convert it to the $(1+y)^2$ form? And why did you convert it into the Cholesky decomposition form thereafter? Did you "see" the solution in your mind, and sort of "backtracked" it? Or is there a set of steps that, upon mental execution, tells you what you need to do? $\endgroup$ – Kristada673 Sep 24 '16 at 12:40
  • 1
    $\begingroup$ Some years back, I wrote my Ph.D dissertation on automating these kind of transformations using software. Candidly, I couldn't remember how it worked and had to look it up and it still took me a bit to remember the trick. Anyway, for me at least, it was a lot of guessing and checking. I find it easier to work from the second-order cone form first and then work backwards. In general, convex quadratics use the Choleski factorization trick pretty often, so I go to that first. Also, I'm not the first to use this transformation, but you'll find matrix square roots more often than Choleski.. $\endgroup$ – wyer33 Sep 24 '16 at 14:58
  • $\begingroup$ In the spirit of beating a dead horse, I just realized that trick above uses one of the polarization identities. The most famous one is the parallelogram law $$ \|x+y\|^2+\|x-y\|^2=2\|x\|^2+2\|y\|^2 $$ However, another identity does the reverse where we have $$ \|x+y\|^2-\|x-y\|^2=4\langle x,y\rangle $$ In $\mathbb{R}$, this is just $$ (x+y)^2-(x-y)^2=4xy $$ and letting $x=1$, we get the form used above, which is $$ (1+y)^2-(1-y)^2=4y $$ Anyway, that may give a better insight as to how to derive the above result rather than my original approach of just guess and check. $\endgroup$ – wyer33 Oct 21 '16 at 3:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, what's funny is that we obtain the exact same reformulation if you just plug $u$ and $z$ back into your problem. $\endgroup$ – wyer33 Oct 4 '16 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.