约束最优化方法学习教案

1、会计学1约束约束(yush)最优化方法最优化方法第一页，共42页。(fgh)(fh)即第1页/共42页第二页，共42页。分量形式：ljjjxhxf1*0)()(0)()(*xxhxf第2页/共42页第三页，共42页。-f( ) h( )h(x)-f(x*)h(x*)这里 x* -l.opt. f(x*)与h(x*) 共线，而非l.opt.f( )与h( )不共线。hjjjxhxf1*)(*)(第3页/共42页第四页，共42页。(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1为起作用约束第4页/共42页第五页，共42页。g( )-f( )X*-f(x*)g(x*)第5页/共42

2、页第六页，共42页。点。称条件的点满足互补松弛条件。那么，可微，如果在TKxTKmixgumiuxguxfixgxxguxfiiimiiiiIiii*1*)(,2, 10)(,2, 100)()()(,0)()(第6页/共42页第七页，共42页。0),(0),(042),(05),(.)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T第7页/共42页第八页，共42页。0)()()()2,2()2(2),3(2(

3、)()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第8页/共42页第九页，共42页。0)(,2,1,00)()(xgumiuxguxfiiimiii个未知量个方程66)6(0)5(0)4(0)42()3(0)5(0,)2(022)2(2)1(02)3(224132122221143214221232111xuxuxxuxx

4、uuuuuuuxuxuuxux第9页/共42页第十页，共42页。点。是故得TKxuuuxuxuxuxT)1 , 2(032,31022)2(202)3(22122122111第10页/共42页第十一页，共42页。点。故不是不满足点；故不是得交点：与TKgSTKSxxxxggTTT,0,)5,0(,)5,0()5,0(00521222131.04, 060)20(20)30(204, 3)0 , 0(:,43432143点故非得解故交点TKuuuuuuISxggT第11页/共42页第十二页，共42页。034. 04742),(),(0502)2(202)3(20,10)()(1351320134

5、52121320134522211221114321xxgTKSxxuxxuxxuuuIxgxf点故均不是得解则相切的情况：与目标函数第12页/共42页第十三页，共42页。线性无关。，向量组约束规格）。（的某邻域内连续可微。在）（，连续，在可微在设为起作用集。，问题定理：)(,),(,),)(, 2 , 1)(,)(,0)(, 0)(|)(, 2 , 10)(, 2 , 10)(. .)(min)(1xhxhIixgCQxljhxIixgxIixgIxhxgxSxfghljxhmixgt sxffghlijiiji第13页/共42页第十四页，共42页。点。是则及为凸规划，满足可微性若亦可微，那

6、么在如果还有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiiiiljjjIiiiji.)(,2, 10)(00)()()()(0)()()(,2, 1,0.111第14页/共42页第十五页，共42页。为既约梯度称相应非基变量基变量，使非奇异，存在分解：、既约梯度及搜索方向）个正分量。（的每个极点都有列线性无关；的任意、非退化假设：的多面体同可行集：秩）、问题：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11

7、)()(,)()()(0, 0,30212.)(0,|,0. .)(min1第15页/共42页第十六页，共42页。为可行方向。故即有）时，（则取由故又）时，（当为可行方向，即时当为可行方向寻找下降可行方向：dSdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.000|min.)(,0,0.0,00,0,)(0,0:.0,00)1(第16页/共42页第十七页，共42页。0)()()()()()()(0)(:)2(0, 00.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfd

8、xfdxfdxfdNdBddxddNdBdNdBdddNBAdddd分解：要求下降方向及中，对应可行，可取在故要使得到根据考虑分解第17页/共42页第十八页，共42页。点。若的下降可行方向；为若那么方向定理：按上述方案产生的分量。为其中：时当时当的方案向的一种产生下降可行方、结合TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN02)(, 01,00:)2() 1 ()3(1第18页/共42页第十九页，共42页。证毕。非零，于是或至少一个由于又保证故总有对.0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjjjdrrxrdrrx

9、rrdrdrdrAdNdBddrxdrrdrxproof第19页/共42页第二十页，共42页。得证。即条件：可得取故时，当原因：则取矛盾；与那么，反证。若存在可得000)()(0)()(0)(,)(); 0000, 0, 0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxfTKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN第20页/共42页第二十一页，共42页。证毕。也就是即故恒有时当时当，即由第三式得：由第一式得：点即.00, 0, 000000000, 0)()(0)()

