资源描述：
《最优化理论与算法(第十一章)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第十一章约束最优化问题的可行方向法§1Frank-Wolf方法一、问题形式min/(%)Ax>b(11.1)s.t.<{x>0其中4为mxn矩阵，/川Rm，xeRn。记D二仝么又之0，xe/?"}并设/(又)一阶连续可微。二、算法基本思想£>是一个凸多面体，任取xQeZ)，将/(%)在xQ处线性展开/(X)«/(x°)+V/(x°)T(x-x°)=A(x)minfL(x)minV/(x0)rx[Ax>b或[Ax>b(11.2)s.t.0{x>Q逼近原问题，这是一个线性规划问题，是其最优解。1)若V/(xQ/(/-xQ)=0,则W也是线性规划
2、问题(11.2)的最优解，此时可证？为原问题的K-T点。2)若▽/('/(/—xG)*0,则由/是(11.2)的最优解，故必有▽/(WyW/CvW从而WW-W),允许误差
3、£〉0,1=0。2）求解线性规划问题minW/x,得最优解/e£>。xeD3）^]^f（xk）T（yk—xk）Stop,x-xk:否则goto4）。4）进行一维搜索min/（分+2（/’-/'））,得最优步长因子/I%0<2<1^xM«xk+Ak（yk-xk）fk-k+,goto2）四、算法收敛性定理定理11.1设非线性规划问题（11.1）的最优解存在，且对算法产生的点列线性规划问题min[Ax>b（11.3）s.t.<{x>0的最优解总存在。则1）若迭代到某步有-妙）=0,则/°为问题（li.i）的k-t点；2）若情形1）总不发生，则算法产生一有界无穷点列
4、{•?},其任意极限点都是原问题（11.1）的K-T点。证明：若惜形1）出现，则;^也是问题（11.3）的最优解，故;^满足（11.3）的K-T条件：▽，（？”-AV-v（）=0uqt（Ax^-b）=Q（11.4）v0Txk°=0w°>0,v°>0,x^>0,>bY,W--v=0(11.5)uT(Ax-b)=OvTx=On>0,v>0,x>0,Ar>/?(11.4)表明,«n,vQ—起满足K-T条件(11.5),故/'°是原问题的K-T点。2)由点列包含在£＞的极点的凸组合巾，而｛/｝均为D的极点，故均为有界点列。设为的任一极限点，即存在子列使得：limxk
5、,=x°°注意到点列｛/J满足：考虑点列｛/｝、｛，'｝、｛?*+,｝,不失一般性，设lim/=，，lim劝=/T,limx^+1=，+1A,—＞OOki-々'一＞00否则，可以通过反复抽取子序列，使上式对某个子序列成立。由/;是1^117；^/*的駁优解,xeD故Vxe£),有且再由及収极限，有▽/Wpv/W/WW-，)/(分+妙(/-分))VAe[0,1]▽，(r)7’x>v/(x°°)5r,v/(%°°)r(，一r)so/(x°°-x00))(11.6)00+1OO1oo/oooox=
6、x^/L(y-x)不等式组(11.6)等价于:minV/(r/xxeD▽/(r)VV/(x^)r(y°°-r)<0minZ(r+A(r-r))=+/T(，-r))%°°+,=x^+r(yw-x°o)(11.7)若能证明即；r为问题minV/(r)rxeD的最优解，由本定理的第一部分可知，为原问题k-t点。下证：v/cr/Gr—z°)=o,若不然，由(11.7)即知必有故一;r为；r处的下降方向，因而当a充分小时，有/(r+A(r-rw)进而有：/^+，)00而且limf
7、(xk)=limf(xki)=/(xTO)A;-lim/(?)=lim，(xvl)=，(，+1)々—>oo>oo即=W)与(ii.8)矛盾，故必有▽/(z°/(/°-；r)=o。§2Rosen的梯度投影法一、问题形式min/(%)[a]x=biZ=l，…，(11.9)Ti[a(x>bji=%+1，…，”2二、算法基本思想该算法的基本思想是将无约束的最速下降算法推广到有约束情形1）若当前迭代点分位于约束域内部，此时负梯度方向为可行下降方向；2）若xM立于约朿域边界上，情况就不同了，此时应将负梯度方向向可行域内部投影，以保证方向是可行下降方向。设分是当前迭代点（
8、可行点），-V/C?）显然是下降方向，
