Pith. sign in

REVIEW 3 major objections 5 minor 25 references

Active-set Newton-MR methods for nonconvex optimization problems with bound constraints

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Pith's one-line read Two active-set methods bring provable ε-stopping complexity to Newton-MR with bound constraints: O(nε^-2) with SPG escapes and O(n|log ε|ε^-3/2) with cubic regularization.

desk verdict Worth a serious referee: Algorithm P is solid with a clean O(n ε^-2) bound and strong experiments; Algorithm T's headline O(ε^-3/2) rate has a real gap between theory and implementation. read the letter →

arxiv 2508.20967 v1 pith:ZKYLIMNS submitted 2025-08-28 math.OC

classification math.OC MSC 90C2690C3065K0590C5390C06
keywords bound-constrainedoptimizationMINRESNewton-MRactive-setmethodsnonconvexworst-caseiterationcomplexityspectralprojectedgradientcubicregularization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper brings the Newton-MR idea — a truncated Newton method that uses the Minimum Residual (MINRES) solver — to bound-constrained nonconvex minimization, and proves worst-case guarantees on the number of oracle calls. Inside each face of the feasible box, an Armijo line search descends along an approximate Newton direction computed by MINRES; to escape a face, the method uses either a monotone Spectral Projected Gradient step (Algorithm P) or a specialized cubic-regularization step (Algorithm T). Under only a Lipschitz gradient and a bounded-below objective, Theorem 2.5 shows Algorithm P reaches a point with projected-gradient norm at most ε in O(nε^-2) oracle calls, and adding a Lipschitz-Hessian assumption, Theorem 2.15 shows Algorithm T achieves the same in O(n|log2 ε|ε^-3/2) calls. A notable byproduct is that within a face the MINRES direction alone can give O(ε^3/2) descent per iteration, without cubic regularization. On 475 benchmark problems, the O(ε^-2) variant was more robust and faster than the cubic variant and than the CG-based active-set method Gencan — evidence that MINRES is a practical upgrade over conjugate gradients inside active-set Newton solvers.

What carries the argument

MINRES's certified output is the load-bearing object: under the grade assumption it returns either 'SOL' (approximate Newton step, curvature ≥ η) or 'NPC' (negative-curvature direction with ⟨g,r⟩ = −‖r‖²). Lemma 2.1's correction rescales any candidate and blends it with steepest descent so that ‖d‖ ≤ a1‖g‖ and ⟨g,d⟩ ≤ −a2‖g‖², making Armijo decrease uniform. Lemmas 2.7–2.9 convert these certified directions into O(‖∇_I f‖^3/2) descent per face-iteration, the engine of the ε^-3/2 rate; the SPG variant needs only O(‖∇_I f‖²) descent, so its O(ε^-2) bound skips the dichotomy and Hessian Lipschitzness. The active-set structure adds the factor n: each boundary escape drops face dimension, capping

What would settle it

Instrument every MINRES call in the supplied implementation and record, for each call, whether the iteration count exceeds the grade of its Krylov space: a single call that exits past the grade and returns an uncertified step falsifies the precondition of Lemma 2.9 and Theorem 2.15. Separately, run the cubic-regularization variant on a Hessian-Lipschitz bound-constrained problem at ε = 10^-4, 10^-6, 10^-8 and check whether iteration counts scale like ε^-3/2: a clear ε^-2 scaling would show the certified-dichotomy mechanism is not what drives the method. For the numerical claim, re-run the benc

Watch

Extended reading notes

Core claim

The central claim: MINRES's two-certificate output — 'SOL', an approximate Newton-system solution, or 'NPC', a negative-curvature direction whose residual is a certified descent step — is enough to run a Newton method inside the faces of a box with provable stopping times. With an SPG face-escape the method reaches ‖∇_Ω f(x)‖ ≤ ε in O(nε^-2) oracle calls, needing only Lipschitz gradient and bounded-belowness (Theorem 2.5). With a cubic-regularization escape the same target takes O(n|log2 ε|ε^-3/2) calls, at the price of Lipschitz-Hessian smoothness (Theorem 2.15). Lemma 2.9: the MINRES direction alone yields O(‖∇_I f‖^3/2) descent per iteration, without cubic regularization.

