You got the lights on in the afternoon

And the nights are drawn out long

And you’re kissin’ to cut through the gloom

With a cough drop coloured tongue

And you were sittin’ in the corner with the coats all piled high

And I thought you might be mine

In a small world, on an exceptionally rainy Tuesday night

In the right place and time

When the zeros line up on the 24 hour clock

Given a convex set, we want to find the “center” of this set.

• Chebyshev center; this is not unique
• center of the maximum volume inscribing ellispsoid—this is also affine invariant

• SU-SOC175 JAN052025
• SU-SOC175 JAN122025
• SU-SOC175 JAN142025
• SU-SOC175 JAN212025
• SU-SOC175 JAN262025
• SU-SOC175 JAN282026
• SU-SOC175 FEB022025
• SU-SOC175 FEB042025
• SU-SOC175 FEB112026

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}

In convex optimization, relax and round / polishing is a procedure by which you perform a local search after coming up with a relaxation, and round into the actual feasible set (such as integers).