Frank-Wolf最优化方法

§1Frank-Wolf方法一、问题形式min()..0fxAxbstx（1.1）其中A为mn矩阵，mbR，nxR。记,0,nDxAxbxxR并设()fx一阶连续可微。二、算法基本思想D是一个凸多面体，任取0xD，将()fx在0x处线性展开000()()()()()TLfxfxfxxxfx用min()..0LfxAxbstx或0min()..0TfxxAxbstx（1.2）逼近原问题，这是一个线性规划问题，设0yD是其最优解。1）若000()()0Tfxyx，则0x也是线性规划问题（1.2）的最优解，此时可证0x为原问题的K-T点。2）若000()()0Tfxyx，则由0y是（1.2）的最优解，故必有0000()()TTfxyfxx从而000()()0Tfxyx即00yx为()fx在0x处的下降方向，沿此方向作有约束的一维搜索00001min(())fxyx设最佳步长因子为0，令100000000()(1)()xxyxyxD当充分小时100000001()min(())(())fxfxyxfxyx00000()()()()()Tfxfxyxofx用1x取代0x，重复以上计算过程。三、算法迭代步骤1）给定初始点0xD，允许误差0，:0k。2）求解线性规划问题min()kTxDfxx，得最优解kyD。3）若()()kTkkfxyx，Stop,*kxx；否则goto4)。4）进行一维搜索01min(())kkkfxyx，得最优步长因子k；令1()kkkkkxxyx，:1kk，goto2)四、算法收敛性定理定理1.1设非线性规划问题（1.1）的最优解存在，且对算法产生的点列{}kx，线性规划问题min()..0kTfxxAxbstx（1.3）的最优解总存在。则1）若迭代到某步0k，有000()()0kkkTfxyx，则0kx为问题（1.1）的K-T点；2）若情形1）总不发生，则算法产生一有界无穷点列{}kx，其任意极限点都是原问题（1.1）的K-T点。证明：若情形1）出现，则0kx也是问题（1.3）的最优解，故0kx满足（1.3）的K-T条件：00000000000()0()000,0,0,kTkTkTkkfxAuvuAxbvxuvxAxb（1.4）而(1.1)的K-T条件：()0()000,0,0,TTTfxAuvuAxbvxuvxAxb（1.5）（1.4）表明0kx，0u，0v一起满足K-T条件（1.5），故0kx是原问题的K-T点。2）由点列{}kx包含在D的极点的凸组合中，而{}ky均为D的极点，故{}kx、{}ky均为有界点列。设x为{}kx的任一极限点，即存在子列{}ikx，使得：limiikkxx注意到点列{}kx满足：1()kkkkkxxyx考虑点列{}iky、{}ik、1{}ikx，不失一般性，设limiikkyy，limiikk，11limiikkxx否则，可以通过反复抽取子序列，使上式对某个子序列成立。由iky是min()ikTxDfxx的最优解，故xD，有()()iiikkkTTfxxfxy且()()0iiikkkTfxyx再由(())(())iiiiiiikkkkkkkfxyxfxyx0,1及1()iiiiikkkkkxxyx取极限，有1()(),()()0(())(())()TTTfxxfxyfxyxfxyxfxyxxxyx（1.6）不等式组（1.6）等价于：011min()()()()0min(())(())()TTxDTfxxfxyfxyxfxyxfxyxxxyx（1.7）若能证明()()0Tfxyx即x为问题min()TxDfxx的最优解，由本定理的第一部分可知，x为原问题K-T点。下证：()()0Tfxyx，若不然，由（1.7）即知必有()()0Tfxyx故yx为x处的下降方向，因而当充分小时，有(())()fxyxfx进而有：1()()fxfx（1.8）但{()}kfx为单调下降的有界序列，故lim()kkfx存在而且lim()lim()()iikkkkfxfxfx11lim()lim()()iikkkkfxfxfx即1()()fxfx与（1.8）矛盾，故必有()()0Tfxyx。基于上述讨论，可以形成如下求解线性二层规划问题(1)的算法。（1）将不等式约束A1x+B1y≤b1，A2x+B2y≤b2，引入松弛变量w’∈Rp和w∈Rq满足：A1x+B1y+w’=b1，A2x+B2y+w=b2，同时将下层问题用K-T条件进行转换得式。（2）取互补松弛条件为罚函数项,得到相应的式。（3）将(2)式中的变量规范化,即令:z=(x1…xn,y1…ym,u1…uq,v1…vm,w’1…w’p,w1…wq)T得到相应的式(5).例题：121230min(,)844404xFxyxxyyys.t.121230min(,)22yfxyxxyyys.t.123112321231220.51220.51yyyxyyyxyyy(1)引入松弛变量同时利用KT条件对下层问题进行转换,取互补松弛条件为罚函数项同时令zx1,x2,y1,y2,y3,u1,u2,u3,v1,v2,v3,w1,w2,w3z1,z2,z3,z4,z5,z6,z7,z8,z9,z10,z11,z12,z13,z14TT则式(1)相应的转换为1234561271381493104115minFz8z4z4z40z4zMzzzzzzzzzzzzs.t.Az=biz0,i1,2,,14式中：A，b为如下的分块矩阵A=00-11100000010020-12-0.5000000110022-1-0.500000010100000-1-10-100000000001200-10000000001-0.5-0.500-1000Tb=[1,1,1,-1,-1,-2]取初始点：Tz(0)=(0.5,0.5,0,0,0,0,1,3,6,0,0,1,0,0)