NOTES | HOME
$$ \newcommand{\RR}{\mathbb{R}} \newcommand{\GG}{\mathbb{G}} \newcommand{\PP}{\mathbb{P}} \newcommand{\PS}{\mathcal{P}} \newcommand{\SS}{\mathbb{S}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\CC}{\mathbb{C}} \newcommand{\HH}{\mathbb{H}} \newcommand{\ones}{\mathbb{1\hspace{-0.4em}1}} \newcommand{\alg}[1]{\mathfrak{#1}} \newcommand{\mat}[1]{ \begin{pmatrix} #1 \end{pmatrix} } \renewcommand{\bar}{\overline} \renewcommand{\hat}{\widehat} \renewcommand{\tilde}{\widetilde} \newcommand{\inv}[1]{ {#1}^{-1} } \newcommand{\eqdef}{\overset{\text{def}}=} \newcommand{\block}[1]{\left(#1\right)} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\trace}[1]{\mathrm{tr}\block{#1}} \newcommand{\norm}[1]{ \left\| #1 \right\| } \newcommand{\argmin}[1]{ \underset{#1}{\mathrm{argmin}} } \newcommand{\argmax}[1]{ \underset{#1}{\mathrm{argmax}} } \newcommand{\st}{\ \mathrm{s.t.}\ } \newcommand{\sign}[1]{\mathrm{sign}\block{#1}} \newcommand{\half}{\frac{1}{2}} \newcommand{\inner}[1]{\langle #1 \rangle} \newcommand{\dd}{\mathrm{d}} \newcommand{\ddd}[2]{\frac{\partial #1}{\partial #2} } \newcommand{\db}{\dd^b} \newcommand{\ds}{\dd^s} \newcommand{\dL}{\dd_L} \newcommand{\dR}{\dd_R} \newcommand{\Ad}{\mathrm{Ad}} \newcommand{\ad}{\mathrm{ad}} \newcommand{\LL}{\mathcal{L}} \newcommand{\Krylov}{\mathcal{K}} \newcommand{\Span}[1]{\mathrm{Span}\block{#1}} \newcommand{\diag}{\mathrm{diag}} \newcommand{\tr}{\mathrm{tr}} \newcommand{\sinc}{\mathrm{sinc}} \newcommand{\cat}[1]{\mathcal{#1}} \newcommand{\Ob}[1]{\mathrm{Ob}\block{\cat{#1}}} \newcommand{\Hom}[1]{\mathrm{Hom}\block{\cat{#1}}} \newcommand{\op}[1]{\cat{#1}^{op}} \newcommand{\hom}[2]{\cat{#1}\block{#2}} \newcommand{\id}{\mathrm{id}} \newcommand{\Set}{\mathbb{Set}} \newcommand{\Cat}{\mathbb{Cat}} \newcommand{\Hask}{\mathbb{Hask}} \newcommand{\lim}{\mathrm{lim}\ } \newcommand{\funcat}[1]{\left[\cat{#1}\right]} \newcommand{\natsq}[6]{ \begin{matrix} & #2\block{#4} & \overset{#2\block{#6}}\longrightarrow & #2\block{#5} & \\ {#1}_{#4} \hspace{-1.5em} &\downarrow & & \downarrow & \hspace{-1.5em} {#1}_{#5}\\ & #3\block{#4} & \underset{#3\block{#6}}\longrightarrow & #3\block{#5} & \\ \end{matrix} } \newcommand{\comtri}[6]{ \begin{matrix} #1 & \overset{#4}\longrightarrow & #2 & \\ #6 \hspace{-1em} & \searrow & \downarrow & \hspace{-1em} #5 \\ & & #3 & \end{matrix} } \newcommand{\natism}[6]{ \begin{matrix} & #2\block{#4} & \overset{#2\block{#6}}\longrightarrow & #2\block{#5} & \\ {#1}_{#4} \hspace{-1.5em} &\downarrow \uparrow & & \downarrow \uparrow & \hspace{-1.5em} {#1}_{#5}\\ & #3\block{#4} & \underset{#3\block{#6}}\longrightarrow & #3\block{#5} & \\ \end{matrix} } \newcommand{\cone}[1]{\mathcal{#1}} $$

Conic Optimization

  1. Cones
  2. Examples
  3. Dual Cone
  4. Polar Cone
  5. Moreau Decomposition
  6. Convex Conic Programs
  7. Projection on the Second Order Cone

Cones

\[x\in K \Rightarrow \lambda x \in K, \quad \forall \lambda \geq 0\]

Examples

Positive orthant: \(x \geq 0\)

Second-order cone: \((x, t) : \norm{x} \leq t\)

Positive definite matrices: \(M \succeq 0\)

Dual Cone

\[K^* = \left\{ y \in E, \quad x^Ty \geq 0 \quad \forall x \in K\right\}\]

Polar Cone

\(K^- = -K^*\)

Moreau Decomposition

\[z = x + y, \quad x \in K \ \bot \ y \in K^- \iff x = \pi_K(z),\ y = \pi_{K^-}(z)\]

Convex Conic Programs

\[\argmin{x \in K} \quad \half x^T M x + q^T x \quad \iff \quad x \in K \ \bot \ Mx + q \in K^*\]

As a fixed point:

\[x = \pi_K\block{x - (Mx + q)}\]

Projection on the Second Order Cone

Given the second-order cone \(K = \left\{x: \norm{x_T} \leq x_N \right\}\) with normal/tangent subspaces \(N, T\) we consider the orthogonal projection problem:

\[x = \pi_K(p)\]

More precisely, we look for a solution to:

\[\argmin{\norm{x_N}^2 \geq \norm{x_T}^2, \ x_N \geq 0} \norm{x - p}^2\]

which is a convex program. The gradient for constraint \(\norm{x_N}^2 - \norm{x_T}^2 \geq 0\) is \(x_N - x_T\), and KKT conditions are:

\[\begin{align} x_N &= p_N + \lambda x_N + \mu \\ x_T &= p_T - \lambda x_N \\ 0 \leq \lambda \ &\bot\ \norm{x_N}^2 - \norm{x_T}^2 \geq 0 \\ 0 \leq \mu \ &\bot \ x_N \geq 0 \end{align}\]

Now, since complementarity problems are difficult to solve analytically, we will look for critical points for the following non-convex problem instead:

\[\argmin{\norm{x_N}^2 = \norm{x_T}^2} \norm{x - p}^2\]

whose KKT conditions are:

\[\begin{align} (1 - \lambda) x_N &= p_N \\ (1 + \lambda) x_T &= p_T \\ \norm{x_N}^2 - \norm{x_T}^2 &= 0 \\ \end{align}\]

Let us assume for now that \(\norm{\lambda} \neq 1\) and that our constraint is active, we obtain:

\[\begin{align} x_N &= \frac{p_N}{1 - \lambda} \\ x_T &= \frac{p_T}{1 + \lambda} \\ \norm{x_N}^2 - \norm{x_T}^2 &= 0 \\ \end{align}\]

Subtitution gives:

\[(1 - \lambda)^2 \norm{p_T}^2 = (1 + \lambda)^2 \norm{p_N}^2\]

And finally:

\[\block{1 + \lambda^2}\block{ \norm{p_N}^2 - \norm{p_T}^2} + 2 \lambda \block{\norm{p_N}^2 + \norm{p_T}^2} = 0\]

which under our assumptions has always a solution given by:

\[\lambda = \frac{\norm{p}^2 \pm 2 \norm{p_T}\norm{p_N}}{\norm{p_T}^2 - \norm{p_N}^2}\]

Now if we are to use this formula for solving the original orthogonal projection problem, we need to consider the sign of \(x_N\) corresponding to \(\lambda\) in order to rule out critical points. More precisely, we have: \(\sign{x_N} = \sign{p_N}\sign{1 - \lambda}\)

where:

\[1-\lambda = \frac{ 2 \norm{p_N}^2 \pm 2 \norm{p_T}\norm{p_N} } {\norm{p_T}^2 - \norm{p_N}^2}\]

Depending on the sign of \(\norm{p_T}^2 - \norm{p_N}^2\) and that of \(p_N\), each \(\lambda\) pair will result in either two positive, two negative, or exactly one positive and one negative values for \(x_N\). One can verify that:

In other cases, the solution is obtained from the root resulting in a positive \(x_N\). The final projection procedure is the following:

It is easy to check that the two degenerate cases are handled correctly by the above procedure: