报告题目：Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
主讲人：刘勇进教授（福州大学）
时间：2026年11月12日（周四）9:00 a.m.
形式：线上讲座
腾讯会议：269-995-613，密码：1112
主办单位：统计与数学学院
摘要：
Condat算法是一种用于单纯形投影的高效动态阈值方法，但其向加权等式约束的扩展以及重置和移除的算法作用所受到的分析有限。我们针对具有加权等式约束的连续二次背包问题开发了一种动态阈值算法（DTA）。DTA通过加法、重置和移除三种操作维持阈值不变性，我们建立了其有限终止性和正确性。一个使重置不可能发生的充分条件促成了一个更简单的无重置变体NDTA。我们构造了一些实例，使得DTA以O(n)时间运行，而NDTA需要O(n^2)时间，尽管两种算法都具有二次最坏情况复杂度。我们进一步表明，当权重比和每次移除过程中删除的数量有界时，若正阈值增量的趟数为线性数量，则要求输入值之间的最小非零间隙（按数据范围归一化）至多为exp[-O(n log(n))]。最多包含10^7个变量的数值实验表明，DTA和NDTA实现了近似线性的经验 scaling，并且在运行时间上优于Secant、WMVA、Variable Fixing、Newton、Median Search、Heap和Sort。
主讲人简介：
刘勇进，福州大学嘉锡学者特聘教授、博士生导师，福建省闽江教育领军人才闽江特聘教授，担任福建省应用数学中心（福州大学）主任。研究兴趣主要包括：最优化理论、方法与应用，大规模数值计算，统计优化等，研究成果在包括Math. Program.、SIAM J. Optim.、SIAM J. Sci. Comput.等优化与计算领域国际顶级学术期刊上发表。主持国家重点研发计划项目课题1项，主持国家自然科学基金5项，主持教育部、省重点项目等省部级纵向科研项目7项。现任中国数学会理事、中国运筹学会理事、中国运筹学会数学规划分会常务理事、中国运筹学会算法软件与应用分会常务理事、中国统计学会理事、福建省运筹学会会长、福建省数学学会副会长。担任国际期刊Annals of Applied Mathematics编委。
滇公网安备53010202000350号滇ICP备17008047号 Copyright © 2013 Yunnan University of Finance and Economics All Rights Reserved
