背景：
- Lagrange 对偶：对于优化问题
\[\begin{aligned}
&\mathrm{minimize} ~~ &f_0(x)
\\
&\mathrm{subject ~ to} ~~ &f_i(x)\le 0, ~~ h_j(x)=0
\end{aligned}
\]
- 可以建立其 Lagrange 对偶函数 \(L(x,λ,\nu)=f_0(x)+\sum λ_if_i(x)+\sum \nu_jh_j(x)\) ， \(g(λ,\nu)=\inf_x L(x,λ,\nu)\)。
- 无论 \(g(λ,\nu)\) 中 \(λ,\nu\) 怎么变化，它的值都一定是原目标函数的下界，因此其最大值 \(d^*=\sup_{(λ,\nu)}\inf_x L(x,λ,\nu)\) 也是原目标函数的下界。
- 原目标函数的最优值，可以写成如下形式： \(p^*=\inf_x\sup_{(λ,\nu)} L(x,λ,\nu)\)。因此有 \(d^*\le p^*\) ， \(\sup_{(λ,\nu)}\inf_x L(x,λ,\nu) \le \inf_x\sup_{(λ,\nu)} L(x,λ,\nu)\) 。
极大极小不等式：
- 事实上，对于任意函数 f(w,z)，都有 sup inf ≤ inf sup 成立，被称为极大极小不等式。
- 极大极小不等式： \(\sup_z \inf_w f(w,z) ≤ \inf_w \sup_z f(w,z)\) 。
- 证明：
- 首先，有 \(\inf_w f(w,z) ≤ f(w_0,z)\)，z 在定义域上变化，\(\inf_w f(w,z)\) 是 \(f(w_0,z)\) 的逐点下界。
- 因此，可以有 \(\sup_z \inf_w f(w,z) ≤ \sup_z f(w_0,z)\) ，函数最大值（上界）也满足 ≥ 关系。
- 最后，令 \(w_0 = \arg\min_w [\sup_z f(w,z)]\)，即可得到 \(\sup_z \inf_w f(w,z) ≤ \inf_w \sup_z f(w,z)\) 。