Frank-Wolfe算法.pdf

建模方法与应用建模方法与应用 主讲人：徐猛 北京交通大学交通运输学院 建模方法与应用 本节课内容： 近似线性化和可行下降方向 Frank- Wolfe算法 建模方法与应用 考虑带线性约束的非线性规划问题 min f (x ) s.t. Ax b (1) Ex e x Rn f : R n R 1 A Rmn E Rl n 其中 ， ， 和 是已知矩阵， b Rm 和 d Rn 是 已 知 矩 阵 。 记 (1) 的 可 行 域 为  n  X x R Ax b, Ex e 则(1)式可写作   min f x (2) x X 本节介绍不断利用(1)的目标函数在迭代处的近似线性化，来构造可行下降 方向，从而建立求解(1)的可行方向方法。 建模方法与应用 1. 近似线性化和可行下降方向 f X x (k ) X f 设(1)或者(2)的目标函数 在可行域 可微，点 ，目标函数 在 (k ) x 处的线性逼近可表示为   (k ) (k ) T (k )       f x f x f x x x (k ) 用上式右边的线性函数来近似代替(2) 中的目标函数，则在x 的邻域由 与(2)式近似的线性规划 (k ) (k ) T (k )       min f x f x x x x X 或者等价的，有线性规划 (k ) T   min f x x (3) x X (k ) y 设 是近似线性规划问题(3)的最优解，它与原来的规划问题有如下关系。