第十二章-增广目标函数法课件.ppt

1、最优化最优化主讲：刘陶文课件制作：刘陶文课件制作：刘陶文唯楚有材唯楚有材 於斯为盛於斯为盛学好最优化，走遍天下都不怕学好最优化，走遍天下都不怕第十二章第十二章 约束问题算法约束问题算法(I)增广目标函数法增广目标函数法一、罚函数法一、罚函数法二、二、LagrangeLagrange乘子法乘子法m,1,0)(,2 ,1,0)(.)(min :11mEjxhmIixgtsxfji考察一般约束问题0)(,0)(|)1.12(0)(0)(.)(min :)(,),(),()()(,),(),()(2121111xhxgxDxhxgtsxfxhxhxhxhxgxgxgxgEIEITmmmETmI可行域写

2、成则约束问题可以等价地记.,法称为序列无约束问题算也束问题通常需求解一系列无约无约束问题来求解题化为增广目标函数将约束问增广目标函数法：构造乘子法内点罚函数法外点罚函数法罚函数法：Lagrange第一节 罚函数法综合表达式目标函数与约束函数的增广目标函数:的求解列无约束问题问题的求解转化成一系使得约束中去然后将它加到目标函数惩罚函数特点构造某种构造方法：根据约束的 ,.,于原约束问题的极小点直到收敛内移动或者一直保持在可行域可行域靠近向题的极小点或者无限地迫使这一系列无约束问值函数迭代点给以很大的目标中企图违反约束的那些对无约束问题求解过程策略惩罚解释：利用这种外点罚函数法 1.1.12D外点

3、*x思想思想逼近迭代点向可行域从而使内部的点不惩罚施加惩罚即违反约束的点外的点对可行域DD,)(.,)()(min ,),()(法求解无法用无约束问题的方其特性太坏而且无法实现仅是理论上的想法然而这样的约束问题则原约束问题等价于无惩罚外的点施加无限的即对如构造函数xFxFDDxDxxfxFnRx.,)(0,0,)(,)(,),()(,0,)(,)()()()(,惩罚函数法不同的形式对应不同的有多种形式如果如果的程度偏离可行域的值的大小反映其中为罚参数或罚因子一般地如果很大的正数如果满足：称为惩罚函数其中构造辅助函数即束的点施加有限惩罚现实的想法是对违反约xSDxDxxSDxxSxSxPDxDx

4、xPxPxPxfxF.)(,)(,)(|)(|0 ),(min|)(|0),(min )()()(,),()(0,),(min)(,)()()()(xSDxxSDxxSxhxgxhxgxhxgxSDxEjxhxhIixgxgxEIEjjIiiEjjIiijjii满足：显然即来描述度函数的范数的程度可以用违反约束偏离可行域点函数我们定义约束违反度偏离可行域的程度为了描述点.|)(|0 ),(min|)()(|)(|0 ),(min|)()(:Courant .,2|)(|21|0 ),(min|21)()(|)(|0 ),(min|)()(,11122222罚函数罚函数和他们分别称为是另外两个重

5、要的罚函数罚函数它是最早的罚函数罚函数之为这个辅助函数称范数量函数的由于这里我们使用了向或我们得到辅助函数因此LLxhxgxfxFxhxgxfxFLxhxgxfxFxhxgxfxFEIEIEIEI问题极小点的关系约束察罚函数的极小点与原下面我们通过例子来观).()(.)(min :1.1.12xxgtsxxf问题考察简单的不等式约束例*,(xD极小点)(:)(0,)(1),(,)(0 1,min)(:2xxFxFxxxxxxFxxxFL的极小点得驻点即令则罚函数为对应的可行域可行域*2)(,.)()(min :,xxxxF时当特别靠近向原约束问题的极小点的极小点无约束问题增大时当罚因子由图可知

6、xxtsxxxf.)(min 2.1.12考虑等式约束问题例Tx)1 ,1(*2222121211212122*1:()(-2)2()22(-2)021()()2 2(-2)021,min()()(1,1)TLF xxxxxF xxxxxxF xxxxxF xxx 解 该问题的罚函数为令当的极小点.)(,)(,)()(min,2.1.121.1.12最优解时就是所求的原问题的当特别逐渐靠近可行域增大时而当点的极小无约束问题看出及例由例DxDxDxxF)(min :,2 ,1 ,0,kxFkk题求解一系列的无约束问对的数列取为一个趋于正无穷大把在实际算法中 1.,1:;44.STOP.,)(3,

7、min:2)(21)()(1.1:.0,1 ,0;0)(1.12 1k)(110转步令：步否则转步则得解若：步得解题为初始点求解无约束问以：步构造增广目标函数：步置精度放大系数初始罚因子选定初始点：步外点罚函数法算法kkxxSxFxxSxfxFkRxkkkkkxkknkk函数中可选用多种增广目标注意：在步1)(.)(min 3.1.12为常数用外点法求解例ccxxxtsxxxf,min2)()(:2cxxxxxxF构造增广目标函数解：2)()(),(0,2)()(xxxxxFcxcxcxxxxxxF如果如果求导得0)(0,)(21xxFxxF令图解如下Txcx)122 ,122()(,)1(1

8、时当Tcccxcx)132)(2 ,13)()(,22)(时当*T)1()1(1)(1,)(,),(:.1 1xxxc时并且驻点为：情形*T)()()2 ,()(,),(:.xccxxc时并且驻点为：情形*xcx c1x2x1 )(ca*xcx c1x2x1 )(cb外点法的收敛性先介绍下面的性质：.)(3);)(2);)(1),12.1 1.1.12k单调非降关于序列单调非降关于序列单调非增关于序列则单调增加且序列产生由算法设引理kxFkxfkxSxkkkkk)()(,0)()()(,)()(),()(,)(-kkkkkkkkkkkkkxSxSxSxSxFxFxFxFxkkkk因此即得上述两

9、式相加我们有定义及由证明：.(2),)()()()()(),()()(-成立因此变形得于由kkkkkkkkxfxSxSxfxfxFxFkk.(3),)()(21)()(21)()()(3)1-1-11-成立因此kkkkkkkkkxFxSxfxSxfxFxFkkk.(12.1).,1.12 .)1.12(,1.1.12的解的任何极限点都是问题则趋于单调增加且其中产生由算法设序列存在的解且问题连续可微设函数定理kkkjixxhgf.,0,)()(lim,)()(2)(0 )()()()()()()()()()()(.,*是极小点从而即得令推出又由的连续性得由则有不妨设小点的一个极是若小点是证明：设

10、约束问题的极xDxxSxSkxfxfxSxSxfxfxfxffxfxSxfxFxFxfxxxxxkkkkkkkkkkkkkkkkkk第二节 内点罚函数法.,.,.函数法内点罚函数法又称障碍穿越边界阻碍迭代点的墙在边界上筑成一道很高这好比大边界上点的惩罚为无穷的惩罚来越大对接近边界的点施加越内部移动都是在可行域的内点罚函数法的迭代点.,约束问题故仅适合于不等式的内部非空内点法要求可行域D)6.12(,0)(.)(minIixgtsxfi,0)(|:,0)(|:0IixgRxDDIixgRxDinin的内部可行域思想思想.)(,:)(),()()(称为障碍因子这里趋于正无穷大趋向于边界时当满足其中

11、构造增广目标函数xSxxSDxxSxfxF?)(如何构造呢xS)()(,0)(,:,xSxSxgIixxi约束有效即至少有某个约束成为时趋于边界上某点当,():()-ln()1 ()()ii Ii IiS xS xg xS xg x很显然主要有两种简单的形式对数形式倒数形式xtsxxf.)(min 1.2.12考察约束问题例.,1 ,*得原问题的解则令xx.:,)(1)(),(min )(xxxFRxxFxxxxF得解令求解：是可行域的边界这里构造增广目标函数xoF1)(xf)(1-xS)(xFx).()(.)(min :.12xxgtsxxf等式约束问题用内点罚函数法求解不例*,)(),(m

12、in:)(ln)(xxxxxxFRxxFxxxF令得解：令求解无约束问题：解：构造增广目标函数图解如下 1.,:;44.STOP.,)(3,min:2)()()(1.:.,;0)(2.12 1k-)(转步令：步否则转步则得解若：步得解题为初始点求解无约束问以：步构造增广目标函数：步置精度放大系数初始罚因子选定初始点：步内点罚函数法算法kkxxSxFxxSxfxFkRxkkkkkxkknkk .)()(min 3.2.12xxtsxxxf用内点罚函数法求解例实际当中按数值法求解xxxxxF11)()(:解：构造增广目标函数xxxFxxxxF1)()(1)()(令Tx1,:得解*0 ,1 ,xxT

13、）（则令.(12.6).,1.12 .6)12(.,)(,1.1.120的解问题的任何极限点都是则单调增加且趋于其中产生由算法设序列的解存在问题设非空且连续可微设函数定理kkkixxDIigfkkkkkkkxStsxfxxSkxFkxSxk)(.)(min :),(3);)(2);)(1),12.2 3.1.12k也是下列问题的解则记单调非增关于序列单调非降关于序列则单调增加且序列产生由算法设引理关于内点法的收敛性第三节 乘子法一、等式约束问题的乘子法.Lagrange,.,Hessian,函数的乘子法人们提出了基于为克服这一缺陷算上的困难从而导致数值计矩阵出现病态广目标函数的这将导致增罚参数