10、(0)(000)(111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT第21页/共42页第二十二页，共42页。x(1)S, k=1k=k+1Jk=j|xj为x(k)中最大m个正分量(fn ling)之一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. .)(

11、min)(t sdxfk0,0,0|/min)(ddddxjjkj否则当第22页/共42页第二十三页，共42页。.,:,:0)(. .)(min0,552. .32min.21212121212221babaRbaRRhRRfbxaxhtsxfPGRGxxxxxxtsxxxxxxExnlnn，且的分量允许连续可微。其中：）（标准形式）二、广义既约梯度法（见书（略）第23页/共42页第二十四页，共42页。TTTyTzTzyyzyzylnlzxhyxhxfxfryxhbyabbbaaaRzRyzyxSxbxaxhxS)()()()()(2,1,0)(|1广义既约梯度：非奇异使记使分解非退化假设：记

12、第24页/共42页第二十五页，共42页。点。时为下降可行方向；当同样有结论：或且或且令取方向：TKxdddzxhyxhdJirJidrbzraziJzTTyiziziziiizii0201)()(0)(0)(0)(|0)(|1第25页/共42页第二十六页，共42页。0)(0)()()()(:0)(:0)(.:)(min)(.1)(11xxxxxhxgxRRhxhRRgxgtsRRfxffghTechniqueonMinimizatinedUnconstraiSequentialSUMTljjmiilnmnn有不满足约束的有目的：使满足约束的构造罚函数：罚函数概念：序列无约束最优化方法第26页/

13、共42页第二十七页，共42页。)2.(22|)(, 0max)()(),()()(min)()(0)(, 0000,0)(000,0)(次是最低次的光滑函数常用：因次罚函数时，称当为正整数。的典型取法：辅助问题辅助函数不可行可行惩罚项可构造取时当时当时当时当其中：ppttttttxxfxxfxttttttpp第27页/共42页第二十八页，共42页。.22),(,22214),(,22,2,4) 14()2()()(),(:2)()()(min,2, 02,)2(2, 0max)(:02. .min.2222optxxxgxxxgxxxxxxxxxxfxgxxfxxfxxxxxxtsxEx 故的

14、最小值点时当的驻点时当辅助函数解析解时当如图二次罚函数第28页/共42页第二十九页，共42页。第29页/共42页第三十页，共42页。的单调非增函数关于的单调非降函数；关于）（则）（使：，再设为罚函数，连续。连续，引理：设下确界）（定义：0)(0)(),(20|sup| )(inf1)()(,0)(,)()(infxxfSxxfxxfDxxhgfxxfxx第30页/共42页第三十一页，共42页。.,0)(00)(.2)(lim0| )(sup| )(inf1.0,0)(,0)(|),()(21optxxoptxSxxfxxxhxgxSfghxkkkk 则使若推论：在定理条件下，且那么，有即单调增

15、加的正数列在引理假设下，设存在定理：第31页/共42页第三十二页，共42页。初始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第37页/共42页第三十八页，共42页。转置否则停，说明若；转为初始内点，得到解以用闸函数法求解：；转使否则，取为初始内点。则若令；转求初始内点：2, 1.,0)(44,0)(.)(min33|)(max)(,0)(|22, 1,10)1()1()()()()()()1(kkSxgxxIixgtsxgIixgxgjxIxgiIkxkjkkkijkkikjkkkik第38页/共42页第三十九页，共42页。: )(:0)(. .:)(min)(xfLagrangeRDDxRRhxhtsRRfxffhDnlnn函数代替用约束构成。是一个集合，常由简单第39页/共42页第四十页，共42页。及调整否则及乘子得到解若得到求解为罚因子。为乘子，其中：乘子罚函数：