<aside>
🧸 本文简单说明了如何用轮椅计算跑路路线。
无动画Chapter22Dual.pdf
</aside>
J. S. Lagrange对偶
-
【鞍点saddle point 问题】
鞍点从两个方向看是不同的极值。
$$
\psi(x^,z)\le\psi(x^,z^)\le \psi(x,z^)\\\forall x\in X,z\in Z.
$$
$$
\left\{\begin{aligned}\bm x^=\arg\min_{x\in\mathcal X}\psi(\bm x,\bm z^),\\\bm z^=\arg\min_{z\in\mathcal Z}\psi(\bm x^,\bm z).\end{aligned}\right.
$$
-
【极小极大问题 minimax problem 】
可以先求极小再极大（dual）得$q^$，也可以先求极大再极小（primal）得$w^$。两者互为对偶问题。
<aside>
<img src="/icons/chess-bishop_yellow.svg" alt="/icons/chess-bishop_yellow.svg" width="40px" /> 【弱对偶定理】
【极大极小不等式】
原始问题的极值不小于对偶问题的极值。
$$
w^=\min_{x\in X}\max_{z\in Z} \phi(x,z)\ge \max_{z\in Z}\min_{x\in X}\phi(x,z)=q^.
$$
证明：函数比大小，比最大大就比全局大。整个空间是$X\otimes Y$,子空间的最值内外部的求解实际是耦合一起的。
- 【鞍点存在性】
弱对偶不等式的等号成立条件是存在鞍点。反之亦然。
</aside>
约束优化的拉格朗日函数 【约束优化的拉格朗日函数】
$$
\begin{aligned}
\text{minimize }& f(\boldsymbol{x}) \\
\text{subject to }& \bm h(\bm x)=0 \\
&\bm g(\boldsymbol{x})\leqslant0 \\
\text{其中},f:\mathbb{R}^{n}\rightarrow & \mathbb{R},\boldsymbol{h}:\mathbb{R}^{n}\to\mathbb{R}^{m}, m{\leqslant}n, \boldsymbol{g}:\mathbb{R}^{n}\to\mathbb{R}^{p}
\end{aligned}
$$
$$
L(\bm x,\bm \lambda,\bm \mu)=f(\bm x)+\bm \lambda^T \bm h(\bm x)+\bm \mu^T \bm g(\bm x).
$$
-
【P】
$$
\min_{x}\max_{\lambda,\mu\ge0}L(x,\lambda,\mu)=\min _{\bm x} p(\bm x)
$$
$p(x)$总有这个形式：
$$
p(\bm x)=\left\{\begin{aligned}&f(\bm x)&h(x)=0,g(x)\le 0\\ &+\infty &otherwise\end{aligned}\right.
$$
极大问题将拉格朗日系数与优化变量分离，按照上述构造能否回到拉格朗日函数对应的线性优化问题（原始问题Primal Problem）。
$$
\min f(x)\\s.t.\ h(x)=0,g(x)\le 0.
$$
-
【D】
$$
\max_{\lambda,\mu\ge0}\min_{x}L(x,\lambda,\mu)=\max_{\bm \lambda,\bm \mu}q(\bm \lambda,\bm \mu)
$$
极小问题通常很难求解，假设有显式解，得到对偶问题Dual Problem
$$
\min_{\lambda,\mu\ge 0}q(\lambda,\mu).
$$
其中$q(\lambda,\mu)$是以下问题的显式解：
$$
q(\lambda,\mu)=\min_{x}L(x,\lambda,\mu).
$$
<aside>
<img src="/icons/chess-bishop_yellow.svg" alt="/icons/chess-bishop_yellow.svg" width="40px" />
-
对偶问题有可能是一个很简单的优化问题，也有可能没有显式拉格朗日对偶。
拉格朗日对偶可能没有 显式问题，也可能简化原始问题。
-
对偶类算法 针对可以简化问题的对偶。
-
【强对偶】
弱对偶不等式⇒对偶间隙$gap(D,P)=f(x)-q(\lambda,\mu)$为零。
</aside>
-
举例：哪些优化问题的拉格朗日对偶有显式问题？
<aside>
📢
【弱对偶】
进一步写成
$$
f(x)\ge \min_x f(x)\ge \max_{\lambda,\mu}q(\lambda,\mu)\ge q(\lambda,\mu)\\ f(x)\ge q(\lambda,\mu).
$$
-
【弱对偶问题】原始问题的最小值$\omega^$大于对偶问题的最大值$q^$(弱对偶问题) 故 任取可行解$x,\lambda$
$$
\bm c^T\bm x\ge \bm \lambda^T\bm b
$$
</aside>
【拉格朗日对偶】
- 【充要条件】弱对偶定理的等号条件就是原始问题和对偶问题同解的条件。