多模式交通均衡问题的一阶分裂算法

本文研究包含私人交通和公共交通工具的多模式交通均衡问题,将其建模成带线性不等式约束的可分单调变分不等式问题,并提出一种修正的交替方向乘子法进行求解。通过适当地修改子问题并加上一个简单的校正步,提出一种针对线性不等式约束问题的并行求解算法。在一般的假设条件下,证明了这个新算法的全局收敛性和次线性收敛速度,并把算法应用到交通模型中。

关于一类非光滑极大极小问题的非单调线性搜索算法(英文)

考虑一类非光滑的离散的极大极小问题 :minmax{fi(x) |i=1…m} ,其中fi 是凸的 ,但不一定可微 .在这里我们给出了非单调线性搜索算法 ,并证明了在一定条件下算法具有全局收敛性 .

一类对称拟定系统的数值方法

证明了对称拟定系统的Schur补问题等价于一个广义最小二乘问题,并基于一种双对角化过程(GKLB过程)推导出了解系统(l)的一种新的迭代算法——LSQR(A(-1),C)方法,该方法不需要求出A和C的Cholesky因子,数值结果表明,与传统的方法(如SYMMLQ方法)比较,该方法有更快的收敛速度。

前言

城市交通系统是典型的动态复杂巨系统,具有开放、随机、非线性、多主体、自适应、耦合反馈等特点。系统性解决交通问题需要交叉融合多学科,数学在这一交叉融合过程中发挥着至关重要的作用。以运筹学为代表的数学科学为交通科学理论体系的建立与发展作出了巨大贡献。2022年,科学技术部国家重点研发计划“数学和应用研究”专项设立“智慧城市交通系统若干关键技术的数学理论与算法”项目(No.2021YFA1000300)。该项目由中国运筹学会理事长、中国科学院数学与系统科学研究院戴或虹研究员牵头,联合华东师范大学、长安大学、北京市城市规划设计研究院、青岛海信网络科技股份有限公司、中国交通信息科技集团有限公司等一批数学与交通研究相关单位,旨在依靠前沿数学理论赋能、“数学+”方法体系重构的创新研究方式摆脱传统路径依赖,着力突破解决城市交通基础研究与发展实践中的系列问题。

LC^1无约束优化问题的非单调线搜索算法

考虑LC1无约束优化问题,用二阶上Dini方向导数代替二阶的方向导数,从而给出该问题的一个非单调线搜索算法,并证明了所给算法的全局收敛性．

算子分裂法求解一类变分不等式问题的收敛率分析

考虑一类变分不等式问题:寻找x^*∈Ω,满足F(x^*)T(x-x^*)≥0,x∈Ω,其中Ω是R n上的闭凸子集,F=f+g是R n到R n的连续算子,f和g单调但f的表达式未知.针对此类应用较广的问题,本文研究了一种新的算子分裂法.根据已有的收敛性结果,进一步分析了该方法在非遍历意义下O(1/k)和o(1/k)的次线性收敛率,其中k表示迭代步数.最后,通过数值实验展示了算法的有效性.

一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法．当实际问题中子问题难以求解时，可以采用在子问题中添加邻近项的方法处理，邻近矩阵正定时，算法收敛，然而这也会使迭代步长较小．最新研究表明，邻近矩阵可以有一定的不正定性．本文在基于不定邻近项的广义交替方向乘子法框架下，提出一种自适应的广义交替方向乘子法，动态地选择邻近矩阵，增大迭代步长．在一些较弱的假设下，证明了算法的全局收敛性．我们进行一些初等数值实验，验证了算法的有效性．

求鞍点问题的新的原始-对偶算法

本文考虑求解鞍点问题的原始-对偶算法.通过对算法中的子问题加以修正,得到一类新的原始-对偶算法.在适当的假设条件下,证明了算法的收敛性.同时,将算法应用到一些图像处理问题,并与其它的原始-对偶类算法进行数值比较.结果表明,新的算法更加有效.

广义鞍点问题的改进的类SOR算法

针对广义鞍点问题,本文提出了一个改进的类逐次超松弛迭代算法,在较弱的条件下,分析了算法的收敛性及线性收敛率.新算法的每步计算量与已有的算法类似,都是需要(近似)求解线性方程组,但新算法有更好的灵活度通过合适地选取参数矩阵,每一步子问题可以容易地求解,甚至可以有闭式解(closed-form solution).数值实验结果显示了新算法的有效性.

稀疏优化在数独中的应用

数独是一个难以求解的整数规划问题,可以通过实数编码的方式去除整数约束的限制,将整数规划模型转化为一个ℓ_(0)范数极小化模型.已有算法大多是求解松弛的ℓ1范数极小化模型,只能求解部分数独问题.本文证明对于数独这样一个特殊的问题,ℓ_(q)(0<q<1)范数极小化模型等价于ℓ_(0)范数极小化模型,同时用ℓ_(1/2)-SLP(sequential linear programming)算法求解ℓ_(1/2)范数极小化模型.数值实验表明该方法可以求解更多的数独问题,本文从时间和成功率两方面验证了算法的高效性.

求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法

增广拉格朗日方法是求解带线性约束的凸优化问题的有效算法.线性化增广拉格朗日方法通过线性化增广拉格朗日函数的二次罚项并加上一个临近正则项,使得子问题容易求解,其中正则项系数的恰当选取对算法的收敛性和收敛速度至关重要.较大的系数可保证算法收敛性,但容易导致小步长.较小的系数允许迭代步长增大,但容易导致算法不收敛.本文考虑求解带线性等式或不等式约束的凸优化问题.我们利用自适应技术设计了一类不定线性化增广拉格朗日方法,即利用当前迭代点的信息自适应选取合适的正则项系数,在保证收敛性的前提下尽量使得子问题步长选择范围更大,从而提高算法收敛速度.我们从理论上证明了算法的全局收敛性,并利用数值实验说明了算法的有效性.