如何理解对偶问题以及符号替换

由于最近在写的论文过程中，需要用对偶问题来求解带约束的优化问题。于是，再次将对偶问题以及符号替换问题进行了更为深入的研究。发现对于有约束的优化问题，大都可以采用拉格朗日乘数法将有约束问题转化为无约束问题，然后再对拉格朗日函数求偏导得到极值点，即可实现约束问题的求解以及相应的符号替换。

1 对偶问题的一般理论

注意：构造拉格朗日函数是求解带约束优化问题的重要方法！！！

为便于描述，我们用如下公式表达带约束的优化问题。

$$ \begin{equation} \begin{aligned} & \min_{u}{f(u)} \\ \text{S.t.}~&~g_{i}(u) \le 0,~~i=1,2,\cdots,m \\ &~h_{j}(u) = 0,~~j=1,2,\cdots,n \end{aligned} \end{equation} $$

其对应的拉格朗日函数为

$$ \begin{equation} L(u,\alpha,\beta):=f(u)+\sum_{i=1}^{m}{\alpha_{i}g_{i}(u)}+\sum_{j=1}^{n}{\beta_{j}h_{j}(u)},~\text{其中,}~\alpha_{i} \ge 0 \end{equation} $$

引理1： 公式（1）描述的优化问题等价于

$$ \begin{equation} \begin{aligned} & \min_{u}{\max_{\alpha,\beta}{L(u,\alpha,\beta)}} \\ \text{S.t.:}~&~\alpha_{i} \ge 0,~i=1,2,\cdots,m \end{aligned} \end{equation} $$

证明：

$$ \begin{equation} \begin{aligned} \min_{u}{\max_{\alpha,\beta}{L(u,\alpha,\beta)}} & = \min_{u}\left(f(u)+\max_{\alpha,\beta}{\left(\sum_{i=1}^{m}{\alpha_{i}g_{i}(u)} + \sum_{j=1}^{n}{\beta_{j}h_{j}(u)}\right)}\right) \\ \\ & = \min_{u} \left( f(u)+ \left\{ \begin{aligned} 0 &,~\text{若}u\text{满足}\alpha\text{和}\beta \\ \infty &,\text{否则} \end{aligned} \right. \right) \\ \\ & = \min_{u} f(u),\text{且}u\text{满足约束} \end{aligned} \end{equation} $$

其中，当$g_{i}$不满足约束时，也就是$g_{i}(u) >0$，则可以取$\alpha_{i}=\infty$，使得$\alpha_{i}g_{i}(u)=\infty$；当$h_{j}$不满足约束时，也就是$h_{j}(u)\ne0$，则可以取$\beta_{j}=sign(h_{j}(u))\infty$，使得$\beta_{j}h_{j}(u)=\infty$；当$u$满足条件时，由于$\alpha_{i}\ge 0$，$g_{i}(u) \le 0$，因此，$\alpha_{i}g_{i}(u) \le 0$，因此$\alpha_{i}g_{i}(u)=0$为最大值，即其最大值为0。