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 $Θ (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 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.
Related
- Continuous-time analysis and algorithms for linear and convex quadratic programs via exactly solvable differential inclusions
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- A Quadratic Lower Bound on Determinantal Complexity
- Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
BibTeX
@misc{liu2026dynamicthreshold,
title = {{Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity}},
author = {Yong-Jin Liu and Peicheng Xie and Chuan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.00740},
eprint = {2608.00740},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.00740},
}
RIS
TY - UNPB
TI - Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
AU - Yong-Jin Liu
AU - Peicheng Xie
AU - Chuan Yang
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2608.00740
UR - https://arxiv.org/abs/2608.00740
AB - 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 Θ(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 [− Θ(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.
ER -