minimax duality

Considering a bilevel optimization problem (or saddle point problem) on the two-argument function $f(x, y)$, in general it holds that

That is, the inner optimization is at least as 'powerful' as the outer optimization. The difference between the two sides of the inequality is the duality gap.

We might view this as a two-player zero-sum game: the outer optimizer has to move first (choosing a row of the payoff matrix) and the inner optimizer gets to see their move and choose the best response. Going second gives strictly more information with which to make your move, so you always prefer it.

For example, suppose that $f(x, y) = \|x - y\|$ measures the distance between $x$ and $y$. Then the LHS of the above allows the minimizer to go second, choosing $x = y$ to obtain the objective

while the RHS allows the maximizer to go second, choosing an arbitrarily different value $x \to y + \infty$ so that

Saddle-point property

We say that $\tilde{x}, \tilde{y}$ form a saddle pointUnlike the usual calculus definition, this definition is a global property that does not require $f$ to be differentiable. of $f$ if

This is equivalent to the condition that $\tilde{x}$ maximizes $f(\cdot, \tilde{y})$ and $\tilde{y}$ minimizes $f(\tilde{x}, \cdot)$,

If a saddle point exists, it follows that the minimax inequality is tight (equivalently, the duality gap is zero - sometimes called strong duality):

with both sides obtaining the value $f(\tilde{x}, \tilde{y})$.

Why? From the definition of the saddle point, it follows that

since the outer minimizer can always choose $y = \tilde{y}$ to get a value of $f(\tilde{x}, \tilde{y})$, so it will always do at least that well at minimizing the value. A symmetric argument shows that

Putting these facts together, we derive the opposite of the minimax inequality,

which implies our conclusion.

The converse is also true: strong duality implies that the common value is obtained at a saddle point $x^*, y^*$, where $x^* = \arg\max_x \min_y f(x, y)$ is primal optimal and $y^* = \arg\min_y \max_x f(x, y)$ is dual optimal.