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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

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

%d bloggers like this: