下载文档原格式
Frank-Wolfe算法求解交通分配问题：比较不同流量更新策略和线搜索技术徐猛;屈云超;高自友【期刊名称】《交通运输系统工程与信息》【年(卷),期】2008(008)003【摘要】Frank-Wolfe(FW)算法是一类广泛应用于求解交通分配问题的算法.它具有容易编程实现,所需内存少的特点.但是该算法收敛速度较慢,不能得到路径信息.为了提高算法的效率,本文研究三种流量更新策略(all-at-once,one-origin-at-a-time,one-OD-at-a-time)以及不同的步长搜索策略下的FW算法,其中步长搜索策略包括精确线性搜索方法(包括二分法、黄金分割法、成功失败法)和不精确的线性搜索方法(包括基于Wolfe-Powell收敛准则的搜索方法和Gao等提出的非单调线性搜索方法).最后,本文将上述策略应用于四种不同规模的交通网络中,并给出较适合求解的组合.【总页数】9页(P14-22)【作者】徐猛;屈云超;高自友【作者单位】北京交通大学交通运输学院系统科学所,北京,100044;北京交通大学交通运输学院系统科学所,北京,100044;北京交通大学轨道交通控制与安全国家重点实验室,北京,100044【正文语种】中文【中图分类】U491【相关文献】1.求解二级线性价格控制问题的Frank-Wolfe算法 [J], 徐裕生;陈诚;史向平2.求解二级线性价格控制问题的Frank-Wolfe算法 [J], 徐裕生;陈诚;史向平3.用于求解路径交通流量的改进Frank-Wolfe算法 [J], 柴获;何瑞春;马昌喜;代存杰4.基于Frank-Wolfe算法的交通分配研究 [J], 郑晏群;张鹍鹏5.一类求解非线性约束优化问题的线搜索渐缩滤子算法 [J], 裴永刚;孔维悦;董兰婷因版权原因，仅展示原文概要，查看原文内容请购买。
Wolfe线性搜索下的超记忆梯度法及其收敛性汤京永;董丽【摘要】研究无约束优化问题, 给出了一种新的超记忆梯度法, 在较弱条件下证明了算法具有全局收敛性和线性收敛速率. 数值试验表明新算法是有效的.【期刊名称】《吉林大学学报（理学版）》【年(卷),期】2010(048)003【总页数】5页(P396-400)【关键词】无约束优化;超记忆梯度法;全局收敛性;线性收敛速率【作者】汤京永;董丽【作者单位】信阳师范学院,数学与信息科学学院,河南,信阳,464000;上海交通大学,数学系,上海,200240;信阳师范学院,数学与信息科学学院,河南,信阳,464000【正文语种】中文【中图分类】O221.21 引言考虑无约束优化问题min f(x), x∈Rn,(1.1)其中: Rn是n维欧氏空间; f(x): Rn→R为连续可微函数. 本文设f(x)的梯度函数为g(x), 若xk为当前迭代点, 则g(xk)简记为gk, f(xk)简记为fk, f(x*)简记为f *.求解问题(1.1)的算法主要是迭代法, 基本格式为xk+1=xk+αkdk,(1.2)这里dk为f(x)在xk点的下降方向, αk为f(x)沿该方向的搜索步长. 对αk和dk的不同选择构成了不同的迭代法[1].对于dk, 可采用dk=-gk, 此种算法称为最速下降法[1]. 此类算法虽然结构简单, 每次迭代的计算量小, 但收敛速度慢且容易产生拉锯现象. 若f(x)二次连续可微, 则可采用dk=-Hkgk, 其中Hk为▽2f(xk)-1或▽2f(xk)-1的某种近似, 此种算法称为拟牛顿法[1]. 拟牛顿法虽然在一定条件下有较快的收敛速度, 但每次迭代时都需要计算和存储矩阵, 不适于求解大型优化问题. 上述两种算法在每步迭代时仅利用当前点的信息产生下一个迭代点, 而忽略了前面迭代点的信息, 这在算法设计中是一种信息浪费.共轭梯度法在每次迭代时通过记忆前一步的迭代信息产生下一个迭代点, 搜索方向的基本结构为其中βk是一个参数, 当βk用不同的公式时即得到了不同的共轭梯度法[1-2]. 此类算法有效避免了计算和存储矩阵, 是求解大型优化问题的有效方法之一, 但很多共轭梯度法不具有全局收敛性[2-3].为了充分利用前面迭代点的信息, 以改进算法的性能, 保证算法具有全局收敛性, 文献[4]提出了记忆梯度法[4]. 记忆梯度法是共轭梯度法的推广, 在每步迭代时同样不需计算和存储矩阵, 算法简单, 因而适于求解大型优化问题, 且与共轭梯度法相比, 此类算法增加了参数选择的自由度, 更有利于构造稳定的快速收敛算法[5-7]. 但很多记忆梯度法仅利用前一步的迭代信息, 同样忽略了前面迭代点的信息. 文献[8]提出一种超记忆梯度法, 算法在每步都能充分利用前面多步迭代点的信息, 并且具有全局收敛性.本文提出一种新的求解无约束优化问题的超记忆梯度法, 算法在每步迭代时都充分利用前面多步迭代点的信息产生下降方向, 采用Wolfe线性搜索产生步长, 在较弱条件下证明了算法具有全局收敛性. 当目标函数为一致凸函数时, 证明了算法具有线性收敛速率. 数值试验表明算法是有效的.2 超记忆梯度法及其性质假设:(H1) 目标函数f(x)在水平集L0={x∈Rn|f(x) ≤f(x1)}上有下界;(H2) 梯度函数g(x)在包含L0的开凸集B上一致连续;(H3) f(x)是二次连续可微的一致凸函数.算法2.1 ρ∈(0,1), 0<σ1<σ2<1, m>0是一个整数, x1∈Rn. 令k ∶=1.步骤如下:(1) 若‖gk‖=0, 则停止迭代; 否则, 转(2);(2) 计算dk, 使其满足:(2.1)其中(2.2)(3) xk+1=xk+αkdk, 其中αk由Wolfe线性搜索确定, 即要求αk满足:(2.3)(2.4)(4) 令k ∶=k+1, 转(1).引理2.1 对任意的k≥1, 有注2.1 由引理2.1及式(2.3)可知{fk}单调不增, 即fk≤fk-1≤…≤f1, 从而知xk∈L0.引理2.2 对任意的k≥1, 有‖dk‖≤(1+ρ)‖gk‖.3 算法的全局收敛性定理3.1 假设(H1)和(H2)成立, {xk}是由新算法产生的迭代点列, 则证明: 首先证明{‖dk‖}有界. 由引理2.2知, 只需证明{‖gk‖}有界. 假设{‖gk‖}无界, 则存在无穷子列N⊂{1,2,…,}, 使得‖gk‖→+∞, k∈N, k→+∞.(3.1)由式(2.3)和引理2.2知(3.2)因为{fk}单调不增且有下界, 故知{fk}有极限, 从而由式(3.2)知(3.3)因此αk‖gk‖2→ 0 (k∈N, k→+∞), 于是由式(3.1)可知αk‖gk‖→ 0 (k∈N,k→+∞), 进而再由引理2.2可得αk‖dk‖→0, k∈N, k→+∞.(3.4)由式(2.4)、引理2.1及引理2.2可得(3.5)从而由(H2)和式(3.4)可得‖gk‖→ 0 (k∈N, k→+∞), 这与式(3.1)矛盾. 因此, {‖gk‖}有界.假设则存在无穷子列K⊂{1,2,…}及υ>0, 使得‖gk‖>, ∀k∈K.(3.6)由式(3.3)和(3.6)知,(3.7)从而知αk→ 0 (k∈K, k→+∞). 因为{‖dk‖}有界, 故知式(3.4)成立. 又由式(3.5)及假设(H2)和式(3.4)知‖gk‖→ 0 (k∈K, k→+∞), 这与式(3.6)矛盾. 因此,4 算法的线性收敛速率引理4.1[5] 若假设(H3)成立, 则假设(H1)和(H2)成立, f(x)在Rn上有唯一的极小点x*, 且存在M≥m>0, 使得:(4.1)m‖x-x*‖≤‖g(x)‖≤M‖x-x*‖.(4.2)引理4.2[5] 若假设(H3)成立, 则g(x)在水平集L0上Lipschitz连续, 即存在常数L>0, 使得‖g(x)-g(y)‖≤L‖x-y‖, ∀x,y∈L0.定理4.1 若假设(H3)成立, {xk}是由算法2.1产生的无穷点列, 则{xk}至少线性收敛于x*.证明: 由式(2.3)和引理2.1可知(4.3)又由式(3.5)知(4.4)从而由引理4.2可得于是由引理2.2知(4.5)又由式(4.3)和(4.5)可得(4.6)令则易知0<ω<1/2, 从而由式(4.6)知fk-fk+1≥ω‖gk‖2.余下的证明类似于文献[5]中的定理3, 故略.5 数值试验为进一步检验算法2.1的实用效果, 选取两个算例对本文算法进行数值试验, 并与Wolfe搜索下的共轭梯度法和最速下降法进行比较. 用IT表示达到相应精度时算法的迭代次数, fk表示迭代结束时的目标函数值, NA表示本文提出的新算法, 用FR,PRP,HS,CD和DY分别表示FR,PRP,HS,CD及DY共轭梯度法[1-2], SM表示最速下降法. 参数取值为ρ=0.299, σ1=0.38, σ2=0.85. 计算结果列于表1～表3. 例5.1 f(x)=(x1-x2)2+(x2+x3-2)2+(x4-1)2+(x5-1)2,x0=(-2,2,-2,2,2)T, x*=(1,1,1,1,1)T, f *=0.例5.2 扩展Beale函数:其中n=40.例5.3 例5.2中取n=80.表1 精度为|fk-f *|≤10-8,10-9,10-10时例5.1的计算结果Table 1 Results of example 5.1 with precision requirements |fk-f *|≤10-8,10-9,10-10方法ITfkNA8,9,91.531 2×10-9, 7.188 6×10-11, 7.188 6×10-11FR12,13,158.254 4×10-9, 9.037 9×10-10, 2.920 9×10-11PRP10,11,123.531 8×10-9, 1.4309×10-10, 8.863 7×10-11HS19,20,212.685 8×10-9, 2.552 0×10-10, 1.2343×10-11CD12,13,141.442 0×10-9, 1.403 5×10-10, 6.294 6×10-11DY12,14,149.175 2×10-9, 8.899 0×10-11, 8.899 0×10-11SM14,15,163.465 8×10-9, 5.180 8×10-10, 6.871 2×10-11表2 精度为|fk-f *|≤10-4,10-5,10-6时例5.2的计算结果Table 2 Results of example 5.2 with precision requirements |fk-f *|≤10-4,10-5,10-6方法ITfkNA13,15,165.902 6×10-5, 2.291 6×10-6, 2.108 7×10-7FR21,26,275.054 4×10-5, 2.864 4×10-6, 6.378 0×10-7PRP14,15,171.672 2×10-5, 5.0709×10-6, 8.909 3×10-7HS83,143,2036.925 6×10-5, 9.915 7×10-6, 9.9476×10-7CD16,18,22 6.059 7×10-5, 8.275 8×10-6, 7.110 6×10-7DY22,25,264.830 1×10-5, 1.036 3×10-6, 4.843 8×10-7SM98,128,1728.586 6×10-5, 9.226 2×10-6, 8.990 0×10-7表3 精度为|fk-f *|≤10-4,10-5,10-6时例5.3的计算结果Table 3 Results of example 5.3 with precision requirements |fk-f *|≤10-4,10-5,10-6方法ITfkNA14,15,164.801 9×10-5, 4.583 2×10-6, 4.217 3×10-7FR22,26,285.609 5×10-5, 5.728 7×10-6, 5.096 6×10-7PRP14,16,193.344 5×10-5, 3.2499×10-6, 6.644 6×10-7HS94,162,2249.834 6×10-5, 9.961 2×10-6, 9.9260×10-7CD17,19,249.915 0×10-5, 8.436 0×10-6, 2.212 7×10-7DY22,25,269.660 2×10-5, 2.072 5×10-6, 9.687 6×10-7SM103,139,1839.330 6×10-5, 9.941 6×10-6, 9.897 4×10-7由表1～表3可见, 本文提出的新算法不但理论上具有全局收敛性和线性收敛速率, 而且数值效果较好, 特别在要求精度较高和规模较大时, 新算法具有更好的效果.参考文献【相关文献】[1] 袁亚湘, 孙文瑜. 最优化理论与方法 [M]. 北京: 科学出版社, 1997.[2] 戴或虹, 袁亚湘. 非线性共轭梯度法 [M]. 上海: 上海科学技术出版社, 2000.[3] MA Ming-juan, HUANG Qing-dao, DENG Jian. Conjugate Gradient Method with the Inexact Line Search [J]. Journal of Jilin University: Science Edition, 2009, 47(3): 505-506. (马明娟, 黄庆道, 邓键. 非精确条件下的共轭梯度方法 [J]. 吉林大学学报: 理学版, 2009, 47(3): 505-506.)[4] Miele A, Cantrell J W. Study on a Memory Gradient Method for the Minimization of Functions [J]. JOTA, 1969, 3(6): 459-470.[5] TANG Jing-yong, SHI Zhen-jun. A Class of Global Convergent Memory Gradient Methods and Its Linear Convergence Rate [J]. Advances in Mathematics, 2007, 36(1): 67-75. (汤京永, 时贞军. 一类全局收敛的记忆梯度法及其线性收敛性 [J]. 数学进展, 2007, 36(1): 67-75.)[6] TANG Jing-yong, DONG Li, GUO Shu-li. A New Memory Gradient Method with Curve Search Rule [J]. Journal of Xinyang Normal University: Natural Science Edition, 2009, 22(2): 179-182. (汤京永, 董丽, 郭淑利. 一类新的曲线搜索下的记忆梯度法 [J]. 信阳师范学院学报: 自然科学版, 2009, 22(2): 179-182.)[7] TANG Jing-yong, DONG Li, ZHANG Xiu-jun. A New Class of Memory Gradient Methods with Wolfe Line Search [J]. Journal of Shandong University: Natural Science, 2009, 44(7): 33-37. (汤京永, 董丽, 张秀军. 一类新的Wolfe线性搜索下的记忆梯度法 [J]. 山东大学学报: 理学版, 2009, 44(7): 33-37.)[8] SHI Zhen-jun. A New Super-Memory Gradient Method for Unconstrained Optimization[J]. Advances in Mathematics, 2006, 35(3): 265-274.。
Frank-Wolfe 算法（也称为条件梯度法或梯度投影算法）是一种用于解决凸优化问题的迭代算法。
该算法的基本原理涉及到在每一步通过梯度信息在一个约束集合上寻找一个线性化的近似最优解。
以下是 Frank-Wolfe 算法的基本原理和一个简单的Python 实现。
基本原理：
给定一个凸优化问题：
min x∈C f(x)
其中f(x)是目标函数，C是一个约束集合。
Frank-Wolfe 算法的迭代步骤如下：
1.在当前点x k处计算目标函数的梯度∇f(x k)。
2.在约束集合C中找到一个关于梯度的线性化近似最优解s k。
这通常通过求
解线性子问题来实现。
3.根据线性化近似解更新当前点x k，即执行x k+1=x k+αk(s k−x k)。
4.重复上述步骤直到满足停止准则。
Python 实现：
以下是一个简单的 Python 实现，假设目标函数是二次函数：
这是一个简单的二次函数的例子。
在实际应用中，你需要替换quadratic_objective、quadratic_gradient、和quadratic_linear_oracle为实际问题中的目标函数、梯度函数和线性预测函数。
此外，可以根据实际情况选择合适的步长规则。
Matlab学习手记——线搜索Wolfe准则线是数值最优化算法中常用的一种方法，用于确定在给定方向上的最优步长。
Wolfe准则是一种经典的线准则，旨在保证策略能够在每一步都保持收敛性质，并且避免过大或过小的步长。
在Matlab中，我们可以利用内置函数和自定义函数来实现线Wolfe准则。
首先，我们需要定义一个目标函数和它的梯度函数。
例如，我们以Rosenbrock函数为例：```matlabfunction [value, gradient] = rosenbrock(x)value = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;if nargout > 1gradient = [-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1)); 200*(x(2)-x(1)^2)];endend```其中，`x`是一个二维向量。
该函数计算了Rosenbrock函数的值和梯度。
接下来，我们可以定义一个函数来实现线Wolfe准则。
具体来说，我们需要实现Armijo准则和曲率条件。
以下是一个可能的实现：```matlabfunction [alpha, value] = line_search_wolfe(f, x, p, c1, c2, max_iter, alpha_max)alpha = alpha_max;[f0, gradient0] = f(x);value = f0;for iter = 1:max_iter[f_alpha, gradient_alpha] = f(x + alpha*p);if f_alpha > f0 + c1*alpha*gradient0'*p ， (iter > 1 &&f_alpha >= f_alpha0)alpha = zoom(f, x, p, c1, c2, alpha0, alpha);return;endif abs(gradient_alpha'*p) <= -c2*gradient0'*preturn;endif gradient_alpha'*p >= 0alpha = zoom(f, x, p, c1, c2, alpha, alpha0);return;endalpha0 = alpha;f_alpha0 = f_alpha;alpha = min(2*alpha, alpha_max);endendfunction alpha = zoom(f, x, p, c1, c2, alpha_lo, alpha_hi) while truealpha = (alpha_lo + alpha_hi)/2;[f_alpha, gradient_alpha] = f(x + alpha*p);f_lo = f(x + alpha_lo*p);if f_alpha > f_lo + c1*alpha*(gradient_alpha'*p) ，f_alpha >= f_alpha_loalpha_hi = alpha;elseif abs(gradient_alpha'*p) <= -c2*(gradient_lo'*p)break;endif gradient_alpha'*p*(alpha_hi - alpha_lo) >= 0alpha_hi = alpha_lo;endalpha_lo = alpha;f_alpha_lo = f_alpha;endendend```该函数接受一个目标函数和它的参数 `x` 和方向 `p`。
frank-wolfe算法机制
Frank-Wolfe算法是一种优化算法，用于求解具有线性约束的
最小化问题。
它也被称为条件梯度算法或序列最小优化算法。
该算法的基本思想是从问题的初始解开始，每次迭代通过在当前解处进行一次线性搜索来更新解。
具体步骤如下：
1. 初始化解：选择一个初始解 $x_0$ 作为起点。
2. 计算梯度：计算当前解的梯度 $g_k$。
3. 线性搜索：在问题的可行域中找到一个方向 $d_k$，使得在
该方向上的线性搜索能够得到一个新的解 $x_{k+1}$，该解使
得目标函数的值最小化。
具体来说，需要解决以下线性优化问题：
$$
\min_{d_k} g_k^T d_k \\
\text{subject to } x_k + d_k \text{满足线性约束}
$$
找到最优的 $d_k$ 后，更新解：$x_{k+1} = x_k + \lambda_k
d_k$，其中 $\lambda_k$ 是线性搜索的步长。
4. 更新梯度：计算新解 $x_{k+1}$ 处的梯度 $g_{k+1}$。
5. 终止条件判断：检查是否满足终止条件，如目标函数的变化小于某个阈值。
如果满足终止条件，则输出当前解$x_{k+1}$，否则返回第2步继续迭代。
Frank-Wolfe算法的优点是每次迭代只需要计算梯度，而无需
计算Hessian矩阵等二阶信息，因此在某些问题上的代价更低。
然而，它在某些情况下可能会收敛较慢，因此通常适用于问题具有稀疏结构或解稀疏的情况。
