Frank-Wolfe算法

建模方法与应用建模方法与应用主讲人：徐猛北京交通大学交通运输学院建模方法与应用建模方法与应用本节课内容：近似线性化和可行下降方向Frank-Wolfe算法建模方法与应用考虑带线性约束的非线性规划问题eExbAxx..)(mintsf(1)其中nRx，1:RRnf，nmRA和nlRE是已知矩阵，mRb和nRd是已知矩阵。记(1)的可行域为eExbAxRxX,n则(1)式可写作xXxfmin(2)本节介绍不断利用(1)的目标函数在迭代处的近似线性化，来构造可行下降方向，从而建立求解(1)的可行方向方法。建模方法与应用1.近似线性化和可行下降方向设(1)或者(2)的目标函数f在可行域X可微，点Xx)(k，目标函数f在)(kx处的线性逼近可表示为)()()(kTkkfffxxxxx用上式右边的线性函数来近似代替(2)中的目标函数，则在)(kx的邻域由与(2)式近似的线性规划)()()(minkTkkffxxxxXx或者等价的，有线性规划xxXxTkf)(min(3)设)(ky是近似线性规划问题(3)的最优解，它与原来的规划问题有如下关系。建模方法与应用定理：设1:RRnf可微，点Xx)(k，如果)(ky是近似线性规划问题(3)的最优解，则(1).当0)()()(kkTkfxyx时，)(kx是(1)的K-T点；(2).当0)()()(kkTkfxyx时，向量)()()(kkkxyp是f在点)(kx处关于X的可行下降方向。建模方法与应用2.F-W算法我们可以通过(3)式产生的可行下降方向，来建立一个求解(1)的可行方向法。先选取(1)的一个初始可行点。当已知可行点Xx)(k，则借助求解可行线性规划(3),可得其最优解)(ky。如果0)()()(kkTkfxyx，则由定理可知得到(1)式的K-T点。否则，可建立在Xx)(k的可行下降方向)()()(kkkxyp。从点)(kx出发，沿方向)(kp进行一维线性搜索，即求k，使得)()(10)()(minkkkkkffpxpx由于X是凸集，过可得下一个迭代点)()()1(kkkkpxx比仍是(1)的可行点。如此反复迭代，便由可能得到越来越接近(1)的K-T点。建模方法与应用在实际求解过程中，判断迭代终止的条件0)()()(kkTkfxyx一般用)()()(kkTkfxyx来代替。这一求解线性约束的非线性规划问题是由Frank和Wolfe(1956)提出的，通常称为F-W算法。又由于这一算法每一步采用线性化目标函数的手段，因而也叫近似线性化方法。建模方法与应用F-W法步骤第1步：选取初始数据。取初始可行点求X)0(x，给定终止误差0，令0k，转第2步。第2步：求解近似线性规划。求解线性规划规划xxXxTkf)(min设得到最优解)(ky第3步：构造可行下降方向。若)()()(kkTkfxyx，停止迭代输出)(kx；否则，确定可行下降方向)()()(kkkxyp，转第4步。建模方法与应用第4步：进行有效一维搜索。求解线搜索问题10..min)()(tsfkkdx设得最优解k。令)()()1(kkkkpxx，,1kk转第2步。从以上求解过程可知，F-W算法把线性约束的非线性规划问题，归为求解一系列线性规划和有效一维搜索。建模方法与应用[例]用F-W算法求解带下面的带线性约束的非线性规划问题。要求取初始点T)0,0()1(x，终止误差610。2121222164222)(minxxxxxxfx0005502212121xxxxxx建模方法与应用解：第一轮迭代因为6244241221xxxxfx故64)1(xf。按(3)式作近似线性规划21064)(minxxfTxx0005502212121xxxxxx建模方法与应用可求得它的最优解T4345)1(y。由于)1()1()1(xyxTf，继续迭代，构造T)0,0()1(x点处可行下降方向)1()1()1(xyp。从点)1(x出发沿)1(p进行有效一维搜索，即求解ttf219819min2)1()1(10px得最优解11。于是，下一个迭代点为TTT43454345100)1(1)1()2(pxx建模方法与应用第二轮迭代因为21121)2(xf，按(3)式作近似线性规划21021121)(minxxfTxx0005502212121xxxxxx建模方法与应用可求得它的最优解T10)2(y。由于)2()2()2(xyxTf，继续迭代，构造T4345)2(x点处可行下降方向)2()2()2(xyp。从点)2(x出发沿)2(p进行有效一维搜索，即求解85743831min2)2()2(10ttfpx得最优解3132。于是，下一个迭代点为TTT3124313541453134345)2(2)2()3(pxx建模方法与应用第三轮迭代因为311603132)3(xf，按(3)式作近似线性规划210311603132)(minxxfTxx0005502212121xxxxxx建模方法与应用可求得它的最优解T51)3(y，其中450不唯一。由于0)3()3()3(xyxTf，迭代停止，输出T31243135)3(x。由于这时有0)3()3()3(xyxTf，故由定理可知，)3(x是一个K-T点。又由于上面得非线性规划问题是一个凸规划，可知)3(x是所求问题得最优解。建模方法与应用F-W算法的收敛定理设1:RRnf连续可微，可行集X有界，Xx)0(。若)(kx是由F-W算法求解线性约束的非线性规划问题(1)所产生的点列，则(1).当)(kx是有穷点列时，其最后一个点*x是(1)的K-T点；(2).当)(kx是无穷点列时，它必有极限点，并且其任一极限点Xx*是(1)的K-T点。建模方法与应用F-W算法求解(1)的特点，是通过对目标函数的近似线性化，把问题归为求解一系列辅助得线性规划问题。方法简便，但需要指出，此法的收敛速度较慢。不过，由于所求得各线性规划具有相同的约束条件，因此在有现成的求解线性规划程序的情况下，此法也被人们所采用。非线性规划基础交通分配问题的基本概念Wardrop平衡原则UE配流的数学规划模型UE配流模型的求解算法优化方法建模实例非线性规划基础交通分配问题的基本概念交通量分配就是将已知的O-D需求量按照一定的准则分配到路网中的各条路段上，求出每条路段上的交通流量，以判断各条路段的负荷水平。交通量分配可以为路网规划、设计与决策提供依据。显然，对于这个问题的基本要求就是，所得到的路段交通量应该最大限度的符合实际交通情况。事实上，交通网络上形成的交通量分布是由两种机制相互作用直至平衡的结果，一方面，网络用户（各种车辆）试图通过选择最佳行驶路线来达到费用最少的目的；另一方面，网络用户遇到的阻抗（即广义费用）与系统被使用的情况密切相关，道路上的车流量越大，对应的行驶费用就越高。两种机制的交叉作用使我们难以找出节点与节点之间最佳行驶路线的位置分布与最后导致的流量分布结果。我们可以运用数学工具模拟这两种机制，并估计交通网络上交通流量的合理分布（即平衡状态下的分布）。非线性规划基础符号介绍N：交通网络中节点的集合。A：交通网络中路段的集合。I：产生交通量的起始节点的集合，NI。J：吸引交通量的终讫节点的集合，NJ。i：表示一个起始节点，Ii。j：表示一个终讫节点，Jj。ijK：连接O-D对ji的所有路径的集合。ijq：在所研究的时段内从i到j的交通流量。q：O-D需求量列向量Tijq),,(，Ii，Jj。ijkh：O-D对ji之间的第k条路径上的流量，ijKk。非线性规划基础符号介绍ijh：列向量Tijkh),,(，ijKk。h：列向量TTij),)(,(h，Ii，Jj。ijkc：O-D对ji之间的第k条路径上的费用，ijKk。ijc：列向量Tijkc),,(，ijKk。c：向量TTij),)(,(c，Ii，Jj。af：路段a上的交通流量，Aa。f：列向量Taf),,(，Aa。ac：路段a上的费用，Aa。c：列向量Tac),,(，Aa。ijka,：如果路段a在连接O-D对ji的第k条路径上，其值为1，否则为0。ijΔ：矩阵[ijka,]，Aa，ijKk。Δ：矩阵向量（,,ijΔ），Ii，Jj。非线性规划基础符号介绍关于路段与路径之间的流量和费用，有如下关系：kijkaijkjiahf,，a（3-1）aijkaaijkcc,，k，ji,（3-2）这两个方程描述了路径/路段的关联关系，而ijΔ称为O-D对ji的关联矩阵。更简明一点，可以用矩阵来表达上面的关联关系：cΔcT，Δhf注：出行费用有时也称为道路阻抗，交通网络中的路段也可以称为弧。非线性规划基础符号介绍例：如图3.1所示，网络中有两个起点和一个终点。从节点a到节点d有两条路经，即1-3和1-4；从节点b到节点d也有两条路经，即2-3和2-4。a13dc2b4图3.1简例因为路段1在从a到d的第一条路径和第二条路径上，所以11,1ad，12,1ad，但不在从b到d的任何路径上，故01,1bd，02,1bd。我们可以得到如下的关联矩阵:非线性规划基础符号介绍表3-1O-D（a-d）O-D（b-d）路径路段121211100200113101040101可以写出路段流量与路径流量之间的相互关系，如：bdadbdbdbdbdadadadadhhhhhhf112,321,312,321,313以及路径费用与路段费用之间的关系，如：311,441,331,221,111cccccccadadadadad非线性规划基础Wardrop平衡原则进行城市交通网络规划时，如何将O-D需求量分配到交通网络的各条路段上去，这是几十年来许多研究学者苦苦思考的问题。人们早就认识到：所需出行时间、距离及费用等是选择路线的重要基准，但在早期由于缺乏系统理论和计算手段，不得不依靠实际作业者的个人经验和判断。进入50年代后，美国BPR(BureauofPublicRoads)和HRB(HighwayResearchBoard)在研究高速道路交通转移率时提出了转移率曲线方法，这可以说是交通量分配理论系统发展的最初尝试。1957年Moore和Dantzing发表了寻找网络中两点间最短路方法的论文，这一成果对交通量分配理论的发展产生了很大的影响。经过Carroll、Schneider等人的努力，50年代后期建立在最短路方法基础上的“全有全无”法(All-or-Nothing)在交通量分配中得到了实际应用。非线性规划基础Wardrop平衡原则•为体现拥挤效应，车辆在路段上的行驶时间（阻抗）是路段交通流量的增函数。•最著名的关于路径选择的理论就是用户均衡（UE）原则，由Wardrop在1952年提出。–在均衡态，同一OD对之间所有被使用的路径的阻抗是相等的，并且不大于任何未被使用路径的阻抗，没有人能够通过单方面改变自己的路径来达到降低自己阻抗的目的。–“thejourneyti