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

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

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。

标签: 对偶问题, 拉格朗日, KKT条件

添加新评论