Load-bearing premise

The load-bearing premise is that every MINRES run is short enough that its output is guaranteed to be one of two certified types — an approximate Newton solution or a detected negative-curvature direction — and, for the faster variant, that the objective's Hessian is Lipschitz continuous.

Editorial extensions

If this is right

  • Augmented Lagrangian methods that use these algorithms as subproblem solvers inherit per-subproblem worst-case budgets of O(nε^-2) or O(n|log2 ε|ε^-3/2) oracle calls, with constants fixed by the Lipschitz and line-search parameters.
  • Algorithm P's O(ε^-2) guarantee requires only a Lipschitz gradient and a bounded-below objective, so the complexity proof covers nonconvex problems where Hessian Lipschitzness cannot be verified.
  • Within any given face, the certified MINRES direction alone yields O(ε^3/2) function decrease per iteration, so the fast rate does not inherently require the cubic-regularization machinery.
  • If the benchmark comparison generalizes, replacing CG with MINRES in the inner Newton loop of active-set solvers improves both robustness and speed, with implications for large-scale bound-constrained software.
  • The observed ordering of the two methods — the weaker-guarantee SPG variant performing better than the stronger-guarantee cubic variant — follows from the latter's stricter assumptions and extra machinery, mirroring the paper's own reading of its results.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A broader design lesson the paper only implies: because MINRES's 'NPC' certificate gives a principled response to negative curvature, the same swap from CG to a residual-certifying solver is likely to help in other settings with indefinite Newton systems, such as equality-constrained or semidefinite problems.
  • The implementation's dynamic MINRES tolerance (Section 3.1.2) has no explicit grade cap, so the certified 'SOL'/'NPC' dichotomy that Theorem 2.15 relies on can fail on indefinite or very large problems; adding a grade-based stopping rule and re-running the benchmarks would test whether the ε^-3/2 rate survives in practice.
  • A third algorithmic variant, not tried here, would use the certified within-face descent alone with a cheaper face-exit than cubic regularization; its performance would isolate how much of Algorithm T's machinery is actually needed.
  • The practical advantage of Algorithm P over Gencan could compound inside an augmented Lagrangian loop, where many subproblems are warm-started; the paper names this as future work without testing it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes two active-set algorithms for bound-constrained minimization of nonconvex C^2 functions. Algorithm P (Algorithms 1–3) uses MINRES-based descent directions inside the current face with Armijo backtracking, and a monotone Spectral Projected Gradient step for leaving faces; under A1–A2 it is shown to return an ε-approximate stationary point in at most (1+n)(f(x0)-flow)κ1^{-1}ε^{-2} iterations, hence O(nε^{-2}) oracle calls. Algorithm T (Algorithms 4–6) uses a certified MINRES direction inside faces and a cubic-regularization iteration for escapes; under A1–A3 it is claimed to require O(n|log ε|ε^{-3/2}) oracle calls. Numerical experiments on 475 CUTEst problems compare variants and show that Algorithm P is more robust and efficient than Algorithm T and than Gencan.

Significance. If the theory is sound, the paper provides the first worst-case complexity guarantees for bound-constrained truncated-Newton methods using MINRES, and the O(ε^{3/2}) descent inside faces without cubic regularization is an interesting contribution. The algorithms are concrete, the Fortran code is made available, and the experiments cover the full CUTEst collection and compare with a well-established code. The O(nε^{-2}) result for Algorithm P is supported by the proofs and by the numerical evidence. However, the O(n|log ε|ε^{-3/2}) theorem currently has two proof gaps and a mismatch between the theorem's hypotheses and the implemented Algorithm T. These issues are local and seem fixable, but they must be addressed before the main complexity claim can be accepted as stated.

