Lowner-John Ellipsoid

minimum volume surrounding ellipsoid

Consider a set of ellipsoid \(C\). Minimum volume ellipsoid \(\epsilon\) with \(C \subset \epsilon\). We can parameterize \(\epsilon\) as \(\epsilon = \qty {v \mid \norm{Av + b}_{2} \leq 1}\); where we assume \(A \in \mathcal{S}_{++}^{n}\).

The volume is proportional to \(\text{det} A^{-1}\). Thus to find minimal-volume ellipsoid, solve:

\begin{align} \min_{A,b}\quad & \log \text{det} A^{-1} \\ \textrm{s.t.} \quad & \text{sup}_{v \in C} \norm{A v + b}_{2} \leq 1 \end{align}

OR, for finite sets:

\begin{align} \min_{A,b}\quad & \log \text{det} A^{-1} \\ \textrm{s.t.} \quad & \norm{A x_{i} + b }_{2} \leq 1, i = 1 \dots m \end{align}

Inside

maximum volume inscribing ellipsoid

Consider a set of ellipsoid \(C\). Minimum volume ellipsoid \(\epsilon\) with \(C \subset \epsilon\). We can parameterize \(\epsilon\) as \(\epsilon = \qty {Bu + d \mid \norm{u}_{2} \leq 1}\); where we assume \(B \in \mathcal{S}_{++}^{n}\).

\begin{align} \max_{B,d}\quad & \log \text{det} B \\ \textrm{s.t.} \quad & \text{sup}_{\norm{u}_{2}} \leq 1, I_{C}\qty(Bu+d) \leq 0 \end{align}

where \(I_{C} = 0\) when \(c \in C\), \(\infty\) otherwise.