优化问题之拉格朗日乘子法&KKT条件分析

优化问题

1. 无约束优化问题

   minf(x)$minf(x)$，由Fermat’s theorem可知，可微函数的极值点都是其驻点（必要条件），故令其导数为零即可求解，当然也可利用梯度下降算法求解；

2. 等式约束优化问题

   minf0(x),  s.t., hi(x)=0, i=1,2,⋯,p$$min{f}_0(x),s.t.,h_i(x)=0,i=1,2,\cdots ,p$$
   对于这种情形我们常使用拉格朗日乘子法（Lagrange multiplier）求解；

3. 不等式约束优化问题

   minf0(x)$$min{f}_0(x)$$
   s.t., hi(x)=0,i=1,2,⋯,p$$s.t.,h_i(x)=0,i=1,2,\cdots ,p$$
   fi(x)≤0,i=1,2,⋯,m,$$f_i(x)\le 0,i=1,2,\cdots ,m,$$

   对于这种情形我们常使用KKT条件求解，Lagrange 函数L:Rn×Rm×Rp→R$R^n\times R^m\times R^p\to R$为

   L(x,λ,v)=f0(x)+∑i=1mλifi(x)+∑i=1pvihi(x),$$L(x,\lambda ,\mathcal{v})=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{v}_i{h}_i(x),$$
   我们假设该问题的定义域（非可行域）为
   D=⋂i=0mdomfi∩⋂i=1pdomhi,且原问题的最优值为p∗$$\mathcal{D}=\bigcap _{i=0}^m\mathbf{d}\mathbf{o}\mathbf{m}{f}_i\cap \bigcap _{i=1}^p\mathbf{d}\mathbf{o}\mathbf{m}{h}_i,且原问题的最优值为p^{\ast }$$
   另外我们定义Lagrange 对偶函数g:Rm×Rp→R$R^m\times R^p\to R$为Lagrange函数关于定义域内x$x$取得的最小值，即，
   g(λ,v)=infx∈DL(x,λ,v)=infx∈D(f0(x)+∑i=1mλifi(x)+∑i=1pvihi(x)))$$g(\lambda ,v)={inf}_{x\in \mathcal{D}}L(x,\lambda ,v)=in{f}_{x\in \mathcal{D}}\left(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{v}_i{h}_i(x))\right)$$
   我们可以得出对偶函数构成了原问题最优值p∗$p^{\ast }$的下界，即，
   ∀λ⪰0,v,  g(λ,v)≤p∗.$$\mathrm{\forall }\lambda ⪰0,v,g(\lambda ,v)\le p^{\ast }.$$
   令x∗和(λ∗,v∗)$x^{\ast }和({\lambda }^{\ast },v^{\ast })$分别为原问题和对偶问题的某对最优解，且满足强对偶性（对偶间隙为零），那么我们就可以得到，f0(x∗)=g(λ∗,v∗)$f_0(x^{\ast })=g({\lambda }^{\ast },v^{\ast })$。另外，
   KKT为，
   ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪fi(x∗)≤0,hi(x∗)=0,λ∗i≥0,λ∗ifi(x∗)=0,∇f0(x∗)+∑mi=1λ∗i∇fi(x∗)+∑pi=1v∗i∇hi(x∗)=0，i=1,2,⋯,mi=1,2,⋯,pi=1,2,⋯,mi=1,2,⋯,m∗$$\{\begin{array}{lr}{f}_i(x^{\ast })\le 0,& i=1,2,\cdots ,m\\ h_i(x^{\ast })=0,& i=1,2,\cdots ,p\\ {\lambda }_i^{\ast }\ge 0,& i=1,2,\cdots ,m\\ {\lambda }_i^{\ast }{f}_i(x^{\ast })=0,& i=1,2,\cdots ,m\\ \mathrm{\nabla }{f}_0(x^{\ast })+\sum _{i=1}^m{\lambda }_i^{\ast }\mathrm{\nabla }{f}_i(x^{\ast })+\sum _{i=1}^p{v}_i^{\ast }\mathrm{\nabla }{h}_i(x^{\ast })=0，& \ast \end{array}$$
   
   注，对于上面的所有情况的优化问题，目标函数及其约束函数若为凸函数，可行域组成凸集，才能得到全局最优解，否则只能得到局部最优解，因为这些条件只是必要条件，而非充要条件。。。