凸优化中的弱对偶性定理

凸优化中的弱对偶性定理是凸优化理论中的一个重要基础定理，其表述及相关内容如下：

1. 定理表述：

   • 对于原优化问题（也称为“原始问题”）和其对应的对偶问题，记原问题的最优值为$p^*$，对偶问题的最优值为$d^*$，那么一定存在$d^*\leq p^*$，这个性质就称为弱对偶性。

2. 证明思路：

   • 通常基于拉格朗日函数来证明。对于标准形式的凸优化原问题：

   $<script type="math/tex; mode=display">\begin{cases}\min\;f_0(x)\\s.t.\;f_i(x)\leq0, i = 1,2,\cdots,m\\h_i(x)=0, i = 1,2,\cdots,p\end{cases}$ - 构造拉格朗日函数$L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^{m}{\lambda_if_i(x)}+\sum_{i=1}^{p}{\nu_ih_i(x)}$，其中$\lambda_i\geq0$，$\lambda$ 和 $\nu$ 称为对偶变量或拉格朗日乘子向量。 - 定义拉格朗日对偶函数$g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu)$，其中$D$ 是原问题的可行域。 - 因为对于任意的$\lambda\geq0$和$\nu$，$g(\lambda,\nu)$ 是原问题目标函数在满足一定约束条件下的一个下界（即对于所有$x\in D$，都有$g(\lambda,\nu)\leq L(x,\lambda,\nu)$），所以对偶问题是在寻找拉格朗日对偶函数的最大值，而原问题是寻找目标函数的最小值，这就自然导致了对偶问题的最优值$d^*$不会超过原问题的最优值$p^*$，即$d^*\leq p^*$。

3. 意义和作用：

   • 提供下界估计：在求解原问题比较困难时，可以通过求解对偶问题来得到原问题最优值的一个下界估计。这对于优化算法的设计和分析非常重要，例如在一些迭代算法中，可以利用对偶问题的解来判断当前解的优劣，或者作为算法收敛的判断依据。
   • 理论分析基础：弱对偶性定理是凸优化理论中许多其他重要定理和概念的基础，比如强对偶性定理。强对偶性是在满足一定条件下$d^* = p^*$的情况，而弱对偶性是强对偶性的基础，对理解凸优化问题的性质和求解方法具有重要的理论意义。