An arc-search BFGS algorithm for unconstrained nonlinear optimization problems

Yaguang Yang · 2026

Read An arc-search BFGS algorithm for unconstrained nonlinear optimization problems by Yaguang Yang (2026) 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-2606-01506.txt.

Introduction

Yang adds an arc search to the BFGS method for nonlinear optimization. BFGS is a classic method for unconstrained problems. It works well on convex problems. On non-convex ones, it may fail to converge in a reliable way. Modified BFGS variants handle both classes of problems. A robust BFGS variant is known for global convergence. It also has fast local convergence, at a superlinear rate, under mild assumptions.

Yang aims to cut the cost of that robust variant. An arc search replaces the usual line search step. The good convergence traits of the robust method are kept. Tests compare the new method with state-of-the-art rivals. The reported results favor the arc-search version on efficiency.

Catalog record

CREATORYaguang Yang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01506

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An arc-search BFGS algorithm for unconstrained nonlinear optimization problems Yaguang Yang Abstract The classical BFGS algorithm performs excellently for convex optimization problems. However, for non-convex problems, the classical BFGS method may fail to converge reliably. To overcome this limitation, researchers have developed modified BFGS methods that are applicable to both convex and non-convex optimization problems. Among these methods, a robust BFGS algorithm has been shown to achieve global convergence and fast local convergence, with a superlinear convergence rate, for both convex and non-convex nonlinear optimization problems under mild assumptions. In this paper, we propose an arc-search BFGS algorithm that aims to further improve the computational efficiency of the robust BFGS method while preserving its desirable convergence properties. Numerical experiments are carried out, and performance comparisons between the proposed algorithm and state-of-the-art algorithms are reported to demonstrate the advantages of the arc-search BFGS algorithm. keywords: arc-search BFGS algorithm, global convergence, superlinear convergence, unconstrained optimization. AMS subject classifications: 90C30. 1 Introduction BFGS algorithm, introduced in the seminal works of C. G. Broyden, R. Fletcher, D. Goldfarb, and D. F. Shanno [ 2 , 5 , 6 , 23 ] , is one of the most successful algorithms for unconstrained optimization problems. The algorithm is globally convergent when the objective function is convex [ 20 ] . However, for nonconvex objective functions, Y.-H. Dai showed in [ 3 ] that the classical BFGS method may fail to converge. Consequently, many modified BFGS methods have been proposed; see, for example, [ 15 , 16 , 35 , 37 , 39 , 40 ] and the references therein. Among these approaches, the robust BFGS method proposed in [ 35 ] (based on an idea of [ 32 ] ) has been shown to possess desirable theoretical properties, including global convergence and a local superlinear convergence rate. Moreover, preliminary numerical experiments reported in [ 35 ] demonstrate that it outperforms several state-of-the-art algorithms. The goal of this paper is to further improve the efficiency and effectiveness of the robust BFGS method while preserving its favorable convergence properties. To this end, we view the unconstrained optimization problem as a special case of a constrained optimization problem with box constraints, where each variable satisfies x_{i}\in(-\infty,\infty),~i=1,2,…,n . Under this perspective, unconstrained optimization can be treated within a unified constrained optimization framework, which provides additional flexibility for designing modified quasi-Newton updating strategies. Within this framework, every iterate is an interior point, which naturally connects unconstrained optimization algorithms to the Interior-point method (IPM). Developed in the 1980s, widely popularized in the 1990s, and now recognized as one of the most efficient approaches for constrained optimization [ 17 , 20 , 34 ] , IPMs have been extensively studied in the literature. More recently, it has been shown that arc-search interior-point methods possess superior convergence properties compared with traditional line-search interior-point methods for linear optimization [ 11 , 33 ] , convex quadratic optimization [ 31 , 41 ] , symmetric optimization [ 12 , 21 , 30 ] , linear complementarity problems [ 22 , 38 ] , semidefinite optimization [ 13 , 14 , 42 ] , and nonlinear optimization [ 29 , 36 ] . In addition, the author showed in [ 33 ] that an arc-search interior-point method not only achieves the best known polynomial complexity bound for linear optimization problems, but is also competitive with Mehrotra’s algorithm, which has been implemented in many state-of-the-art optimization software packages [ 28 ] . This resolves a long-standing dilemma discussed in [ 25 , 28 , 34 ] , namely, how to design an interior-point method based on arc-search techniques that simultaneously achieves strong theoretical polynomial complexity and excellent practical computational performance. Motivated by the success of the arc-search in IPM, we propose an arc-search BFGS algorithm that combines the advantages of the robust BFGS framework with those of arc-search techniques. We show that the proposed arc-search algorithm naturally satisfies the Wolfe conditions, thereby eliminating the need for a complicated procedure described in [ 18 ] , which is typically essential for ensuring convergence [ 20 ] . Furthermore, we establish the global convergence and superlinear convergence rate of the proposed method. Numerical experiments on standard CUTEst benchmark set problems demonstrate that the proposed arc-search BFGS algorithm is highly promising in practice. Throughout the paper, we use lowercase bold font for vectors, uppercase bold font for matrices, standard font for scalars. To save the space, we use {\bf x}=(x_{1},x_{2},\ldots,x_{n}) for column vector {\bf x} . Therefore, we define by \nabla_{{\bf x}}f({\bf x})=(\frac{df}{dx_{1}},\frac{df}{dx_{2}},\ldots\frac{df}{dx_{n}}) or simply \nabla_{{\bf x}}f for the gradient of f({\bf x}) , by {\bf H}({\bf x})=\nabla_{{\bf x}}^{2}f({\bf x}) or simply {\bf H} for the Hessian of f({\bf x}) . We denote {\bf H}\succ{\bf 0} if a matrix {\bf H} is positive definite, {\bf H}\succeq{\bf 0} if {\bf H} is positive semi-definite. We use superscript k to represent the value of a vector (or a matrix) at the k th iteration while use the subscript i ( ij ) to represent the i element ( ij element) of the vector (or the matrix), and subscript k for the value of the scalar at the k iteration while use the superscript for the power of the scalar. Hence, {\bf x}^{0} is used to represent the initial point of the algorithm and \alpha_{0} is the initial value of \alpha . The remainder of the paper is organized as follows. Section 2 introduces the arc-search BFGS algorithm. Section 3 discusses the algorithm’s convergence properties. Section 4 provides the detailed implementation information. Section 5 includes the test results and comparison of proposed algorithm with the established ones. Section 6 summarizes the conclusions. 2 The arc-search BFGS Method This paper proposes an arc-search algorithm to minimize a general (convex or nonconvex) multi-variable nonlinear function \min f({\bf x}), (1) where f:\mathbb{R}^{n}\rightarrow\mathbb{R} is a twice differentiable function of {\bf x}\in\mathbb{R}^{n} . Let \nabla_{{\bf x}}f({{\bf x}}) and {\bf H}({\bf x}) be the gradient and Hessian matrix of f({\bf x}) respectively. We denote by \bar{{\bf x}} a local minimizer of ( 1 ) that satisfies \nabla_{{\bf x}}f(\bar{{\bf x}})={\bf 0}. (2) Following the practice of [ 20 ] , we make the standard assumptions on f({\bf x}) which will be used in the convergence analysis. Assumptions: 1. For an open set {\cal M} containing the level set {\cal L}=\{{\bf x}:f({\bf x})\leq f({\bf x}^{0})\} , \nabla f({\bf x}) is Lipschitz continuous, i.e., there exists a constant L>0 such that \|\nabla f({\bf x})-\nabla f({\bf y})\|\leq L\|{\bf x}-{\bf y}\|, (3) for all {\bf x},{\bf y}\in{\cal M} . 2. There are positive numbers \delta>0 , 0<m<1<M , and a neighborhood of \bar{{\bf x}} , defined by {\cal N}(\bar{{\bf x}})=\{{\bf x}:f({{\bf x}})-f(\bar{{\bf x}})\leq\delta\} , such that for all {\bf x}\in{\cal N}(\bar{{\bf x}}) and for all {\bf z}\in\mathbb{R}^{n} , m\|{\bf z}\|^{2}\leq{\bf z}^{{\rm T}}{\bf H}({\bf x}){\bf z}\leq M\|{\bf z}\|^{2}. (4) 3. There is a positive number L>0 such that for all {\bf x}\in{\cal N}(\bar{{\bf x}}) , \|{\bf H}({\bf x})-{\bf H}(\bar{{\bf x}})\|\leq L\|{\bf x}-\bar{{\bf x}}\|. (5) 4. The summation of the distances between the iterates and optimizer is bounded, i.e., \sum_{k=1}^{\infty}\|{\bf x}^{k}-\bar{{\bf x}}\|<\infty. (6) Assumption 1 [ 20 , (3.13)] is required when applying the Zoutendijk theorem to establish the global 1 1 1 We say an algorithm

Read the complete text