pith. sign in

arxiv: 2603.15910 · v2 · pith:USC22ANOnew · submitted 2026-03-16 · 🧮 math.OC

Parallel Newton methods for the continuous quadratic knapsack problem: A Jacobi and Gauss-Seidel tale

Leonardo D. Secchin , Paulo J. S. Silva This is my paper

Pith reviewed 2026-05-21 10:49 UTC · model grok-4.3

classification 🧮 math.OC
keywords continuous quadratic knapsacksemismooth Newton methodparallel algorithmsJacobi methodGauss-Seidelsimplex projectionresource allocationoptimization
0
0 comments X

The pith

The semismooth Newton method for continuous quadratic knapsack problems improves with Condat's multiplier guess and parallel Jacobi or Gauss-Seidel variants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper revisits the semismooth Newton method for the continuous quadratic knapsack problem, which minimizes a diagonal convex quadratic subject to box and equality constraints. The authors show it can be strengthened first by using Condat's effective initial multiplier guess for projections onto the simplex or l1-ball, and second by recasting it as the basis for parallel algorithms using Jacobi and Gauss-Seidel styles. These changes target CPU and GPU architectures and are packaged in open-source Julia code. The work matters because CQK instances arise in resource allocation, multicommodity flows, and Lagrangian relaxation, where faster solves directly enable larger models. Numerical comparisons indicate the new variants deliver better efficiency and scaling than existing solvers.

Core claim

The central claim is that the semismooth Newton method introduced by Cominetti, Mascarenhas and Silva becomes substantially more effective for the continuous quadratic knapsack problem once it incorporates Condat's initial multiplier guess and is extended to parallel Jacobi and Gauss-Seidel realizations; extensive tests then demonstrate superior efficiency and scalability on CPU and GPU hardware relative to state-of-the-art alternatives.

What carries the argument

Semismooth Newton iteration equipped with Condat's multiplier initialization and reformulated as parallel Jacobi or Gauss-Seidel schemes for the CQK problem.

Load-bearing premise

The numerical test instances and hardware setups used are representative of practical CQK problems and that observed speedups arise from the algorithmic changes rather than implementation details.

What would settle it

A large-scale benchmark on diverse real-world CQK instances in which the proposed parallel variants show no consistent runtime or scalability advantage over competing solvers.

Figures

Figures reproduced from arXiv: 2603.15910 by Leonardo D. Secchin, Paulo J. S. Silva.

