# Quadratic constraints to second-order conic ones

In the previous post we discussed how we can project onto the epigraph of the squared norm. However, when in an optimisation problem we encounter constraints of the form

\begin{aligned} (x,t)\in \mathrm{epi}_{\|{}\cdot{}\|^2} \end{aligned}

That is, quadratic constraints (of the form $\|x\|^2 \leq t$), these can be converted to second-order conic constraints.

Note that $t$ in the constraints may or may not be a decision variable (it may as well be a constant).

The following identity does the trick:

\begin{aligned} t = \left(\frac{t+1}{2}\right)^2 - \left(\frac{t-1}{2}\right)^2. \end{aligned}

Then,

\begin{aligned} \mathrm{epi}_{\|{}\cdot{}\|^2} &= \{ (x,t) {}:{} \|x\|^2 \leq t \}\\ &= \left\{ (x,t) {}:{} \|x\|^2 \leq \left(\frac{t+1}{2}\right)^2 - \left(\frac{t-1}{2}\right)^2 \right\}\\ &= \left\{ (x,t) {}:{} \|x\|^2 + \left(\frac{t-1}{2}\right)^2\leq \left(\frac{t+1}{2}\right)^2 \right\}\\ &= \left\{ (x,t) {}:{} \left\| \begin{bmatrix}x\\ \frac{t-1}{2}\end{bmatrix} \right\|^2 \leq \left(\frac{t+1}{2}\right)^2 \right\}\\ &= \left\{ (x,t) {}:{} \left\| \begin{bmatrix}x\\ \frac{t-1}{2}\end{bmatrix} \right\| \leq \frac{t+1}{2} \right\}\\ &= \left\{ (x,t) {}:{} \begin{bmatrix}x\\ \frac{t-1}{2}\\ \frac{t+1}{2}\end{bmatrix} \in \mathcal{K}_{\mathrm{soc}} \right\}, \end{aligned}

where $\mathcal{K}_{\mathrm{soc}}$ is the second-order cone, also known as Lorentz cone or ice cream cone.

Define the linear operator

\begin{aligned} F: \begin{bmatrix}x\\ t\end{bmatrix} \mapsto \begin{bmatrix}x\\ \frac{t-1}{2}\\ \frac{t+1}{2}\end{bmatrix} \end{aligned}

Then, the quadratic constraints $\|x\|^2 \leq t$ becomes

\begin{aligned} F\begin{bmatrix}x\\ t\end{bmatrix} \in \mathcal{K}_{\mathrm{soc}}. \end{aligned}

Having $x'Px$ for some symmetric positive semidefinite matrix $P$ is no different than what we just did since $x'Px = \|P^{1/2}x\|^2$.

mathbabe

Exploring and venting about quantitative issues

Look at the corners!

The math blog of Dmitry Ostrovsky

The Unapologetic Mathematician

Mathematics for the interested outsider

Almost Sure

A random mathematical blog

Mathematix

Mathematix is the mathematician of the village of Asterix