约束最优化方法课件.ppt

1、约束最优化方法约束最优化方法 问题问题 min f(x)s.t.g(x)0 分量形式略分量形式略 h(x)=0 约束集约束集 S=x|g(x)0,h(x)=0 1 Kuhn-Tucker 条件条件一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：考虑考虑 min f(x)s.t.h(x)=0 回顾高等数学中所学的条件极值：回顾高等数学中所学的条件极值：问题问题 求求z=f(x,y)极值极值 min f(x,y)在在(x,y)=0的条件下。的条件下。S.t.(x,y)=0 引入引入Lagrange乘子：乘子：Lagrange函数函数 L(x,y;)=f(x,y)+(x,y)(fgh

2、)(fh)即一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(续续)若若(x*,y*)是条件极值，则存在是条件极值，则存在*，使，使 fx(x*,y*)+*x(x*,y*)=0 fy(x*,y*)+*y(x*,y*)=0 (x*,y*)=0 推广到多元情况，可得到对于推广到多元情况，可得到对于(fh)的情况：的情况：min f(x)s.t.hj(x)=0 j=1,2,l 若若x*是是(fh)的的l.opt.,则存在则存在*Rl使使 矩阵形式：矩阵形式：分量形式：ljjjxhxf1*0)()(0)()(*xxhxf一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(

3、续续)几何意义是明显的：考虑一个约束的情况：几何意义是明显的：考虑一个约束的情况：最优性条件即：最优性条件即：-f()h()h(x)-f(x*)h(x*)这里 x*-l.opt.f(x*)与h(x*)共线，而非l.opt.f()与h()不共线。hjjjxhxf1*)(*)(二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：考虑问题考虑问题 min f(x)s.t.gi(x)0 i=1,2,m 设设 x*S=x|gi(x)0 i=1,2,m 令令 I=i|gi(x*)=0 i=1,2,m 称称I为为 x*点处的起作用集（紧约束集）。点处的起作用集（紧约束集）。如果如果x*

4、是是l.opt.,对每一个约束函数来说，只有当它是起作用约对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：束时，才产生影响，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0,g1为起作用约束二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）特别特别 有如下特征：如图有如下特征：如图 在在x*：f(x*)+u*g(x*)=0 u*0 要使函数值下降，必须使要使函数值下降，必须使g(x)值变大，则值变大，则 在在 点使点使f(x)下降的方向（下降的方向（-f()方向）指向约束集合内方向）指向约束集合内部，因此部，因此不是不是l.opt

5、.l.opt.。g()-f()X*-f(x*)g(x*)二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）定理（最优性必要条件）：定理（最优性必要条件）：（K-T条件）条件）问题问题(fg),设设S=x|gi(x)0,x*S,I为为x*点处的起作用集，设点处的起作用集，设f,gi(x),i I在在x*点可微，点可微，gi(x),i I在在x*点连续。点连续。向量组向量组gi(x*),i I线性无关。线性无关。如果如果x*-l.opt.那么，那么，u*i0,i I使使点。称条件的点满足互补松弛条件。那么，可微，如果在TKxTKmixgumiuxguxfixgx

6、xguxfiiimiiiiIiii*1*)(,2,10)(,2,100)()()(,0)()(二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）0),(0),(042),(05),(.)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）用用K-T条件求解：条件求解：0)()()()2,2()2

