Consider the Robust Approximation problem:

Robust Approximation

Minimize \(\norm{Ax - b}\) with uncertain \(A\); two approaches—

1. stochastic: minimize \(\mathbb{E}\norm{Ax -b }\)
2. worst-case: set \(\mathcal{A}\) of possible values of \(A\), minimize \(\text{sup}_{A \in A} \norm{Ax - b}\)

Key Sequence

Notation

• Stochastic Robust Least Squares
  • worst-case robust least-squares
• Maximum Likelihood Estimation with Convex Optimization

New Concepts

• change of variables

Important Results / Claims

Questions

Interesting Factoids

• fun fact: any (even non-convex) problem in two quadratics usually has zero duality gap and thus its dual can be the solution to the primal problem

Consider some kind of ellipsoid where your data is constrained:

\begin{align} \mathcal{A} = \qty {\bar{A} + u_1 A_1 + \dots + u_{p} A_{p} \mid \norm{u}_{2} \leq 1} \end{align}

You can form the “worst-case robust least squares”:

\begin{align} \min \text{sup}_{A \in \mathcal{A}} \norm{A x - b}_{2}^{2} = \min \text{sup}_{\norm{u}_{2} \leq } \norm{P\qty(x) u + q\qty(x)}_{2}^{2} \end{align}

This is usually a minimax problem, but taking the dual of the inner maximize thing turns out has zero duality gap.

• norm approximation