Active-set Newton-MR methods for nonconvex optimization problems with bound constraints
Ernesto G. Birgin, Geovani N. Grapiglia, Diaulas S. Marcondes · 2025
Read Active-set Newton-MR methods for nonconvex optimization problems with bound constraints by Ernesto G. Birgin, Geovani N. Grapiglia, Diaulas S. Marcondes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20967.txt.
Introduction
Ernesto Birgin, Geovani Grapiglia, and Diaulas Marcondes design in 2025 faster ways to minimize bumpy functions whose variables must stay within bounds. Such problems appear across engineering and data work. Their methods combine active-set logic, which fixes variables sitting at their limits, with Newton steps solved cheaply by an iterative solver.
Two escape routes from flat faces are studied: a spectral gradient method and a cube-regularized Newton variant. The authors prove how many function calls each needs to reach a near-stationary point, with the second scaling better in accuracy. Computer tests against existing methods favor their approach, and the cheap solver beat the standard one for Newton directions.
Catalog record
| CREATOR | Ernesto G. Birgin, Geovani N. Grapiglia, Diaulas S. Marcondes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20967
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Active-set Newton-MR methods for nonconvex optimization problems with bound constraints Thanks: This work has been partially supported by the Brazilian agencies FAPESP (grants 2013/07375-0, 2022/05803-3, 2023/08706-1, and 2024/22384-0) and CNPq (grant 302073/2022-1). Ernesto G. Birgin, Geovani N. Grapiglia, Diaulas S. Marcondes 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 𝒪 ( n ϵ − 2 ) \mathcal{O}(n\epsilon^{-2}) oracle calls to find ϵ \epsilon -approximate stationary points, where n 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 𝒪 ( n | log 2 ( ϵ ) | ϵ − 3 / 2 ) \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 ( ϵ 3 / 2 ) 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. Keywords: Bound-constrained minimization, minimal residual method (MINRES), active-set methods, complexity, numerical experiments. 1 Introduction The optimization problem entails finding a solution that satisfies given constraints while minimizing a specified objective function. This type of problem has far-reaching applications in various fields, including psychology, medicine, economics, engineering, physics, and biology, to name a few. In this work, we focus on cases where the functions that define the feasible region and the objective function are continuous and differentiable. Among the methods developed to address such problems, augmented Lagrangians deserve special attention. Of the existing implementations, Algencan [ 1 , 5 , 7 ] is one of the most efficient and robust. It solves a sequence of bound-constrained problems using Gencan [ 4 ] . When Hessians are not available or available as an operator, Gencan computes approximate Newtonian directions using conjugate gradients. Recent studies [ 12 , 19 , 20 , 21 ] have highlighted the theoretical properties and practical performance of Newtonian methods for unconstrained minimization, which leverage the minimal residual method (MINRES) [ 24 ] to solve linear Newtonian systems. Motivated by these results, and having in mind subproblems in augmented Lagrangian methods, in this work, we propose Newton-MR methods for bound-constrained minimization. The development of methods for minimization with bound constraints is a vibrant and dynamic field. During the past decades, numerous methods have been devised; see, for example, [ 2 , 4 , 14 , 16 , 17 , 18 , 23 ] and the references therein. A comprehensive numerical comparison of freely available software packages was presented in [ 3 ] . The methods proposed here follow the active set paradigm. Specifically, we propose two distinct extensions of the Newton-MR method from [ 21 ] for minimization with bound constraints. In [ 21 ] , the method achieves a worst-case iteration complexity of \mathcal{O}(\epsilon^{-3/2}) to find a point x such that \|\nabla f(x)\|\leq\epsilon when minimizing f(x) over x\in\mathbb{R}^{n} . Our first proposed extension, which introduces greater flexibility in algorithmic choices, takes no more than \mathcal{O}(n\epsilon^{-2}) calls to the oracle to find a point x such that \|P_{\Omega}(x-\nabla f(x))-x\|\leq\epsilon when applied to the problem of minimizing f(x) subject to x\in\Omega , where \Omega is the feasible set defined by the bound constraints. The second extension takes no more than \mathcal{O}(n|\log_{2}(\epsilon)|\epsilon^{-3/2}) calls to the oracle to achieve the same goal. Numerical experiments demonstrate that the first option is more robust and efficient compared to the second, using both unconstrained and bound-constrained minimization problems from the CUTEst collection [ 15 ] . Additional experiments also show that the first version outperforms Gencan, particularly when second derivatives are available but matrix factorizations are not. The remainder of this paper is organized as follows. The two Newton-MR-based methods for bound-constrained minimization and their theoretical properties are described in Section 2 . Numerical experiments are presented and analyzed in Section 3 . Conclusions and directions for future work are presented in the final section. 2 Problem definition and new methods Consider the problem Minimize f(x) subject to x\in\Omega , where \Omega=\left\{x\in\mathbb{R}^{n}\,:\,\ell\leq x\leq u\right\} , with \ell_{i}<u_{i} for i=1,\dots,n , and f:\mathbb{R}^{n}\to\mathbb{R} being a twice continuously differentiable function. Specifically, let us assume that A1. \nabla f:\mathbb{R}^{n}\to\mathbb{R}^{n} is L_{g} -Lipschitz continuous. A2. f(\,\cdot\,) is bounded from below by f_{\mathrm{low}} . Denoting [n]:=\left\{1,\ldots,n\right\} , for any x\in\Omega , define the sets \mathcal{A}_{0}(x)=\{j\in[n]:x_{j}=\ell_{j}\} , \mathcal{A}_{1}(x)=\{j\in[n]:x_{j}=u_{j}\} , \mathcal{A}(x)=\mathcal{A}_{0}(x)\cup\mathcal{A}_{1}(x) , and \mathcal{I}(x)=\left\{1,\dots,n\right\}\setminus\mathcal{A}(x) . The face to which x\in\Omega belongs is the set \mathcal{F}(x)=\left\{z\in\Omega:z_{i}=\ell_{i}\text{ if }i\in\mathcal{A}_{0}(x),z_{i}=u_{i}\text{ if }i\in\mathcal{A}_{1}(x),\,\ell_{i}<z_{i}<u_{i}\text{ otherwise}\right\}. The reduced gradient of f at x with respect to \Omega is defined by \nabla_{\Omega}f(x)=x-P_{\Omega}(x-\nabla f(x)), where P_{\Omega}(\,\cdot\,) is the projection operator onto \Omega . Let \nabla_{\Omega}^{I}f(x)\in\mathbb{R}^{n} be the vector defined by \left[\nabla_{\Omega}^{I}f(x)\right]_{i}=[\nabla_{\Omega}f(x)]_{i} , if i\in\mathcal{I}(x) , and \left[\nabla_{\Omega}^{I}f(x)\right]_{i}=0 , otherwise. Considering the enumeration \mathcal{I}(x)=\left\{i_{1},\dots,i_{|\mathcal{I}(x)|}\right\} , with i_{j}<i_{j+1} for j=1,\dots,|\mathcal{I}(x)|-1 when |\mathcal{I}(x)|\geq 2 , let us define Q(x)=\left[e_{i_{1}}\,\,\dots\,\,e_{i_{|\mathcal{I}(x)|}}\right]\in\mathbb{R}^{n\times|\mathcal{I}(x)|} , where e_{i} denotes the i -th vector of the canonical basis of \mathbb{R}^{n} . In what follows, we will consider the function f_{x}:\mathbb{R}^{|\mathcal{I}(x)|}\to\mathbb{R} given by f_{x}(y)=f(x+Q(x)y). (1) We have \nabla f_{x}(y)=Q(x)^{T}\nabla f(x+Q(x)y) and \nabla^{2}f_{x}(y)=Q(x)^{T}\nabla^{2}f(x+Q(x)y)Q(x) , and so \nabla f_{x}(0)=Q(x)^{T}\nabla f(x)\quad\text{and}\quad\nabla^{2}f_{x}(0)=Q(x)^{T}\nabla^{2}f(x)Q(x). (2) 2.1 Method that employs SPG for leaving faces Our first method (Algorithm 1) is inspired by Algorithm 4.1 in [ 6 ] . In its k th iteration, we check whether the gradient norm in the current face, \|\nabla_{\Omega}^{I}f(x^{k})\| , is greater than or equal to a multiple of the reduced gradient norm, \|\nabla_{\Omega}f(x^{k})\| . If this condition holds, then x^{k+1} is computed using Algorithm 2, which performs one iteration of a descent method on f_{x^{k}} , where the descent direction is obtained by MINRES. Otherwise, x^{k+1} is computed by Algorithm 3, which applies a monotone iteration of the Spectral Projected Gradient (SPG) method [ 8 ] to the minimization of f in \Omega . Algorithm 1. Active-Set Newton-MR method with SPG Step 0. Given x^{0}\in\Omega , \epsilon>0 , \theta\in(0,1] , \rho\in(0,1) , m\in\mathbb{N} , a_{1}\geq 1 , a_{2}\in(0,1) , \lambda_{\max}^{\mathrm{spg}}\geq\lambda_{\min}^{\mathrm{spg}}>0 be given. Set k:=0 . Step 1. If \|\nabla_{\Omega}f(x^{k})\|\leq\epsilon , STOP. Step 2. If \left\|\nabla_{\Omega}^{I}f(x^{k})\right\|\geq\theta\|\nabla_{\Omega}f(x^{k})\| , compute x^{k+1} by applying Algorithm 2 with parameters x^{k} , \rho , m , a_{1} , and a_{2} . Otherwise, compute x^{k+1} by applying Algorithm 3 with parameters x^{k} , \rho , \lambda_{\max}^{\mathrm{spg}} , and \lambda_{\min}^{\mathrm{spg}} . Step 3. Set k:=k+1 and go to Step 1. Within faces, we apply Algorithm 2, which is a descent method with Armijo line search and extrapolation. To obtain the search direction, we first compute an approximate solution d_{1}^{k} to the minimum residual problem associated with the Newton system. This solution is then corrected to produce a direction d^{k} satisfying conditions \|d^{k}\|\leq