7、(2),3(2()()2,1()()2,4()2,2()(2,1120),(0),(232131*32*231*1*2*1*2211212211*xgxgxfuuxxxfxgxxxgIxxgxxgxTTTTTT使计算可得起作用集），交点（点在 10,01)(21)2(,22)(,)2(2)3(2)(43221121gxggxxxgxxxf二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）0)(,2,1,00)()(xgumiuxguxfiiimiii个未知量个方程66)6(0)5(0)4(0)42()3(0)5(0,)2(022)2(2)1(02)3(224

8、132122221143214221232111xuxuxxuxxuuuuuuuxuxuuxux二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）可能的可能的K-T点出现在下列情况：点出现在下列情况：两约束曲线的交点：两约束曲线的交点：g1与与g2,g1与与g3,g1与与g4,g2与与g3,g2与与g4,g3与与g4。目标函数与一条曲线相交的情况：目标函数与一条曲线相交的情况：g1，g2,g3,g4 对每一个情况求得满足对每一个情况求得满足(1)(6)的点的点(x1,x2)T及乘子及乘子u1,u2,u3,u4,验验证当满足可得，且证当满足可得，且ui 0时，

9、即为一个时，即为一个K-T点。点。下面举几个情况：下面举几个情况：g1与与g2交点：交点：x=(2,1)TS,I=1,2 则则u3=u4=0 解解点。是故得TKxuuuxuxuxuxT)1,2(032,31022)2(202)3(22122122111二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）点。故不是不满足点；故不是得交点：与TKgSTKSxxxxggTTT,0,)5,0(,)5,0()5,0(00521222131.04,060)20(20)30(204,3)0,0(:,43432143点故非得解故交点TKuuuuuuISxggT二、不等式约束问

10、题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）034.04742),(),(0502)2(202)3(20,10)()(135132013452121320134522211221114321xxgTKSxxuxxuxxuuuIxgxf点故均不是得解则相切的情况：与目标函数三、一般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件线性无关。，向量组约束规格）。（的某邻域内连续可微。在）（，连续，在可微在设为起作用集。，问题定理：)(,),(,),)(,2,1)(,)(,0)(,0)(|)(,2,10)(,2,10)(.)(min)(1xhxhIixgCQxlj

11、hxIixgxIixgIxhxgxSxfghljxhmixgt sxffghlijiiji三、一般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件(续续)点。是则及为凸规划，满足可微性若亦可微，那么在如果还有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiiiiljjjIiiiji.)(,2,10)(00)()()()(0)()()(,2,1,0.111一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法为既约梯度称相应非基变量基变量，使非奇异，存在分解：、既约梯度及搜索方向）个正分量。（的每

12、个极点都有列线性无关；的任意、非退化假设：的多面体同可行集：秩）、问题：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11)()(,)()()(0,0,30212.)(0,|,0.)(min1一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）为可行方向。故即有）时，（则取由故又）时，（当为可行方向，即时当为可行方向寻找下降可行方向：dSdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.000|min.)(,0,0.0

13、,00,0,)(0,0:.0,00)1(一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）0)()()()()()()(0)(:)2(0,00.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfdxfdxfdxfdNdBddxddNdBdNdBdddNBAdddd分解：要求下降方向及中，对应可行，可取在故要使得到根据考虑分解一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）点。若的下降可行方向；为若那么方向定理：按上述方案产生的分量。为其中：时当时当的方案向的一种产生下降可行方、结合

14、TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN02)(,01,00:)2()1()3(1一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）证毕。非零，于是或至少一个由于又保证故总有对.0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjjjdrrxrdrrxrrdrdrdrAdNdBddrxdrrdrxproof得证。即条件：可得取故时，当原因：则取矛盾；与那么，反证。若存在可得000)()(0)()(0)(,)();0000,0,0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxf

