报告题目： Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity

报 告 人：刘勇进 教授（福州大学）

报告时间：2026年9月11日（星期五）15:40—16:20

报告地点：数学科学学院114（小报告厅）

校内联系人：吴佳 教授         联系方式：84708351-8415

报告摘要： Condat's algorithm is an efficient dynamic-threshold method for projection onto the simplex, but its extension to weighted equality constraints and the algorithmic roles of resetting and removal have received limited analysis. We develop a dynamic-threshold algorithm (DTA) for a continuous quadratic knapsack problem with a weighted equality constraint. DTA maintains a threshold invariant through three operations--addition, reset, and removal--and we establish its finite termination and correctness. A sufficient condition under which reset cannot occur motivates a simpler no-reset variant, NDTA. We construct instances for which DTA runs in O(n) time whereas NDTA requires O(n^2) time, although both algorithms have quadratic worst-case complexity. We further show that, when the weight ratio and the number of deletions per removal pass are bounded, a linear number of passes with positive threshold increments requires the minimum nonzero gap between input values, normalized by the data range, to be at most exp[-O(n log(n))]. Numerical experiments with up to 10^7 variables demonstrate that DTA and NDTA achieve approximately linear empirical scaling, and outperform Secant, WMVA, Variable Fixing, Newton, Median Search, Heap, and Sort in running time.  

报告人简介：刘勇进，福州大学嘉锡学者特聘教授、博士生导师，福建省闽江教育领军人才闽江特聘教授，担任福建省应用数学中心（福州大学）主任。研究兴趣主要包括：最优化理论、方法与应用，大规模数值计算，统计优化等，研究成果在包括Math. Program.、SIAM J. Optim.、SIAM J. Sci. Comput.等优化与计算领域国际顶级学术期刊上发表。主持国家重点研发计划项目课题1项，主持国家自然科学基金5项，主持教育部、省重点项目等部省级纵向科研项目7项。现任中国数学会理事、中国运筹学会理事、中国运筹学会数学规划分会常务理事、中国运筹学会算法软件与应用分会常务理事、中国统计学会理事、福建省运筹学会会长、福建省数学学会副会长。担任国际期刊Annals of Applied Mathematics编委。