2026/08/01 by Yong-Jin Liu, Peicheng Xie, Chuan Yang
Mathematics · #math.OC
arxiv created 2026/08/01 · arxiv updated 2026/08/04
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 Θ (n) time whereas NDTA requires Θ(n2) 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 [- Θ(n log n)]. Numerical experiments with up to 107 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.