15、TKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）证毕。也就是即故恒有时当时当，即由第三式得：由第一式得：点即.00,0,000000000,0)()(0)()(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT算法：算法：x(1)S,k=1k=k+1

16、Jk=j|xj为x(k)中最大m个正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)-BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T点 0,0,jjjjjjrrxrrd当当0.)(min)(t sdxfk0,0,0|/min)(ddddxjjkj否则当一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）.,:,:0)(.)(min0,552.32min.21212121212221babaRbaRRhRRfbxaxhtsxfPGRGxxxxxxtsxxxxxxExnlnn，且的分

17、量允许连续可微。其中：）（标准形式）二、广义既约梯度法（见书（略）二、广义既约梯度法二、广义既约梯度法（续）（续）TTTyTzTzyyzyzylnlzxhyxhxfxfryxhbyabbbaaaRzRyzyxSxbxaxhxS)()()()()(2,1,0)(|1广义既约梯度：非奇异使记使分解非退化假设：记二、广义既约梯度法二、广义既约梯度法（续）（续）点。时为下降可行方向；当同样有结论：或且或且令取方向：TKxdddzxhyxhdJirJidrbzraziJzTTyiziziziiizii0201)()(0)(0)(0)(|0)(|10)(0)()()()(:0)(:0)(.:)(min)(

18、.1)(11xxxxxhxgxRRhxhRRgxgtsRRfxffghTechniqueonMinimizatinedUnconstraiSequentialSUMTljjmiilnmnn有不满足约束的有目的：使满足约束的构造罚函数：罚函数概念：序列无约束最优化方法)2.(22|)(,0max)()(),()()(min)()(0)(,0000,0)(000,0)(次是最低次的光滑函数常用：因次罚函数时，称当为正整数。的典型取法：辅助问题辅助函数不可行可行惩罚项可构造取时当时当时当时当其中：ppttttttxxfxxfxttttttpp.22),(,22214),(,22,2,4)14()2(

19、)()(),(:2)()()(min,2,02,)2(2,0max)(:02.min.2222optxxxgxxxgxxxxxxxxxxfxgxxfxxfxxxxxxtsxEx 故的最小值点时当的驻点时当辅助函数解析解时当如图二次罚函数2.罚函数法罚函数法：（fgh）的单调非增函数关于的单调非降函数；关于）（则）（使：，再设为罚函数，连续。连续，引理：设下确界）（定义：0)(0)(),(20|sup|)(inf1)()(,0)(,)()(infxxfSxxfxxfDxxhgfxxfxx2.罚函数法罚函数法：（续）（续）.,0)(00)(.2)(lim0|)(sup|)(inf1.0,0)(,0

20、)(|),()(21optxxoptxSxxfxxxhxgxSfghxkkkk 则使若推论：在定理条件下，且那么，有即单调增加的正数列在引理假设下，设存在定理：算法：算法：初始x(1),10,1,0,k=1以x(k)为初始点，解min f(x)+(x)得到，x(k+1)k(x(k+1)0,0,1,0,k=1min f(x)+k B(x)s.t.x S0从x(k）出发，求得，x(k+1)k B(x(k+1)yes停；x(k+1)解Nok+1=k k=k+1。转置否则停，说明若；转为初始内点，得到解以用闸函数法求解：；转使否则，取为初始内点。则若令；转求初始内点：2,1.,0)(44,0)(.)(

21、min33|)(max)(,0)(|22,1,10)1()1()()()()()()1(kkSxgxxIixgtsxgIixgxgjxIxgiIkxkjkkkijkkikjkkkik4.罚函数法与闸函数法的缺点：罚函数法与闸函数法的缺点：1当罚函数法（闸函数法）的当罚函数法（闸函数法）的 （0+）时，惩罚项时，惩罚项 +0或或0+形式，在计算上有困难；形式，在计算上有困难；2计算一系列无约束问题，故计算量大。计算一系列无约束问题，故计算量大。5.乘子法：乘子法：:)(:0)(.:)(min)(xfLagrangeRDDxRRhxhtsRRfxffhDnlnn函数代替用约束构成。是一个集合，常由简单5.乘子法：乘子法：（续）（续）。及调整否则及乘子得到解若得到求解为罚因子。为乘子，其中：乘子罚函数：)()()()1()1()1()()(121;0)(,2,1,0,.),(min)()()(),(kkkkkkkkllliiiliiivvxxhkxDxtsvxRRvxhxhvxfvx0,|0)(0)(.)(min0)(0)(.)(min)(.),(minzDxzxDxxhzxgtsxfDxxhxgtsxffghDDxtsvxv引入松弛变量一般问题：解。的最优解，即原问题的存在时，当存在可以证明：