强对偶性

1. 原始问题、拉格朗日函数与对偶问题

1.1 原始优化问题

考虑一个一般的约束优化问题 $P$: ${\min }_{\mathbf{x}}{f}_0(\mathbf{x})$ $\text{s.t.}{f}_i(\mathbf{x})\le 0,i=1,\dots ,m\text{(不等式约束)}$ $h_j(\mathbf{x})=0,j=1,\dots ,p\text{(等式约束)}$ 设 $\mathcal{D}$ 为 $f_0,f_i,h_j$ 的定义域交集， $\mathcal{X}$ 为可行域。设原始问题的最优值（下界）为 $p^{\ast }$： $p^{\ast }={\inf }_{\mathbf{x}\in \mathcal{X}}{f}_0(\mathbf{x})$

1.2 拉格朗日函数

我们引入拉格朗日乘子 $\lambda \in {\mathbb{R}}^m$ 和 $\nu \in {\mathbb{R}}^p$，并构造拉格朗日函数 $L:{\mathbb{R}}^n\times {\mathbb{R}}^m\times {\mathbb{R}}^p\to \mathbb{R}$: $L(\mathbf{x},\lambda ,\nu )=f_0(\mathbf{x})+{\sum }_{i=1}^m{\lambda }_i{f}_i(\mathbf{x})+{\sum }_{j=1}^p{\nu }_j{h}_j(\mathbf{x})$ 其中，约束要求 ${\lambda }_i\ge 0$。

1.3 对偶函数

对偶函数 $g(\lambda ,\nu )$ 是拉格朗日函数关于 $\mathbf{x}$ 的下确界： $g(\lambda ,\nu )={\inf }_{\mathbf{x}\in \mathcal{D}}L(\mathbf{x},\lambda ,\nu )$

核心性质： 对偶函数 $g(\lambda ,\nu )$ 总是凹函数，无论原始问题 $f_0,f_i,h_j$ 是否是凸的。

1.4 对偶优化问题

对偶问题 $D$ 是最大化对偶函数： ${\max }_{\lambda ,\nu }g(\lambda ,\nu )$ $\text{s.t.}{\lambda }_i\ge 0,i=1,\dots ,m$ 设对偶问题的最优值（上界）为 $d^{\ast }$： $d^{\ast }={\sup }_{\lambda ⪰0,\nu }g(\lambda ,\nu )$

---

2. 上下界的关系：弱对偶性

“上下界在优化点相等的特性”的基础是弱对偶性。

2.1 弱对偶性定理

对于任何优化问题（凸或非凸），原始最优值 $p^{\ast }$ 总是大于或等于对偶最优值 $d^{\ast }$： $d^{\ast }\le p^{\ast }$

推导证明：

设 $\mathbf{x}\in \mathcal{X}$ 是原始问题的可行解， $(\lambda ,\nu )$ 是对偶问题的可行解（即 $\lambda ⪰0$）。

1. 由于 $\mathbf{x}$ 是可行解，我们有 $f_i(\mathbf{x})\le 0$ 和 $h_j(\mathbf{x})=0$。
2. 由于 ${\lambda }_i\ge 0$，因此 ${\lambda }_i{f}_i(\mathbf{x})\le 0$ 且 ${\nu }_j{h}_j(\mathbf{x})=0$。

考虑拉格朗日函数： $L(\mathbf{x},\lambda ,\nu )=f_0(\mathbf{x})+\underset{\le 0}{\underbrace{\sum _{i=1}^m{\lambda }_i{f}_i(\mathbf{x})}}+\underset{=0}{\underbrace{\sum _{j=1}^p{\nu }_j{h}_j(\mathbf{x})}}$ $⟹L(\mathbf{x},\lambda ,\nu )\le f_0(\mathbf{x})$

现在，根据对偶函数的定义，它是关于 $\mathbf{x}$ 的下确界： $g(\lambda ,\nu )={\inf }_{\mathbf{z}}L(\mathbf{z},\lambda ,\nu )$ 由于 $\mathbf{x}$ 是 $\mathcal{D}$ 中的一个点，显然： $g(\lambda ,\nu )\le L(\mathbf{x},\lambda ,\nu )$

结合上述两个不等式： $g(\lambda ,\nu )\le f_0(\mathbf{x})$

