优化问题分裂算法及早高峰拥堵问题研究

发布时间：2018-06-16 22:30

本文选题：凸规划 + 变分不等式　；参考：《南京师范大学》2017年博士论文

【摘要】：变分不等式及凸规划问题为数学、管理科学及经济学等科研领域中的很多问题提供了一个统一的模型,很多问题都可以写成变分不等式问题,或由凸规划问题来表述.伴随着大数据时代的到来,所研究的实际问题的规模也变得很大,高效的求解算法的提出就显得很有必要,且具有极大的实用意义.目前很多迭代算法已被提出,并用于求解变分不等式问题的数值解,一些经典的方法包括:临近点算法、交替方向法、投影算法、分裂算法、牛顿法等.本文的目的是给出一些新的求解变分不等式问题的数值方法,如向前向后分裂算法、交替方向法、交替线性化方法及投影梯度法,并将其应用到求解互补问题、交通中网络均衡问题、图像恢复问题、压缩传感问题、信号恢复问题以及到椭球上投影的问题.相较于已有的算法,新的数值方法能够更好的求解这些问题.此外,本文也对交通中的早高峰拥堵问题进行了一些研究,并为管理者提供合理的方案,使得社会总消耗成本最小.分裂算法是通过求解一系列“好”条件问题,来求解原来的“坏”条件问题的,我们通过求解一系列的“好”条件问题,来得出原问题的解.然而算法中步长的选取范围对算法求解效率的影响是很大的.我们通过对向前向后分裂算法加松弛步,来扩大步长的选取范围;同时,我们允许每步迭代中的子问题非精确求解,这种策略极大的提高了算法的效率和实用性.交替方向法对于可分凸优化问题的求解具有简单、快速等优势.最近,我们将其应用到求解点到椭球上的投影问题,并与戴[27]的算法进行比较,说明了该算法的高效性.此外,对已有的对称交替方向法(即交替线性化方法),我们也做了适当的修正,给出了一个新的交替线性化方法,从而可以求解一些更一般的可分凸优化问题.最后,需要指出的是,当模型中目标函数为3块及以上的时候,直接的交替方向法在凸性下不一定能保证收敛性.韩和袁[54]给出了强凸下的收敛性证明.我们对条件适当弱化,给出了目标函数为一系列可分的复合函数(强凸和线性函数的复合)时,3块及以上的收敛性证明,并将该模型对应到交通中的一个实例.投影型算法,因在每步迭代中的计算量较小,从而很适合用来求解大规模问题.在该算法的每步迭代中,我们只需要去处理到可行集上的投影和函数值的计算.但现有的很多投影型算法的收敛性条件十分苛刻,如何弱化条件仍能保证收敛性是我们需要做的工作.基于Teschke和Borries提出的最速下降投影方法,我们提出了一个高效的投影算法来求解信号恢复中的非线性反问题,并在较弱的条件下给出了收敛性证明.此外,算法中起步长作用的参数的选取范围得到了适当的放松,并且该参数的选择方式也做了适当的改进.这些使得算法的适用性和效率得到了提高.早高峰交通拥堵问题是现代城市发展面临的一个极具挑战的问题,道路收费是缓解交通拥堵的一个有效的可行手段.但现有的收费模型大部分都是针对网络中为单人出行方式的.然而在很多亚洲国家出现了一种新的出行方式,即家庭式出行.对于这一新的出行方式的研究工作还处于初级阶段.依据已有的均衡下单人出行的出行率结果,我们定量分析了均衡下家庭式出行的出行率,并为管理者合理地制定上学、上班时间,及收费窗口和费用提供方案,使得社会总消耗成本最小.最后,通过可交易电子路票来替代这样的收费模型,在达到相同的缓解拥堵的效果下,也降低了网络中各家庭的时间成本.
[Abstract]:This paper presents some new numerical methods for solving variational inequality problems , such as forward backward splitting algorithm , alternating direction method , projection algorithm , splitting algorithm and Newton method . In this paper , we propose an efficient projection algorithm to solve the nonlinear inverse problem in modern city development .
【学位授予单位】：南京师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O224

【相似文献】