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

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

1 对偶问题的一般理论

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

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

$$\begin{array}{}\text{(1)}& \begin{array}{rl}& \underset{u}{min}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{array}\end{array}$$

其对应的拉格朗日函数为

$$\begin{array}{}\text{(2)}& 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{array}$$

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

$$\begin{array}{}\text{(3)}& \begin{array}{rl}& \underset{u}{min}\underset{\alpha ,\beta }{max}L(u,\alpha ,\beta )\\ \text{S.t.:}& {\alpha }_i\ge 0,i=1,2,\cdots ,m\end{array}\end{array}$$

证明：

$$\begin{array}{}\text{(4)}& \begin{array}{rl}\underset{u}{min}\underset{\alpha ,\beta }{max}L(u,\alpha ,\beta )& =\underset{u}{min}(f(u)+\underset{\alpha ,\beta }{max}(\sum _{i=1}^m{\alpha }_i{g}_i(u)+\sum _{j=1}^n{\beta }_j{h}_j(u)))\\ \\ & =\underset{u}{min}(f(u)+\{\begin{array}{rl}0& ,\text{若}u\text{满足}\alpha \text{和}\beta \\ \mathrm{\infty }& ,\text{否则}\end{array})\\ \\ & =\underset{u}{min}f(u),\text{且}u\text{满足约束}\end{array}\end{array}$$

其中，当$g_i$不满足约束时，也就是$g_i(u)>0$，则可以取${\alpha }_i=\mathrm{\infty }$，使得${\alpha }_i{g}_i(u)=\mathrm{\infty }$；当$h_j$不满足约束时，也就是$h_j(u)\ne 0$，则可以取${\beta }_j=sign(h_j(u))\mathrm{\infty }$，使得${\beta }_j{h}_j(u)=\mathrm{\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。