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

报告人：刘勇进嘉锡学者特聘教授福州大学

报告时间：2026年08月02日上午11:00-12:00

报告地点：正新楼201

校内联系人：温金明 [email protected]

报告摘要：

  In this talk, we propose a dynamic-threshold framework to a continuous quadratic knapsack problem with a weighted equality constraint. This problem arises, in particular, from zero-lower-bound weighted minimum-variance allocation and a continuous relaxation of sensor placement. The resulting dynamic-threshold algorithm (DTA) is governed by three operations: addition, reset, and removal. We establish finite termination and correctness, derive a sufficient condition under which no reset occurs, and introduce a 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 a long removal phase with a bounded number of deletions per iteration requires extremely small nonzero gaps relative to the data range when the weight ratio is bounded. Numerical experiments with up to 10^7 variables show nearly linear empirical scaling for both methods. DTA and NDTA are faster than the tested Secant, WMVA, Variable Fixing, Newton, Median Search, Heap, and Sort implementations, while satisfying the prescribed residual tolerance on all tested instances.

报告人简介：

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