major comments (3)
  1. [Section 2.2 (after eq. (29)), Algorithm 5 Step 1, Section 3.1.2] The proof of Theorem 2.15 relies on every MINRES call returning a certified 'SOL' or 'NPC' output satisfying (26)–(29). This is stated as an assumption 'throughout the remainder of our analysis' immediately after (29). Lemmas 2.9, 2.12 and 2.13, and hence the O(ε^{3/2}) decrease and Theorem 2.15, depend on that dichotomy. The implementation described in Section 3.1.2 stops MINRES with a dynamic residual tolerance and does not cap the iteration count at the grade, so the implemented Algorithm T may exit before the grade. Then the output need not satisfy (26)–(29), and the proof of Theorem 2.15 does not apply to Algorithm T as implemented. The authors should either (a) include an explicit grade cap in Algorithm 5 and in the implementation, and define behavior when the grade is exceeded (e.g. fall back to the correction used for Flag=1), or (b) restate Theorem 2.15 as a guarantee for an ide
  2. [Theorem 2.15, proof around eq. (79)] For k in S^(1) the proof uses (78), ∥∇Ωf(xk)∥ > ε, to conclude f(xk)-f(xk+1) ≥ κ2 ε^{3/2}. This is valid for iterates produced by Algorithm 5, because Lemmas 2.9, 2.12 and 2.13 give lower bounds in terms of ∥∇^I f(xk)∥. But for an iterate produced by Algorithm 6, the imported Lemma 2.14 bounds the decrease by a multiple of ∥∇Ωf(x_{k+1})∥^{3/2}, not ∥∇Ωf(x_k)∥^{3/2}. If k = T(ε)-1 and Algorithm 6 is used, then x_{k+1} = x_{T(ε)} and ∥∇Ωf(x_{k+1})∥ ≤ ε, so (79) need not hold. The final S^(1) step should be excluded from the count and absorbed into the additive constant, or handled by a separate argument. The theorem already has an additive (n+1), so this appears fixable.
  3. [Lemma 2.10 (Section 2.2)] In the Dtype='SOL' case, the proof writes f(x0)-flow ≥ ραη∥d∥² ≥ (ρ/2)(η/Lg)α∥∇^I f(xk)∥². Combining with (62), which gives ∥∇fxk(0)∥ ≤ 2Lg∥dk∥, yields instead ραη∥d∥² ≥ ρη/(4Lg²)α∥∇^I f(xk)∥². Thus the constant in (69) for the SOL case appears too small by a factor of order Lg. With the corrected constant the conclusion remains of the form α ≤ O(ε^{-2}), so the subsequent O(|log ε|) oracle-call bound is unchanged in order; nevertheless, the displayed inequality and constant should be corrected.
minor comments (5)
  1. [Theorem 2.5 proof, after eq. (22)] When x_{k+1} is computed by Algorithm 3, the cited result should be Lemma 2.4, not Lemma 2.3.
  2. [Section 3.2/3.3] The parameter tuning with irace is performed on a 20% training subset, but the subsequent robustness/efficiency tables and profiles are reported on all 475 problems, including the training set. Reporting results on a held-out test set, or at least flagging the possible tuning bias, would strengthen the conclusions.
  3. [Section 2.2, paragraph after (29)] The paper relies on Lemmas 11–13 of [21], an arXiv technical report, for the MINRES SOL/NPC dichotomy. If a peer-reviewed version exists, it should be cited; otherwise the authors should state the precise version of the report used.
  4. [Figure 1 / Figure 2 captions] The captions state 402 and 434 problems, but the surrounding text gives numbers such as 401 and 434 without explicit intersection counts. Please reconcile the counts and define precisely how the 'both found equivalent values' set is computed.
  5. [Algorithm 2, Steps 2.2/2.3 and Section 3.1.3] The theoretical statements say 'using at most m oracle calls, find xk+1 ∈ ∂F(xk)'; the practical extrapolation description in Section 3.1.3 should make explicit how the m-call budget is respected when projection does not land exactly on the boundary.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity theorems are derived in-paper from explicit assumptions and published external lemmas; no fitted quantity is renamed as a prediction.

