frank-wolfe算法

《frank-wolfe算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、建模方法与应用主讲人：徐猛北京交通大学交通运输学院建模方法与应用本节课内容：近似线性化和可行下降方向Frank-Wolfe算法建模方法与应用考虑带线性约束的非线性规划问题minf(x)s.t.Axb(1)ExexRnf:RnR1mnln其中，，AR和ER是已知矩阵，mnbR和dR是已知矩阵。记(1)的可行域为nXxRAxb,Exe则(1)式可写作minfx(2)xX本节介绍不断利用(1)的目标函数在迭代处的近似线性化，来构造可行下降方向，从而建立求解(1)的可行方向方法。建模方法与应用1.近似线性化和可行下降方向(k)设(1)或者(

2、2)的目标函数f在可行域X可微，点xX，目标函数f在(k)x处的线性逼近可表示为(k)(k)T(k)fxfxfxxx(k)用上式右边的线性函数来近似代替(2)中的目标函数，则在x的邻域由与(2)式近似的线性规划(k)(k)T(k)minfxfxxxxX或者等价的，有线性规划(k)Tminfxx(3)xX(k)设y是近似线性规划问题(3)的最优解，它与原来的规划问题有如下关系。建模方法与应用n1(k)y(k)定理：设f:RR可微，点xX，如果是近似线性规划问题(3)的最优解，则(k)T(k)(k)(k)(1).当fx

3、yx0时，x是(1)的K-T点；(k)T(k)(k)(k)(k)(k)(2).当fxyx0时，向量pyx是f在点(k)x处关于X的可行下降方向。建模方法与应用2.F-W算法我们可以通过(3)式产生的可行下降方向，来建立一个求解(1)的可行方向法。(k)先选取(1)的一个初始可行点。当已知可行点xX，则借助求解可(k)fx(k)Ty(k)x(k)行线性规划(3),可得其最优解y。如果0，则(k)由定理可知得到(1)式的K-T点。否则，可建立在xX的可行下降方p(k)y(k)x(k)(k)p(k)向。从点x出发，沿方向进行一维线性

4、搜索，即求k，使得(k)(k)(k)(k)fxpminfxpk01(k1)(k)(k)由于X是凸集，过可得下一个迭代点xxkp比仍是(1)的可行点。如此反复迭代，便由可能得到越来越接近(1)的K-T点。建模方法与应用(k)T(k)(k)在实际求解过程中，判断迭代终止的条件fxyx0(k)T(k)(k)fxyx一般用来代替。这一求解线性约束的非线性规划问题是由Frank和Wolfe(1956)提出的，通常称为F-W算法。又由于这一算法每一步采用线性化目标函数的手段，因而也叫近似线性化方法。建模方法与应用F-W法步骤

5、(0)第1步：选取初始数据。取初始可行点求xX，给定终止误差0，令k0，转第2步。第2步：求解近似线性规划。求解线性规划规划(k)TminfxxxX(k)设得到最优解y(k)T(k)(k)第3步：构造可行下降方向。若fxyx，停止迭(k)(k)(k)(k)代输出x；否则，确定可行下降方向pyx，转第4步。建模方法与应用第4步：进行有效一维搜索。求解线搜索问题(k)(k)minfxds.t.01(k1)(k)(k)设得最优解k。令xxkp，kk1,转第2步。从以上求解过程可知，F-W算法把线性约束的非线性规划问题，

6、归为求解一系列线性规划和有效一维搜索。建模方法与应用[例]用F-W算法求解带下面的带线性约束的非线性规划问题。要求(1)T6取初始点x(0,0)，终止误差10。22minf(x)2x2x2xx4x6x121212xx2012x5x5012x10x02建模方法与应用解：第一轮迭代4x12x24fx因为4x2x6214(1)fx故。按(3)式作近似线性规划60Tminf(x)x4x6x12xx2012x5x5012x01x02建模方法与应用T(1)53

7、(1)T(1)(1)可求得它的最优解y。由于fxyx，继续44(1)T(1)(1)(1)迭代，构造x(0,0)点处可行下降方向pyx。从点(1)(1)x出发沿p进行有效一维搜索，即求解(1)(1)19219minfxptt0182得最优解11。于是，下一个迭代点为TT(2)(1)(1)T5353xx1p0014444建模方法与应用第二轮迭代(2)111因为fx，按(3)式作近似线性规划22