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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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
- [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.
- [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)
- [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.
- [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.
- [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.
- [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.
- [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
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
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
- 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)
assumptions (6)
- domain assumption A1: gradient of f is Lg-Lipschitz continuous on R^n
- domain assumption A2: f is bounded below by f_low
- domain assumption A3: Hessian of f is LH-Lipschitz continuous
- domain assumption MINRES termination within the grade of the least-squares problem (SOL/NPC dichotomy)
- domain assumption Approximate cubic subproblem solutions satisfying Algorithm 6 Step 1 conditions exist and are computable
- standard math Standard projection and linear-algebra facts: Q(x)^T Q(x) = I, projection properties, descent lemma for L-Lipschitz gradients
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
Reference graph
Works this paper leans on
-
[1]
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
work page 2008
-
[2]
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
work page 2005
-
[3]
E. G. Birgin and J. M. Gentil. Evaluating bound-constrai ned minimization software. Compu- tational Optimization and Applications , 53(2):347–373, 2012
work page 2012
-
[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
work page 2002
-
[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
work page 2014
-
[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
work page 2018
-
[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
work page 2020
-
[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
work page 2000
Show all 25 references
-
[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
1994
-
[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
1996
-
[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
1992
-
[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
1988
-
[13]
E. D. Dolan and J. J. Mor´ e. Benchmarking optimization s oftware with performance profiles. Mathematical Programming, 91(2):201–213, 2002
2002
-
[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
2002
-
[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
2014
-
[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
2006
-
[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
1999
-
[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
1999
-
[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
2021
-
[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
2022
-
[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
2023 arXiv
-
[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
2016
-
[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
2011
-
[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
1975
-
[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
2005
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.