I have tried to convert the following constraint into SOCP form but can't figure it out. My issue is that whenever I create the norm, the other side has to be square rooted which invalidates the SOCP form.

The directional parameters $${\boldsymbol w}\in\Bbb R^d$$ satisfies the following shaping constraint: $$\boldsymbol w^\top\boldsymbol\Sigma\boldsymbol w+\boldsymbol c^\top\boldsymbol w\le1,$$ where $$\boldsymbol\Sigma\in\Bbb R^{d\times d}$$ is a given symmetric, positive definite matrix and $$\boldsymbol c\in\Bbb R^d$$ is a given vector.

• Btw how do you know Sigma is PSD? Maybe because you know a matrix H such that Sigma=HH'? May 11, 2022 at 7:00

For all things convex, Mosek's modeling cookbook and conic modeling cheatsheet have you covered.

Since $$\boldsymbol\Sigma$$ is PSD, there exists $$\boldsymbol Q$$ s.t. $$\boldsymbol Q^\top\boldsymbol Q=\boldsymbol \Sigma$$ (by Cholesky, or eigendecomposition).

Then $$\boldsymbol w^\top\boldsymbol \Sigma\boldsymbol w =\boldsymbol w^\top\boldsymbol Q^\top\boldsymbol Q\boldsymbol w = \|\boldsymbol Q\boldsymbol w\|_2^2.$$

Then introduce new variable $$y$$ as epigraph of $$\|\boldsymbol Q\boldsymbol w\|$$ as follows:

\begin{align}y+\boldsymbol c^\top\boldsymbol w&=1\tag{linear constraint}\\\|\boldsymbol Q\boldsymbol w\|_2^2&\le y\tag{rotated quadratic cone constraint}\end{align}

As @mtanneau posted, these modeling tricks(?) are well-explained in the MOSEK tutorial.

If you use MOSEK, you can just directly use rotated quadratic cone to model second constraint. If you want to convert into second order conic constraints,

\begin{align}&\|\boldsymbol{Qw}\|_{2}^{2} \leq y \\\iff&(\boldsymbol{Qw})^\intercal (\boldsymbol{Qw}) \leq y \\ \iff& (\boldsymbol{Qw})^\intercal (\boldsymbol{Qw})+\frac{(y-1)^2}{4} \leq \frac{(y+1)^2}{4}\\ \iff& \left\|\begin{pmatrix}\boldsymbol{Qw}\\ \frac{y-1}{2} \end{pmatrix}\right\|_{2} \leq \frac{y+1}{2}\end{align}

Hope this is what you're looking for.
*Converting quadratic constraint into soc constraint is well-known tricks, you can find in https://www2.isye.gatech.edu/~nemirovs/LMCOLN2021WithSol.pdf

• Shouldn't the 2-norm of $Qw$ be squared?
– prubin
May 10, 2022 at 15:24
• @prubin Sure. I had a mistake. Thanks.
– Seok
May 11, 2022 at 3:56
• I suggest you change $y+c'w\le1$ to $y+c'w = 1$. That is correct and in theory more efficient. May 11, 2022 at 6:56
• Oh, I see. I didnt realize making it linear equality is better until now. Thank you :) BTW, can you plz explain or give some references about that efficiency? Maybe the linear equality can project onto the smaller search space..?
– Seok
May 11, 2022 at 7:42
• It follows from the complexity analysis of interior-point methods i.e. the barrier parameter will be smaller with equality. May 11, 2022 at 10:06