full rationale

The derivation chain is self-contained modulo standard, published results. Theorem 2.5 combines Lemma 2.3 (proved in the paper from Assumption A1 and Armijo descent) with Lemma 2.4, imported as Theorem 4.2 of [7]. That SPG decrease bound is a parameter-free, published result whose assumptions (A1) do not include the target complexity bound, so it is independent support rather than circular self-citation. Theorem 2.15 similarly combines Lemma 2.9, proved in the paper under the explicit MINRES grade dichotomy (26)-(29) and Assumptions A1-A3, with Lemma 2.14, imported from Lemma 3.4 of [6]; again the cited lemma is a published, parameter-free regularized-method decrease bound that does not assume the paper's O(n |log eps| eps^{-3/2}) result. The MINRES grade assumption is explicitly stated as an assumption, not derived from the theorem it supports, so its possible violation by the implemented tolerance in Section 3.1.2 is a correctness/robustness gap, not circularity. No fitted parameter is later called a prediction: irace tuning is performed on a training subset and the methods are then tested on the CUTEst collection against Gencan, an external benchmark. The conclusion's caveat that the stronger assumptions are 'difficult to verify in practice' is a stated limitation, not a circular step. Overall, the novelty—bound-constrained Newton-MR with these complexity guarantees—is derived from stated hypotheses and independent lemmas, with no reduction of the conclusion to its inputs.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central complexity claims rest on three standard regularity assumptions (A1-A3), the imported MINRES SOL/NPC dichotomy from [21], and the imported subproblem-solution conditions from [6]. Problem constants Lg, LH, f_low, f(x0) are inputs, not fitted parameters; the user-set algorithmic constants only rescale the explicit constants kappa1 and kappa2. No data were fitted and no invented entities are introduced; the Flag/sigma_k state variables and MINRES outputs are algorithmic bookkeeping.

free parameters (2)
  • Algorithm P constants = theta=0.1, rho=1e-4, a1=1e8, a2=1e-16, lambda_spg_min=1e-16, lambda_spg_max=1e16, m=20, epsilon_mr_ini=0.1
    Values from the literature and from irace tuning on a 20% training split (Section 3.2.1). The theorems hold for any values in the stated ranges; the constants kappa1 and kappa2 and log factors depend on them. Not fitted to make the derivation work.
  • Algorithm T constants = theta=0.1, eta=1e-8, eta0=eta, tau=0.9, rho=1e-4, alpha=1e-8, gamma=1, m=20 (M, a1, a2 not reported)
    Set from the literature and by irace (Section 3.2.2); tau is moot once eta0 = eta. Same role as above: user-supplied constants that rescale the explicit constants in the bounds.
assumptions (6)
  • domain assumption A1: gradient of f is Lg-Lipschitz continuous on R^n
    Standard smoothness regularity. Enters every stepsize lower bound (Lemmas 2.2, 2.3, 2.7-2.13) through the descent/Taylor inequality (12), (42), (50), and the bounds ||Hessian|| <= Lg in (62), (67).
  • domain assumption A2: f is bounded below by f_low
    Used in Theorems 2.5 and 2.15 to convert per-iteration decrease into a finite iteration count via f(x0) - f(xk) <= f(x0) - f_low (see (24) and (81)).
  • domain assumption A3: Hessian of f is LH-Lipschitz continuous
    Needed for the cubic Taylor bound (40), the O(epsilon^{3/2}) decrease bounds of Lemmas 2.9, 2.12, 2.13 and 2.14, and Theorem 2.15. Only Algorithm T needs it.
  • domain assumption MINRES termination within the grade of the least-squares problem (SOL/NPC dichotomy)
    Stated in Section 2.2 after (29): 'we shall assume ... the number of iterations does not exceed the grade'. The characterizations (26)-(29) underpin the Flag = 0 cases of Lemma 2.9 and hence Theorem 2.15. The implementation (Section 3.1.2) does not describe a grade cap.
  • domain assumption Approximate cubic subproblem solutions satisfying Algorithm 6 Step 1 conditions exist and are computable
    Algorithm 6 requires s_l with T2(xk, s_l) + (2^l M_k) ||s_l||^3 <= 0 and the projected-gradient condition; the decrease bound (74) is imported as Lemma 3.4 from [6].
  • standard math Standard projection and linear-algebra facts: Q(x)^T Q(x) = I, projection properties, descent lemma for L-Lipschitz gradients
    Used throughout (e.g., (2), (12), Lemma 2.2). Standard background for the field; no ad hoc content.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Active-set Newton-MR methods for nonconvex optimization problems with bound constraints." pith.science (2026). https://pith.science/paper/ZKYLIMNS