由于这个关系对所有原始可行解 $\mathbf{x}$ 和所有对偶可行解 $(\lambda ,\nu )$ 都成立，我们可以对左边取上确界（对偶问题），对右边取下确界（原始问题）： ${\sup }_{\lambda ⪰0,\nu }g(\lambda ,\nu )\le {\inf }_{\mathbf{x}\in \mathcal{X}}{f}_0(\mathbf{x})$ $⟹d^{\ast }\le p^{\ast }$

弱对偶性总是成立的，它意味着对偶问题提供了一个原始问题最优值的下界。

---

3. 优化点相等的特性：强对偶性

强对偶性是“上下界在优化点相等”的特性。

3.1 强对偶性定理

定义： 如果 $d^{\ast }=p^{\ast }$，则称原始问题和对偶问题之间存在强对偶性。

重要性： 在强对偶性成立时：

1. 对偶问题提供了一个紧致的下界。
2. 求解对偶问题与求解原始问题是等价的（这通常更容易，因为对偶函数总是凹的）。
3. 原始最优解 ${\mathbf{x}}^{\ast }$ 和对偶最优解 $({\lambda }^{\ast },{\nu }^{\ast })$ 之间满足 KKT (Karush-Kuhn-Tucker) 条件。

3.2 强对偶性的条件：Slater 条件

对于凸优化问题（即 $f_0,f_i$ 是凸函数，$h_j$ 是仿射函数），强对偶性成立的充分条件是 Slater 条件：

Slater 条件： 存在一个严格可行点 ${\mathbf{x}}_{\text{slater}}\in \mathcal{D}$，使得所有非仿射不等式约束严格满足： $f_i({\mathbf{x}}_{\text{slater}})<0(\text{对于非仿射 }{f}_i)$ $f_i({\mathbf{x}}_{\text{slater}})\le 0(\text{对于仿射 }{f}_i)$ $h_j({\mathbf{x}}_{\text{slater}})=0$

只要满足 Slater 条件，并且原始问题是凸的，我们就保证 $d^{\ast }=p^{\ast }$。

3.3 KKT 条件：最优解的充要条件

当强对偶性成立时， ${\mathbf{x}}^{\ast }$ 是原始问题的最优解， $({\lambda }^{\ast },{\nu }^{\ast })$ 是对偶问题的最优解，当且仅当它们满足 KKT 条件：

条件	形式化表示	意义
1. 可行性 (Primal Feasibility)	$f_i({\mathbf{x}}^{\ast })\le 0,h_j({\mathbf{x}}^{\ast })=0$	${\mathbf{x}}^{\ast }$ 必须是原始问题的可行解。
2. 对偶可行性 (Dual Feasibility)	${\lambda }_i^{\ast }\ge 0$	${\lambda }^{\ast },{\nu }^{\ast }$ 必须是对偶问题的可行解。
3. 互补松弛性 (Complementary Slackness)	${\lambda }_i^{\ast }{f}_i({\mathbf{x}}^{\ast })=0,\forall i$	对于非紧约束 ($f_i({\mathbf{x}}^{\ast })<0$)，其拉格朗日乘子必须为零 (${\lambda }_i^{\ast }=0$)。
4. 梯度为零 (Stationarity)	${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\lambda }^{\ast },{\nu }^{\ast })=0$	${\mathbf{x}}^{\ast }$ 使拉格朗日函数达到极小值。

---

4. 结论：上下界相等的数学意义

“上下界在优化点相等”的特性，即 $d^{\ast }=p^{\ast }$，是凸优化理论中最有价值的成果之一。

它意味着：

${\min }_{\mathbf{x}\in \mathcal{X}}{f}_0(\mathbf{x})={\max }_{\lambda ⪰0,\nu }{\inf }_{\mathbf{x}\in \mathcal{D}}L(\mathbf{x},\lambda ,\nu )$

当 $d^{\ast }=p^{\ast }$ 时， ${\mathbf{x}}^{\ast }$ 是原始问题的解， $({\lambda }^{\ast },{\nu }^{\ast })$ 是对偶问题的解，它们形成一个鞍点 (Saddle Point)：

$L({\mathbf{x}}^{\ast },\lambda ,\nu )\le L({\mathbf{x}}^{\ast },{\lambda }^{\ast },{\nu }^{\ast })\le L(\mathbf{x},{\lambda }^{\ast },{\nu }^{\ast })$

在鞍点处，原始问题的解 ${\mathbf{x}}^{\ast }$ 使得拉格朗日函数极小化，而对偶乘子 $({\lambda }^{\ast },{\nu }^{\ast })$ 使得拉格朗日函数极大化。强对偶性成立，确保了这种极小化和极大化的顺序可以互换，并且最终的最优值是相同的。