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

来源 :南京师范大学 | 被引量 : 1次 | 上传用户:majun913
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
变分不等式及凸规划问题为数学、管理科学及经济学等科研领域中的很多问题提供了一个统一的模型,很多问题都可以写成变分不等式问题,或由凸规划问题来表述.伴随着大数据时代的到来,所研究的实际问题的规模也变得很大,高效的求解算法的提出就显得很有必要,且具有极大的实用意义.目前很多迭代算法已被提出,并用于求解变分不等式问题的数值解,一些经典的方法包括:临近点算法、交替方向法、投影算法、分裂算法、牛顿法等.本文的目的是给出一些新的求解变分不等式问题的数值方法,如向前向后分裂算法、交替方向法、交替线性化方法及投影梯度法,并将其应用到求解互补问题、交通中网络均衡问题、图像恢复问题、压缩传感问题、信号恢复问题以及到椭球上投影的问题.相较于已有的算法,新的数值方法能够更好的求解这些问题.此外,本文也对交通中的早高峰拥堵问题进行了一些研究,并为管理者提供合理的方案,使得社会总消耗成本最小.分裂算法是通过求解一系列“好”条件问题,来求解原来的“坏”条件问题的,我们通过求解一系列的“好”条件问题,来得出原问题的解.然而算法中步长的选取范围对算法求解效率的影响是很大的.我们通过对向前向后分裂算法加松弛步,来扩大步长的选取范围;同时,我们允许每步迭代中的子问题非精确求解,这种策略极大的提高了算法的效率和实用性.交替方向法对于可分凸优化问题的求解具有简单、快速等优势.最近,我们将其应用到求解点到椭球上的投影问题,并与戴[27]的算法进行比较,说明了该算法的高效性.此外,对已有的对称交替方向法(即交替线性化方法),我们也做了适当的修正,给出了一个新的交替线性化方法,从而可以求解一些更一般的可分凸优化问题.最后,需要指出的是,当模型中目标函数为3块及以上的时候,直接的交替方向法在凸性下不一定能保证收敛性.韩和袁[54]给出了强凸下的收敛性证明.我们对条件适当弱化,给出了目标函数为一系列可分的复合函数(强凸和线性函数的复合)时,3块及以上的收敛性证明,并将该模型对应到交通中的一个实例.投影型算法,因在每步迭代中的计算量较小,从而很适合用来求解大规模问题.在该算法的每步迭代中,我们只需要去处理到可行集上的投影和函数值的计算.但现有的很多投影型算法的收敛性条件十分苛刻,如何弱化条件仍能保证收敛性是我们需要做的工作.基于Teschke和Borries提出的最速下降投影方法,我们提出了一个高效的投影算法来求解信号恢复中的非线性反问题,并在较弱的条件下给出了收敛性证明.此外,算法中起步长作用的参数的选取范围得到了适当的放松,并且该参数的选择方式也做了适当的改进.这些使得算法的适用性和效率得到了提高.早高峰交通拥堵问题是现代城市发展面临的一个极具挑战的问题,道路收费是缓解交通拥堵的一个有效的可行手段.但现有的收费模型大部分都是针对网络中为单人出行方式的.然而在很多亚洲国家出现了一种新的出行方式,即家庭式出行.对于这一新的出行方式的研究工作还处于初级阶段.依据已有的均衡下单人出行的出行率结果,我们定量分析了均衡下家庭式出行的出行率,并为管理者合理地制定上学、上班时间,及收费窗口和费用提供方案,使得社会总消耗成本最小.最后,通过可交易电子路票来替代这样的收费模型,在达到相同的缓解拥堵的效果下,也降低了网络中各家庭的时间成本.
其他文献
学位
学位
G蛋白偶联受体(GPCR)Latrophilin(LPH)不仅涉及人类与哺乳动物的多动症、精神分裂症及成瘾等精神疾病的发生,还涉及到对外源蛛毒素的信号传递及多种药物的敏感性。目前关于LPH受体在昆虫中的功能和信号传导机制尚不清楚。本研究首先在21种动物中对LPH进行了系统进化分析,结果显示,lph是由一个共同祖先基因衍化而来,但是lph分别在脊椎动物、头索动物、尾索动物和昆虫中发生了独立的进化。l
本文主要研究了余半倾斜(cosilting)模和余半倾斜复形的同调性质.具体本文组织如下:1,首先,我们研究了拟倾斜模的对偶—拟余倾斜模。在这一部分中我们证明了所有的拟余倾斜模既是纯内射的又是余有限自同态(cofinendo)的.由此得到,当M是一个拟余倾斜模时,由M余生成的类CogenM总是一个盖类.同时也给出了关于拟余倾斜模的一些特征刻画.作为这部分的主要结果,我们给出了拟余倾斜模的等价类和挠
在本文中,我们研究了 Douglas-Rachford算子分裂方法求解非凸优化问题的收敛性分析.论文由四部分构成,结构如下:第一、二章,给出了本文的研究背景及所要用到的一些预备知识.第三章,我们考虑乘子交替方向法求解线性约束非凸优化问题的收敛性分析.本质上,乘子交替方向法可以看作Douglas-Rachford分裂方法应用到两块线性约束可分凸优化问题的对偶问题.对于许多应用问题中的大规模可分优化问
学位
本文主要研究几类丢番图方程.文章主要由三部分构成.1.第一部分,我们研究了广义费马方程,得到了下面几个结论:(1.1)设素数p满足br+1 = 2pt,其中r,t,6为正整数,且6 = 3,5 (mod 8),则丢番图方程x2+bm=pn只有一组正整数解(x,m,n) = (pt-1,r,2t).进而,如果6 = q是奇素数,并且r = t = 2,则上述方程满足下述条件之一时只有一组正整数解,这
图像不仅包含颜色、大小等属性信息,还具有位置、形状及拓扑关系等丰富的空间信息,它能够为GIS提供及时、综合和可靠的空间数据,是GIS空间数据的重要来源。随着数码相机、手机等摄像设备的普及使用,以及摄像元件分辨率越来越高,图像包含的空间信息也越来越丰富,从图像中快速提取并构建三维模型成为3DGIS空间数据获取的发展趋势。在计算机视觉研究领域,目前较多关注基于图像提取三维模型的方法研究,较少研究三维模
本文中我们主要研究了混合指数和及欧拉函数值的和.主要结果如下:1.对任意的正整数m, n,k≥ 2, q > 3,我们关心下面的四次均值其中χ是模q的狄利克雷特征,表示函数f在不超过q的与q互素的正整数a上的值之和.2008年,Liu在条件(k, q) = 1及(n,q) = 1下得到了这个四次均值的显式公式.2014年,Chen, Ai和Cai去掉了限制条件(k,q) = 1.在本文中,我们去掉
本文致力于研究动力系统中Birkhoff平均的重分形分析和可数离散群作用的Bowen拓扑熵。(X,d,f)称为拓扑动力系统,是指(X,d)是一个紧致度量空间,f是一个X到自身的连续映射。第一章到第三章,我们研究了具有几乎弱specification性质的映射并且把结果应用到紧致度量阿贝尔群的遍历自同构。我们研究了historic集的压、generic性质,并且得到了关于集合E(I)拓扑压的一个条件