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}

This is a Linear Program but quadratic now.

\begin{align} \min_{x}\ &\qty(\frac{1}{2}) x^{T} P x + q^{T} x + r \\ s.t.\ &Gx \preceq h \\ & Ax = b \end{align}

We want \(P \in S_{+}^{n}\), so PSD. So its convex quadratic.

Examples

Least Squares

Obviously least-squares is a basic Quadratic Program

\begin{equation} \norm{A x - b}^{2}_{2} \end{equation}

Linear Program with Random Cost

Consider a linear program with stochastic cost \(c\) with mean \(\bar{c}\) and covariance \(\Sigma\). Hence, a Linear Program objective \(c^{T}x\) is a random variable with mean \(\bar{c}^{T}x\) and variance \(x^{T} \Sigma x\).

Two approaches to handling uncertainty. Consider an LP:

\begin{align} &\min c^{T}x \\ &s.t. a_{i}^{x} \leq b_{i} \end{align}

what if our constraints are uncertain. Both of these reduce to an SOCP. See slides.

Deterministic Worst-Case

\begin{align} &\min c^{T}x \\ &s.t.\ a_{i}^{T} x \leq b_{i}, \forall a_{i} \in \epsilon_{i} \end{align}

Stochastic

\begin{align} &\min c^{T}x \\ &s.t.\ \text{prob}\qty(a_{i}^{T} x \leq b_{i}) \geq \eta, i = 1 \dots m \end{align}