拉格朗日对偶性

原始问题：

$\underset{x}{min}f(x)$

$\begin{matrix}
s.t. & c_{i}(x)\leq 0，i=1\sim k \\
 &h_{j}(x)= 0，j=1\sim l  
\end{matrix}$

 

广义拉格朗日函数

$L(x,\alpha ,\beta )=f(x)+\sum_{i=1}^{k}\alpha _{i}c_{i}(x)+\sum_{j=1}^{l}\beta _{i}h_{j}(x)$

$\alpha _{i}\geq 0$

$\alpha _{i}$和$\beta _{i}$为拉格朗日乘子；

$\theta _{p}(x)=\underset{\alpha ,\beta ,\alpha _{i}\geq 0}{max}L(x,\alpha ,\beta )$

由于$h_{j}(x)=0$，第三项为0，$c_{i}(x)\leq 0$

则对于max L

$\left.\begin{matrix}
c_{i}(x)=0\\
c_{i}(x)< 0,\alpha _{i}=0
\end{matrix}\right\}故第二项为0$

则$\theta _{p}(x)=f(x)$

$\underset{x}{min}\theta _{p}(x)=\underset{x}{min}\underset{\alpha ,\beta， \alpha _{i}\geq 0}{max}L(x,\alpha ,\beta )$

即为原始问题

 

对偶问题

$\underset{\alpha ,\beta, \alpha _{i}\geq 0}{max}\underset{x}{min}L(x,\alpha ,\beta )$

1、若原始问题和对偶问题都有最优值，则

$max minL=minmaxL$

且最优解同时为$x^{*},\alpha ^{*},\beta ^{*}$（有解则解相同）

2、KKT（有解$\Leftrightarrow$满足KKT）

$\begin{matrix}
\bigtriangledown _{x}L(x,\alpha ,\beta )=0\\
\alpha _{i}c_{i}(x_{i})=0\\
c_{i}(x_{i})\leq 0\\
\alpha _{i}\geq 0\\
h_{j}(x)=0
\end{matrix}$

第一个条件为偏导等于0；

第二个为原始问题的中间结果；

最后三个为原始约束条件；