14、需取足够大的值足够好的近似解为获得数法求解约束问题时当使用前面介绍的罚函)8.12(,0)(.)(min :Ejxhtsxfj考虑等式约束问题思想思想.KKT,:Lagrange点点逼近原约束问题的定使得增广目标函数的稳行点施加某种惩罚对非可函数构造增广目标函数利用(12.11)()()()(),(),(.)()()(),(),(:),.(EiiEiiiEiiEiixhxhxfxhxLxLxhxSxSxLxL从而这里构造增广目标函数考虑等式约束问题.向可行域靠近使用惩罚项的目的是使x惩罚项nRxxL ),(min :求解无约束问题)()()()()(),(,xxhxhxhxfxLEiiiEii

15、ix设其解为令求驻点点呢的在什么情况下是问题思考：KKT)8.12()(xEjxhj,0)()2(,)1(:*满足两个条件Ejxhjk,0)(,*使得增大罚因子构造近似解决办法：具体分析如下：0)()(KKT*Eiiixhxf条件：0)()()(0)()()()(),(.),(min :,)()(*EikikikkikkiEikikkiEikikkkxkkkkxhxhxfxhxhxhxfxLxxLk即有则有得解求解无约束问题及罚因子的估计给定乘子)1(),(-,KKT(12.8)1)()1(为放大系数其中增加罚因子令条件的比较kkkkikkikiEixh 1.,:;),(5.;,|)(|)(|

16、44.STOP.,)(|)(|3.),(min :2)(),(),(.:.1);(0,;,0)(3.12)()(111-1/21转步令令：步否则则令成立若：步否则转步则得解若：步设其解是题为初始点求解无约束问并以：步构造增广目标函数：步置精度常数初始罚因子初始乘子估计选定初始点：步等式约束问题的乘子法算法kkEixhxhxhxxSxhxxLxxSxLxLkRxkikkikikkkkkEkEkkkEkkkkkknkk.)8.12(,4).(,|)(|)(|,|)(|,)(21,3.12,1-k的最优解问题趋于无穷大就能获得原无需这意味着在乘子法中见算法步不必增大则如满足的值有足够下降当因此向可行

17、域靠近迫使数的目的是通过增大罚参我们使用罚项中在算法正如前面分析kkkEkEkEkkkxhxhxhxxS 01)(.)(min 2.12xxxhtsxxxxxf：用乘子法求解下列问题例12,1初始乘子估计解：选取罚因子21)(21 1)(),(:xxxxxxxxxLkk构造乘子罚函数TT)1(2)1(1)1(143 ,21),(),(min :)1(xxxxLk得解求解第一次迭代TT)(2)(1)(2)(41 2),(61),(,),(min ,kkkkkkxxxxLk得解次迭代：求解在地一般地kkkkkkkxh61 42622 )(:修正乘子估计*52,kk时当显然*T)(53 ,52 :x

18、xk由此推出乘子法的收敛性.Lagrange,)()()(),(min ,0,.,LICQ,).(2.2.12*乘子处的是其中的严格局部最优解是无约束问题使得对所有存在则处二阶充分条件成立如果在成立处且在的一个局部最优解是问题设定理xxhxhxfxLxxxxEiiEiii二、一般约束问题的乘子法)17.12(,0)(.)(min Iixgtsxfi题：首先考虑不等式约束问).(,z)(.)(min :z Iixgtsxfii的等式约束问题将不等式问题化为等价引入松弛变量IiiiIiiiixgxgxfxLz)(z)()()z,(Lagrange函数如下：构造增广IiiiiixgxfxL）（或)(

19、1z2)()z,(配方:zz,求极小即关于我们消除松弛变量为降低维数)z,(min xL求解无约束问题0,)z,(xLz令iiiiixgxgzIi)(,max)(,max ,因此函数为后得增广中消去将上式代入Lagrangez)z,(xLIiiiixgxfxL)(,max)(),(IiiiiixgxfxL）（或)(1z2)()z,(z)(2z )(zz)z,(,iiiiiiiiixgzxgxLIi即)26.12(,0)(,0)(.)(min EjxhIixgtsxfji式约束的问题：考虑同时含等式和不等).()()()(,max)(),(Lagrange,EjjEjjjIiiiixhxhxgx

20、fxL函数为构造增广基于前面的分析)()(-)()(,0 max-)(),(xhxhxgxgxfxLjEjjjiIiiix),(min .,0,)(kkikxLIi求解无约束问题：其中给定乘子估计)()(-)()(,0 max-)(),(0.)()(kjEjkjkjkiIikikikkkxkxhxhxgxgxfxLx满足得其解 (12.28),(,0 ),(max ,KKT)26.12()()1()(1)(1EjxhIixgkjkjkjkikikik应为乘子修正条件的比较问题 1.,:;(12.28)5.;,|),(min|)(|),(min|)(|44.STOP.,|),(min|)(|3.

21、),(min :2(12.27).:.1);(0,;,0)(3.12)(11-)()(1转步令计算由：步否则则令成立若：步否则转步则得解若：步设其解是题为初始点求解无约束问并以：步构造增广目标函数由：步置精度常数初始罚因子且初始乘子估计选定初始点：步一般约束问题的乘子法算法）（kkxgxhxgxhxxgxhxxLxkIiRRxkkkkkkIkEkIkEkkIkEkkkimnk.,)(.)(min Lagrange 2.2.12选取题：乘子法求解下列约束问用例xxgtsxxxf1)(,max),(LagrangexxxxL函数为解：增广xxxLxxxxxxL),(,1)(),(经计算得06402 0,),()(kkkkxxxL得驻点：令kkkkkx0 ,max 0 ),(max )(从而*)(*01064 ,2 ,xxkkkk时当所以