Quadratically constrained quadratic program

Quadratic Program with quadratic constraints

Second-order cone programming

\begin{align} &\min f^{T} x \\ &s.t\ \norm{A_{i} x + b_{i}}_{2} \leq c_{i}^{T} x + d_{i}, i = 1 \dots m\\ & Fx = g \end{align}

Most things reduce down to a SOCP.

• non-negative scaling
• sum: \(f_{1}+ f_{2}\) is convex if \(f_1, f_2\) is convex
• infinite sums: \(\sum_{i=1}^{\infty} f_{i}\) is convex
• integral: if \(f\qty(x,a)\) is convex in \(x\), \(\int_{a \in A} f\qty(x,a) \dd{a}\) is convex
• pre-composition with affine function: \(f\qty(Ax + b)\) is convex if \(f\) is convex
• pointwise maximum: \(f_{1}, …, f_{m}\) is convex, then \(f\qty(x) = \max \qty(f_{1} \qty(x)\dots f_n \qty(x))\) is convex
• supremum: if \(f\qty(x,y)\) is convex in \(x\) far each \(\text{sup}_{y \in Y} f\qty(x,y)\)
• partial minimization: \(f\qty(x) = \text{inf}_{y \in C} f\qty(x,y)\) (find the smallest value of \(f\) over \(y \in C\), or the point at which its approached)
• perspective of convex function is convex \(\text{persp}\qty(a,b) = b f\qty(\frac{a}{b})\)
• conjugate function of any function is convex

composition with scalar functions

\(g : \mathbb{R}^{n} \to \mathbb{R}\), \(h: \mathbb{R} \to \mathbb{R}\), and let \(f = h\qty(g\qty(x)) = h \odot g\)

constituents

• where \(x \in \mathbb{R}^{n}\) is a vector of variables
• \(f_{0}\) is the objective function, “soft” to be minimized
• \(f_{1} … f_{m}\) are the inequality constraints
• \(g_{1} … g_{p}\) are the equality constraints

requirements

Generally of structure:

\begin{equation} \min f_{0}\qty(x) \end{equation}

subject to:

\begin{align} f_{i} \qty(x) \leq 0, i = 1 \dots m \\ g_{i}\qty(x) = 0, i = 1 \dots p \end{align}

solving optimization problems

You can’t generally solve optimization problems… Some types

The perspective of a function: \(f: \mathbb{R}^{n} \to \mathbb{R}\) is the function: \(g: \mathbb{R}^{n} \times \mathbb{R} \to \mathbb{R}\):

\begin{equation} g\qty(x,t) = t f\qty(\frac{x}{t}), \text{dom } g = \qty {\qty(x,t) \mid x / t \in \text{dom } f, t > 0} \end{equation}

\(g\) is convex if \(f\) is convex.

• \(f\qty(x) = x^{T}x\) is convex, so \(g\qty(x,t) = x^{T}x / t\) is convex for \(t > 0\)
• \(f\qty(x) = - \log x\) is convex, so relative entropy \(g\qty(x,t) = t \log t - t \log x\) is convex on \(\mathbb{R}_{++}^{2}\)

requirements

A perspective function is:

\begin{equation} P\qty(x \dots t) = \frac{x}{t} \end{equation}

\(P: \mathbb{R}^{n+1} \to \mathbb{R}^{n}\).

\begin{equation} \text{persp}\qty(a,b) = b f\qty(\frac{a}{b}) \end{equation}