@misc{pith2026250820967,
  author       = {Pith},
  title        = {Pith review of: Active-set Newton-MR methods for nonconvex optimization problems with bound constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZKYLIMNS}},
  note         = {Machine review of arXiv:2508.20967}
}
abstract

This paper presents active-set methods for minimizing nonconvex twice-continuously differentiable functions subject to bound constraints. Within the faces of the feasible set, we employ descent methods with Armijo line search, utilizing approximated Newton directions obtained through the Minimum Residual (MINRES) method. To escape the faces, we investigate the use of the Spectral Projected Gradient (SPG) method and a tailored variant of the Cubic Regularization of Newton's method for bound-constrained problems. We provide theoretical guarantees, demonstrating that when the objective function has a Lipschitz continuous gradient, the SPG-based method requires no more than $\mathcal{O}(n\epsilon^{-2})$ oracle calls to find $\epsilon$-approximate stationary points, where $n$ is the problem dimension. Furthermore, if the objective function also has a Lipschitz continuous Hessian, we show that the method based on cubic regularization requires no more than $\mathcal{O}\left(n|\log_{2}(\epsilon)|\epsilon^{-3/2}\right)$ oracle calls to achieve the same goal. We emphasize that, under certain hypotheses, the method achieves $O(\epsilon^{3/2})$ descent within the faces without resorting to cubic regularization. Numerical experiments are conducted to compare the proposed methods with existing active-set methods, highlighting the potential benefits of using MINRES instead of the Conjugate Gradient (CG) method for approximating Newton directions.

Figures

Figures reproduced from arXiv: 2508.20967 by the authors.

