Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity

Abstract

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 ${\Theta} (n)$ time whereas NDTA requires $\Theta (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 [- \Theta (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.