Figure 1
Figure 1. Figure 1: (a) Lateral slopes of max{li , min{ui ,(biλ + ai)/di}} at breakpoints. (b) A typical plot of φ(·) − r. Algorithm 1 Semi-smooth Newton method for solving (CQK) Require: the initial dual estimate λ0 1: Set k ← 0, λ ← −∞ and λ ← ∞ 2: if φ(λk) = r then 3: Stop and return x(λk) as the solution of (CQK) 4: if φ(λk) < r then 5: Update λ ← λk 6: if φ ′ +(λk) > 0 then 7: Define λ˜ k = λk − φ(λk)−r φ′ +(λk) 8: If λ˜… view at source ↗
Figure 2
Figure 2. Figure 2: Speedups of parallel Algorithm 1 with variable fixing relative to the sequential version on random instances. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Relative performance of Algorithm 1 from NewtonCQK.jl and CMS using variable fixing and warm starts to solve (7) along the SPG iterations. The baseline (horizontal blue line at 1) is the performance of the NewtonCQK.jl without warm start [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Speedups of parallel Algorithm 1 for solving (7) in relation to the sequential algorithm. All algorithms were executed using the current SPG iterate as warm start. 5.2 Projection onto simplex and ℓ1 ball 5.2.1 Randomly generate instances In this section, we present numerical results for problem (proj∆). Following the methodology in [16] and references therein, we consider three classes of test problems bas… view at source ↗
Figure 5
Figure 5. Figure 5: Speedups of Algorithm 4 implemented in NewtonCQK.jl (CPU versions returning dense and sparse solutions), Dai and Chen’s (sparse solution) and Condat’s (dense solution) algorithms on (proj∆), instances of type 1. The base algorithm is of Condat, which is represented by the horizontal line. We observe that both NewtonCQK.jl implementations of Algorithm 4 (dense and sparse output) outperforms Condat’s origina… view at source ↗
Figure 6
Figure 6. Figure 6: Speedups of Algorithm 4 implemented in NewtonCQK.jl (CPU versions returning dense and sparse solutions), Dai and Chen’s (sparse solution) and Condat’s (dense solution) algorithms on (proj∆), instances of type 3. The base algorithm is of Condat, which is represented by the horizontal line. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: On the left, relative performace of CPU algorithms that compute sparse projections onto [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Speedups of the parallel implementation of the specialized Algorithm [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
read the original abstract

The continuous quadratic knapsack (CQK) problem involves minimizing a diagonal convex quadratic function subject to box constraints and a single linear equality constraint. It has numerous applications in resource allocation, multicommodity flow, machine learning, and classical optimization tasks such as Lagrangian relaxation and quasi-Newton updates. In this work, we revisit the semismooth Newton method introduced by Cominetti, Mascarenhas, and Silva. We demonstrate that the method can be significantly improved in two directions. First, for projections onto the simplex or the $\ell_1$-ball, it can incorporate Condat's highly effective initial multiplier guess. Second, it can serve as a flexible foundation for CQK algorithms, allowing for different parallel variants tailored to exploit CPU and GPU computational models. These improvements are implemented in the open-source Julia package \texttt{NewtonCQK.jl}. We present extensive numerical tests comparing this implementation with other state-of-the-art solvers, demonstrating its superior efficiency and scalability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper revisits the semismooth Newton method for the continuous quadratic knapsack (CQK) problem. It proposes two improvements: incorporating Condat's initial multiplier guess for projections onto the simplex or l1-ball, and developing parallel Jacobi and Gauss-Seidel variants tailored to CPU and GPU architectures. These are implemented in the open-source Julia package NewtonCQK.jl, with claims of superior efficiency and scalability demonstrated via extensive numerical tests against state-of-the-art solvers.

Significance. If the central claims hold, the work offers practical advances for CQK solvers used in resource allocation, machine learning, and Lagrangian relaxation by providing scalable parallel implementations. The open-source package and focus on parallel CPU/GPU models are strengths that enhance reproducibility and applicability. However, the significance is tempered by the need to verify the numerical evidence for unbiased comparisons.

major comments (2)
  1. [Parallel variants section] The manuscript asserts convergence for the parallel Jacobi and Gauss-Seidel variants but does not provide or reference the full convergence analysis or proofs for these parallel implementations (mentioned in the abstract and parallel variants discussion); this is load-bearing for the reliability claims.
  2. [Numerical experiments] Numerical experiments section: the test suite description lacks specifics on problem generation (e.g., conditioning, dimension ranges), hardware details, baseline solver parallelization effort, and full reporting of iteration counts versus wall-clock time; this undermines verification of the superior efficiency and scalability claims.
minor comments (2)
  1. [Numerical experiments] Consider adding a brief comparison table summarizing iteration counts and timings across all methods for quick reference.
  2. [Method description] Notation for the multiplier update in the semismooth Newton step could be clarified with an explicit equation reference to avoid ambiguity in the parallel variants.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive suggestions. We address each major comment below and describe the revisions that will be incorporated into the next version of the manuscript.

read point-by-point responses

  1. Referee: [Parallel variants section] The manuscript asserts convergence for the parallel Jacobi and Gauss-Seidel variants but does not provide or reference the full convergence analysis or proofs for these parallel implementations (mentioned in the abstract and parallel variants discussion); this is load-bearing for the reliability claims.

    Authors: We agree that a dedicated convergence analysis strengthens the reliability of the parallel variants. The sequential semismooth Newton method inherits convergence from the framework of Cominetti, Mascarenhas, and Silva, but the Jacobi and Gauss-Seidel parallelizations require additional justification to account for simultaneous updates. In the revised manuscript we will insert a new subsection under Parallel Variants that sketches the convergence argument: under the assumption that the quadratic is strictly convex and the active-set identification occurs after finitely many steps, both parallel schemes converge to the unique solution because the iteration remains a contraction mapping in a suitable norm (following standard results on parallel semismooth Newton methods). We will also cite relevant literature on asynchronous and block-coordinate Newton methods to place the argument in context. revision: yes

  2. Referee: [Numerical experiments] Numerical experiments section: the test suite description lacks specifics on problem generation (e.g., conditioning, dimension ranges), hardware details, baseline solver parallelization effort, and full reporting of iteration counts versus wall-clock time; this undermines verification of the superior efficiency and scalability claims.

    Authors: We concur that greater experimental detail is required for independent verification. The revised Numerical Experiments section will be expanded to specify: (i) the exact procedure for generating test instances, including dimension ranges (n = 10^3 to 10^7), the distribution used for the diagonal entries of the quadratic (with explicit conditioning numbers), and the random generation of the linear equality right-hand side; (ii) the precise CPU (multi-core Xeon) and GPU (NVIDIA A100) hardware configurations together with Julia version and threading settings; (iii) the parallelization effort applied to each baseline solver (e.g., number of threads or GPU kernels used); and (iv) complete tables reporting both iteration counts and wall-clock times, accompanied by performance profiles that separate iteration complexity from runtime. The generated test instances will be archived in the NewtonCQK.jl repository. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic extensions rest on independent design and external benchmarks.

full rationale

The paper revisits the semismooth Newton method from prior literature (Cominetti, Mascarenhas, Silva) and adds Condat's multiplier guess plus parallel Jacobi/Gauss-Seidel variants implemented in NewtonCQK.jl. These are presented as new algorithmic constructions with numerical comparisons to state-of-the-art solvers. No equations reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations that would force the claimed improvements. The derivation chain for the parallel methods is self-contained against external performance metrics.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new free parameters, invented entities, or ad-hoc axioms. It relies on the convergence properties of the original semismooth Newton method and standard convex optimization assumptions.

axioms (1)
  • domain assumption The semismooth Newton method for CQK converges under the conditions established by Cominetti, Mascarenhas, and Silva.
    The current work revisits and extends this method without reproving its convergence properties.

pith-pipeline@v0.9.0 · 5701 in / 1452 out tokens · 55318 ms · 2026-05-21T10:49:25.038986+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    A. R. Amaral. On the exact solution of a facility layout problem.European Journal of Operational Research, 173(2):508–518, sep 2006

    work page 2006

  2. [2]

    Bauer and Et al

    C. Bauer and Et al. OhMyThreads.jl simple multithreading in Julia, 2026.https://github. com/JuliaFolds2/OhMyThreads.jl

    work page 2026

  3. [3]

    Basis pursuit by inconsistent alternating projections

    R. Behling, Y. Bello-Cruz, L.-R. Santos, and P. J. S. Silva. Basis pursuit by inconsistent alternating projections. (arXiv:2508.15026), Aug. 2025. arXiv:2508.15026 [math]

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  4. [4]

    Besançon, T

    M. Besançon, T. Papamarkou, D. Anthoff, A. Arslan, S. Byrne, D. Lin, and J. Pearson. Dis- tributions.jl: Definition and modeling of probability distributions in the juliastats ecosystem. Journal of Statistical Software, 98(16):1–30, 2021

    work page 2021

  5. [5]

    E. G. Birgin, J. M. Martínez, and M. Raydan. Nonmonotone spectral projected gradient methods on convex sets.SIAM Journal on Optimization, 10(4):1196–1211, 2000

    work page 2000

  6. [6]

    E. G. Birgin, J. M. Martínez, and M. Raydan. Algorithm 813: SPG-software for convex- constrained optimization.ACM Transactions on Mathematical Software, 27(3):340–349, 2001. 18

    work page 2001

  7. [7]

    G. R. Bitran and A. C. Hax. Disaggregation and resource allocation using convex knapsack problems with bounded variables.Management Science, 27(4):431–441, Apr. 1981

    work page 1981

  8. [8]

    K. M. Bretthauer and B. Shetty. Quadratic resource allocation with generalized upper bounds. Operations Research Letters, 20(2):51–57, Feb. 1997

    work page 1997

  9. [9]

    K. M. Bretthauer and B. Shetty. The nonlinear knapsack problem – algorithms and applica- tions.European Journal of Operational Research, 138(3):459–472, May 2002

    work page 2002

  10. [10]

    Abranchandboundalgorithmforintegerquadratic knapsack problems.ORSA Journal on Computing, 7(1):109–116, Feb

    K.M.Bretthauer, B.Shetty, andS.Syam. Abranchandboundalgorithmforintegerquadratic knapsack problems.ORSA Journal on Computing, 7(1):109–116, Feb. 1995

    work page 1995

  11. [11]

    C. J. Burges. A tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery, 2(2):121–167, 1998

    work page 1998

  12. [12]

    Chen and J

    J. Chen and J. Revels. Robust benchmarking in noisy environments.arXiv e-prints, Aug 2016

    work page 2016

  13. [13]

    S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit.SIAM Review, 43(1):129–159, 2001

    work page 2001

  14. [14]

    Cominetti, W

    R. Cominetti, W. F. Mascarenhas, and P. J. S. Silva. A Newton’s method for the continuous quadratic knapsack problem.Mathematical Programming Computation, 6(2):151–169, Feb. 2014

    work page 2014

  15. [15]

    L. Condat. Fast projection onto the simplex and thel1 ball.Mathematical Programming, 158(1–2):575–585, Sept. 2016

    work page 2016

  16. [16]

    Dai and C

    Y. Dai and C. Chen. Sparsity-exploiting distributed projections onto a simplex.INFORMS Journal on Computing, 36(3):820–835, May 2024

    work page 2024

  17. [17]

    Dai and R

    Y.-H. Dai and R. Fletcher. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds.Mathematical Programming, 106(3):403–421, Oct. 2005

    work page 2005

  18. [18]

    Dean and S

    J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters.Commu- nications of the ACM, 51(1):107–113, Jan. 2008

    work page 2008

  19. [19]

    Duchi, S

    J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the l1- ball for learning in high dimensions. InProceedings of the 25th international conference on Machine learning - ICML ’08, ICML ’08, pages 272–279. ACM Press, 2008

    work page 2008

  20. [20]

    Fletcher, S

    R. Fletcher, S. Leyffer, D. Ralph, and S. Scholtes. Local convergence of SQP methods for mathematical programs with equilibrium constraints.SIAM Journal on Optimization, 17(1):259–286, 2006

    work page 2006

  21. [21]

    M. D. Gonzalez-Lima, W. W. Hager, and H. Zhang. An affine-scaling interior-point method for continuous knapsack constraints with application to support vector machines.SIAM Journal on Optimization, 21(1):361–390, Jan. 2011

    work page 2011

  22. [22]

    K. C. Kiwiel. Breakpoint searching algorithms for the continuous quadratic knapsack problem. Mathematical Programming, 112(2):473–491, Nov. 2008

    work page 2008

  23. [23]

    K. C. Kiwiel. Variable fixing algorithms for the continuous quadratic knapsack problem. Journal of Optimization Theory and Applications, 136(3):445–458, Nov. 2008

    work page 2008

  24. [24]

    Lopes, S

    R. Lopes, S. A. Santos, and P. J. S. Silva. Accelerating block coordinate descent methods with identification strategies.Computational Optimization and Applications, 72(3):609–640, Jan. 2019

    work page 2019

  25. [25]

    Marsaglia

    G. Marsaglia. Xorshift RNGs.Journal of Statistical Software, 8(14), 2003

    work page 2003

  26. [26]

    Michelot

    C. Michelot. A finite algorithm for finding the projection of a point onto the canonical simplex ofR n.Journal of Optimization Theory and Applications, 50(1):195–200, July 1986. 19

    work page 1986

  27. [27]

    Nocedal and S

    J. Nocedal and S. J. Wright.Numerical Optimization. Springer, 2 edition, 2006

    work page 2006

  28. [28]

    J.-S. Pang. A new and efficient algorithm for a class of portfolio selection problems.Operations Research, 28(3-part-ii):754–767, 1980

    work page 1980

  29. [29]

    Patriksson

    M. Patriksson. A survey on the continuous nonlinear resource allocation problem.European Journal of Operational Research, 185(1):1–46, Feb. 2008

    work page 2008

  30. [30]

    T. C. Sharkey, H. E. Romeijn, and J. Geunes. A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems.Mathematical Programming, 126(1):69–96, Jan. 2011

    work page 2011

  31. [31]

    Tibshirani

    R. Tibshirani. Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267–288, 1996

    work page 1996

  32. [32]

    J. A. Ventura. Computational development of a lagrangian dual approach for quadratic networks.Networks, 21(4):469–485, 1991. 20 Figure 6: Speedups of Algorithm 4 implemented inNewtonCQK.jl(CPU versions returning dense and sparse solutions), Dai and Chen’s (sparse solution) and Condat’s (dense solution) algorithms on (proj∆), instances of type 3. The base ...

    work page 1991