Figure 1
Figure 1. Performance profiles comparing the efficiency of Alg [PITH_FULL_IMAGE:figures/full_fig_p025_1.png] view at source ↗
Figure 2
Figure 2. Performance profiles comparing the efficiency of Alg [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  1. [1]

    Andreani, E

    R. Andreani, E. G. Birgin, J. M. Mart ´ ınez, and M. L. Schuv erdt. On augmented Lagrangian methods with general lower-level constraints. SIAM Journal on Optimization , 18(4):1286–1309, 2008

  2. [2]

    Andretta, E

    M. Andretta, E. G. Birgin, and J. M. Mart ´ ınez. Practical active-set euclidian trust-region method with spectral projected gradients for bound-constr ained minimization. Optimization, 54(3):305–325, 2005

  3. [3]

    E. G. Birgin and J. M. Gentil. Evaluating bound-constrai ned minimization software. Compu- tational Optimization and Applications , 53(2):347–373, 2012

  4. [4]

    E. G. Birgin and J. M. Mart ´ ınez. Large-scale active-set box-constrained optimization method with spectral projected gradients. Computational Optimization and Applications , 23(1):101–125, 2002

  5. [5]

    E. G. Birgin and J. M. Mart ´ ınez. Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadel phia, PA, 2014

  6. [6]

    E. G. Birgin and J. M. Mart ´ ınez. On regularization and ac tive-set methods with complexity for constrained optimization. SIAM Journal on Optimization , 28(2):1367–1395, 2018

  7. [7]

    E. G. Birgin and J. M. Mart ´ ınez. Complexity and performa nce of an augmented Lagrangian algorithm. Optimization Methods and Software , 35(5):885–920, 2020

  8. [8]

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

Show all 25 references
  1. [9]

    T. F. Coleman and Y. Li. On the convergence of interior-re flective Newton methods for nonlinear minimization subject to bounds. Mathematical Programming, 67(1–3):189–224, 1994

  2. [10]

    T. F. Coleman and Y. Li. An interior trust region approac h for nonlinear minimization subject to bounds. SIAM Journal on Optimization , 6(2):418–445, 1996

  3. [11]

    A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Lancelot: A Fortran package for large scale nonlinear optimization. Springer-Verlag, Berlin, Heidelberg, 1992

  4. [12]

    Dahito and D

    M-A. Dahito and D. Orban. The conjugate residual method in linesearch and trust-region methods. SIAM Journal on Optimization , 29(3):1988–2025, 2019

  5. [13]

    E. D. Dolan and J. J. Mor´ e. Benchmarking optimization s oftware with performance profiles. Mathematical Programming, 91(2):201–213, 2002

  6. [14]

    Facchinei, S

    F. Facchinei, S. Lucidi, and L. Palagi. A truncated Newt on algorithm for large scale box constrained optimization. SIAM Journal on Optimization , 12(4):1100–1125, 2002

  7. [15]

    N. I. M. Gould, D. Orban, and Ph. L. Toint. CUTEst: a const rained and unconstrained testing environment with safe threads for mathematical optimizati on. Computational Optimization and Applications, 60(3):545–557, 2014

  8. [16]

    W. W. Hager and H. Zhang. A new active set algorithm for bo x constrained optimization. SIAM Journal on Optimization , 17(2):526–557, 2006

  9. [17]

    Heinkenschloss, M

    M. Heinkenschloss, M. Ulbrich, and S. Ulbrich. Superli near and quadratic convergence of affine- scaling interior-point Newton methods for problems with si mple bounds without strict comple- mentarity assumption. Mathematical Programming, 86(3):615–635, 1999

  10. [18]

    Lin and J

    C.-J. Lin and J. J. Mor´ e. Newton’s method for large boun d-constrained optimization problems. SIAM Journal on Optimization , 9(4):1100–1127, 1999

  11. [19]

    Liu and F

    Y. Liu and F. Roosta. Convergence of Newton-MR under ine xact hessian information. SIAM Journal on Optimization , 31(1):59–90, 2021

  12. [20]

    Liu and F

    Y. Liu and F. Roosta. MINRES: From negative curvature de tection to monotonicity properties. SIAM Journal on Optimization , 32(4):2636–2661, 2022

  13. [21]

    Liu and F

    Y. Liu and F. Roosta. A Newton-MR algorithm with complex ity guarantees for nonconvex smooth unconstrained optimization. Technical report, arX iv:2208.07095v2, 2023

  14. [22]

    L´ opez-Ib´ a˜ nez, J

    M. L´ opez-Ib´ a˜ nez, J. Dubois-Lacoste, L. P. C´ aceres, T. St¨ utzle, and M. Birattari. The irace pack- age: Iterated racing for automatic algorithm configuration . Operations Research Perspectives, 3:43–58, 2016

  15. [23]

    Algorithm 778: L -BFGS-B: Fortran subroutines for large-scale bound constrained optimization

    J. L. Morales and J. Nocedal. Remark on “Algorithm 778: L -BFGS-B: Fortran subroutines for large-scale bound constrained optimization”. ACM Transactions on Mathematical Software , 38(1):1–4, 2011

  16. [24]

    C. C. Paige and M. A. Saunders. Solution of sparse indefin ite systems of linear equations. SIAM Journal on Numerical Analysis , 12(4):617–629, 1975. 28

  17. [25]

    W¨ achter and L

    A. W¨ achter and L. T. Biegler. On the implementation of a n interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25–57, 2005. 29

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.