Frank-Wolfe演算法計算效率再提昇:以交通網路均衡指派為例

Abstract

Frank-Wolfe 演算法是凸形非線性規劃問題(convex nonlinear programming pro- blem) 的解法之一，而在求解交通網路的均衡指派問題時，一般也是使用 Frank- Wolfe 演算法。此演算法的主要缺點是收斂速度太慢，針對此缺點，在過去已有 Fukushima(1984)、LeBlanc(1985)，以及Weintraub(1985) 等人修改此演算法，本 研究認為其中仍有很大發展空間，因此將研究作進一步的改善。本研究將在收斂條 件的要求更嚴格的考慮下，從以下兩方面著手，更進一步地提昇Frank-Wolfe 演算 法的計算效率： (1) 對Fukushima 的方法做完整的分析，找出更適合的策略。 (2) 結合Weintraub 與Fukushima 二者的不同改善方法。 最後，將以電腦測試求解網路交通量指派問題，以顯示本研究提出之改善策略所提 昇的計算效率。