亲宝软件园·资讯

展开

拉格朗日对偶性

颀周 人气:0

  在约束最优化问题中,常用拉格朗日对偶性将原始问题转换为对偶问题求解。

广义拉格朗日函数

  称最优化问题

$\begin{equation} \begin{array}{lcl} \min\limits_{x\in R^n} f(x)\\ \begin{aligned} \text{s.t.}\;\;&c_i(x) \le 0,\;\;i=1,2,...,k \\ &h_j(x)=0,\;\;j=1,2,...,l \end{aligned} \end{array} \end {equation}$

  为原始最优化问题。使用以上优化问题构造广义拉格朗日函数:

$L(x,\alpha,\beta) = f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x)$

  其中$\alpha_i\ge 0,\beta_j\in R$是拉格朗日乘子。可以发现,对于违反原始问题约束的$x$,即存在某个$c_i(x)>0$,或某个$h_j(x)\ne 0$,有:

$\max\limits_{\alpha\ge 0,\beta}L(x,\alpha,\beta) = +\infty$

  因此有:

$\begin{equation} \max\limits_{\alpha\ge 0, \beta}L(x,\alpha,\beta) = \left\{ \begin{aligned} &f(x),\;\;x满足原始条件约束\\ &+\infty,\;\;else \end{aligned} \right. \end {equation}$

  因此原始问题的最优值可以表示为:

$p^* = \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$

  从而将约束条件与待优化问题结合到了一起,称为广义拉格朗日函数的极小极大问题。

对偶问题以及KKT条件

对偶问题

  将极小极大交换一下,得到

$d^* = \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)$

  即为原始问题的对偶问题的最优值。对偶问题转换为带条件的形式就是:

$\begin{aligned} &\max\limits_{\alpha,\beta}\min\limits_{x} L(x,\alpha,\beta)\\ &\;\text{s.t.}\;\;\alpha_i\ge 0, \;\; i=1,2,...,k \\ \end{aligned}$

  如果原始问题与对偶问题都有最优值,$p^*$和$d^*$,则:

$d^*= \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)\le  \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)= p^*$

  这是因为,对于任意$x,\alpha,\beta$,有:

$\min\limits_{x}L(x,\alpha,\beta)\le L(x,\alpha,\beta)\le\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$

  也就是左边关于$\alpha,\beta$的函数,总是小于等于右边关于$x$的函数。所以有$d^*\le p^*$。

KKT条件

  某些情况下,对偶问题与原始问题有相等的最优值,即$d^* = p^*$,这时解对偶问题可以替代原始问题,条件如下:

  1、$f(x)$和$c_i(x)$是凸函数;

  2、$h_j(x)$是仿射函数,即一次函数;

  3、不等式约束$c_i(x)$是严格可行的,即存在$x$,对所有$i$有$c_i(x)<0$。如果不存在这样的$x$的话,实际上就是等式约束了。这是因为,每个$x$都会使某个不等式约束取等号,也就可以仅使用等式约束来表示这些$x$了。

  此时有:

$p^*=d^*=L(x^*,\alpha^*,\beta^*)$

  且算出$x^*,\alpha^*,\beta^*$的充要条件是(KKT条件):

$\left\{ \begin{aligned} &\nabla_xL(x^*,\alpha^*,\beta^*) = 0 \\ &\alpha^*c_i(x^*) = 0, \;\; i=1,2,...,k \\ &c_i(x^*) \le 0, \;\; i=1,2,...,k \\ &\alpha_i^*\ge 0, \;\; i=1,2,...,k \\ &h_j(x^*) = 0, \;\; i=1,2,...,l \\ \end{aligned} \right.$

直观理解

 

   上图显示了优化的一个情况。等高线表示的是待优化函数$f(x)$($x$二维),越向中心,值越小,是个标准的凸函数。红圈表示不等式约束(内部),是个凸函数。蓝线表示等式约束(线上),是仿射函数。则$x$可取的值在红圈与其内部的蓝线上。可观察有如下几个符合KKT条件的事实:

  1、三个白色箭头分别表示三个函数的梯度方向,此时有三个梯度的加权矢量和为0,与KKT条件中的1式吻合。

  2、因为最优点在红圈上,因此不等式约束取等为0,有2式。

  3、3式和5式是原本的约束条件。

  4、观察三个梯度的方向,因为$f(x)$的方向不能改变(1式梯度前没系数),所以为了矢量和为0,$\alpha$必须大于0。而由于等式约束的仿射函数取反后约束不变,而梯度方向却变反了,因此$\beta$没有正负的限制。

加载全部内容

相关教程
猜你喜欢
用户评论