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

Consider:

\begin{align} f_{0}\qty(x^{*}) &= \text{inf}_{x} \qty(f_{0}\qty(x) + \sum_{i=1}^{m} \lambda_{i}f_{i}\qty(x) + \sum_{i=1}^{p} v_{i}h_{i}\qty(x)) \\ &\leq f_{0}\qty(x) + \dots \\ &\leq f_{0}\qty(x) \end{align}

So the inequality holds strictly

The conjugate of a function \(f\) is \(f^{*}\qty(y) = \text{sup}_{x \in \text{dom }f} \qty(y^{T}x - f\qty(x))\). \(f^{*}\) is convex, even if \(f\) is not.

(fyi \(\text{sup}_{x} = \max_{x}\))