Spectral Scaling BFGS Method

In this paper, we scale the quasiNewton equation and propose a spectral scaling BFGS method. The method has a good selfcorrecting property and can improve the behavior of the BFGS method. Compared with the standard BFGS method, the single-step convergence rate of the spectral scaling BFGS method will not be inferior to that of the steepest descent method when minimizing an n-dimensional quadratic function. In addition, when the method with exact line search is applied to minimize an n-dimensional strictly convex function, it terminates within n steps. Under appropriate conditions, we show that the spectral scaling BFGS method with Wolfe line search is globally and R-linear convergent for uniformly convex optimization problems. The reported numerical results show that the spectral scaling BFGS method outperforms the standard BFGS method.     

An adaptive scaled BFGS method for unconstrained optimization

A new adaptive scaled Broyden-Fletcher-Goldfarb-Shanno (BFGS) method for unconstrained optimization is presented. The third term in the standard BFGS update formula is scaled in order to reduce the large eigenvalues of the approximation to the Hessian of the minimizing function. Under the inexact Wolfe line search conditions, the global convergence of the adaptive scaled BFGS method is proved in very general conditions without assuming the convexity of the minimizing function. Using 80 unconstrained optimization test functions with a medium number of variables, the preliminary numerical experiments show that this variant of the scaled BFGS method is more efficient than the standard BFGS update or than some other scaled BFGS methods.     

Combination of steepest descent and BFGS methods for nonconvex nonsmooth optimization

In this paper, a method is developed for solving nonsmooth nonconvex minimization problems. This method extends the classical BFGS framework. First, we generalize the Wolfe conditions for locally Lipschitz functions and prove that this generalization is well defined. Then, a line search algorithm is presented to find a step length satisfying the generalized Wolfe conditions. Next, the Goldstein e-subgradient is approximated by an iterative method and a descent direction is computed using a positive definite matrix. This matrix is updated using the BFGS method. Finally, a minimization algorithm based on the BFGS method is described. The algorithm is implemented in MATLAB and numerical results using it are reported.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

A combined class of self-scaling and modified quasi-Newton methods

Techniques for obtaining safely positive definite Hessian approximations with self-scaling and modified quasi-Newton updates are combined to obtain ??better?? curvature approximations in line search methods for unconstrained optimization. It is shown that this class of methods, like the BFGS method, has the global and superlinear convergence for convex functions. Numerical experiments with this class, using the well-known quasi-Newton BFGS, DFP and a modified SR1 updates, are presented to illustrate some advantages of the new techniques. These experiments show that the performance of several combined methods are substantially better than that of the standard BFGS method. Similar improvements are also obtained if the simple sufficient function reduction condition on the steplength is used instead of the strong Wolfe conditions.     

A perfect example for the BFGS method

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.     

Quasi-Newton methods for multiobjective optimization problems

This work is an attempt to develop multiobjective versions of some well-known single objective quasi-Newton methods, including BFGS, self-scaling BFGS (SS-BFGS), and the Huang BFGS (H-BFGS). A comprehensive and comparative study of these methods is presented in this paper. The Armijo line search is used for the implementation of these methods. The numerical results show that the Armijo rule does not work the same way for the multiobjective case as for the single objective case, because, in this case, it imposes a large computational effort and significantly decreases the speed of convergence in contrast to the single objective case. Hence, we consider two cases of all multi-objective versions of quasi-Newton methods: in the presence of the Armijo line search and in the absence of any line search. Moreover, the convergence of these methods without using any line search under some mild conditions is shown. Also, by introducing a multiobjective subproblem for finding the quasi-Newton multiobjective search direction, a simple representation of the Karush–Kuhn–Tucker conditions is derived. The H-BFGS quasi-Newton multiobjective optimization method provides a higher-order accuracy in approximating the second order curvature of the problem functions than the BFGS and SS-BFGS methods. Thus, this method has some benefits compared to the other methods as shown in the numerical results. All mentioned methods proposed in this paper are evaluated and compared with each other in different aspects. To do so, some well-known test problems and performance assessment criteria are employed. Moreover, these methods are compared with each other with regard to the expended CPU time, the number of iterations, and the number of function evaluations.     

The BFGS method with exact line searches fails for non-convex objective functions

This work shows that the BFGS method and other methods in the Broyden class, with exact line searches, may fail for non-convex objective functions.     

BFGS算法对非凸函数优化问题的收敛性

ＢＦＧＳ算法是无约束最优化中最著名的数值算法之一,对非凸函数ＢＦＧＳ算法是否具有整体收敛性,这是一个ｏｐｅｎ问题,本文考虑Ｗｏｌｆｏ线搜索下目标函数非凸的ＢＦＧＳ算法,我们给出一个使该算法收敛的充分条件。     

CONVERGENCE PROPERTIES OF A MODIFIED BFGS ALGORITHM FOR MINIMIZATION WITHARMIJO-GOLDSTEIN STEPLENGTHS

1.IntroductionAssumethatwearefindingtheminimizerofthefollowingunconstrainedoptimizationproblemminf(x),(1.1)acReandassumethecurrentpointisxk'TOcalculatexk 1fromxkbyalinesearchmethod,thefollowingiterationXk 1~Xk Akpk,k~1,2,'(1.2)isapplied.IntheBFGSal...     

A Quasi-Newton Method with Wolfe Line Searches for Multiobjective Optimization

Journal of Optimization Theory and Applications - We propose a BFGS method with Wolfe line searches for unconstrained multiobjective optimization problems. The algorithm is well defined even for...     

非精确线性搜索条件下Broyden族方法总体收敛性的一种简单证明

This paper gives a simpler proof of the global convergence of Broyden class quasi-Newton method with inexact line search. This proof generalizes and modifies the proof of the global convergence of BFGS method by Nocedal and Wright in [3].     

Nonsmooth Equation Based BFGS Method for Solving KKT Systems in Mathematical Programming

In this paper, we present a BFGS method for solving a KKT system in mathematical programming, based on a nonsmooth equation reformulation of the KKT system. We split successively the nonsmooth equation into equivalent equations with a particular structure. Based on the splitting, we develop a BFGS method in which the subproblems are systems of linear equations with symmetric and positive-definite coefficient matrices. A suitable line search is introduced under which the generated iterates exhibit an approximate norm descent property. The method is well defined and, under suitable conditions, converges to a KKT point globally and superlinearly without any convexity assumption on the problem.     

一个带有线搜索的新信赖域方法及其收敛性

本文利用一个修正的BFGS公式,提出了一个结合Armijo线搜索条件技术的BFGS信赖域方法,并在一定条件下证明了该方法的全局收敛性和超线性收敛性.初步的数值实验结果表明该方法是有效的.     

解非线性对称方程组问题的具有下降方向的近似高斯-牛顿基础的BFGS方法

本本文给出了一个解非线性对称方程组问题的具有下降方向的近似高斯一牛顿基础BFGS方法。无论使用何种线性搜索此方法产生的方向总是下降的。在适当的条件下我们将证明此方法的全局收敛性和超线性收敛性。并给出数值检验结果。     

Global Convergence of Algorithms with Nonmonotone Line Search Strategy in Unconstrained Optimization

In this paper we state some nonmonotone line search strategies for unconstrained optimization algorithms. Abstracting from the concrete line search strategy we prove two general convergence results. Using this theory we can show the global convergence of the BFGS method with nonmonotone line search strategy. In contrast to some former results about nonmonotone line search strategies, both our convergence results and their proofs are natural generalizations of known results for the monotone case.     

Variational Methods for Non-Linear Least-Squares

We consider Newton-like line search descent methods for solving non-linear least-squares problems. The basis of our approach is to choose a method, or parameters within a method, by minimizing a variational measure which estimates the error in an inverse Hessian approximation. In one approach we consider sizing methods and choose sizing parameters in an optimal way. In another approach we consider various possibilities for hybrid Gauss-Newton/BFGS methods. We conclude that a simple Gauss-Newton/BFGS hybrid is both efficient and robust and we illustrate this by a range of comparative tests with other methods. These experiments include not only many well known test problems but also some new classes of large residual problem.     

Global convergence of BFGS and PRP methods under a modified weak Wolfe–Powell line search

The BFGS method is one of the most effective quasi-Newton algorithms for optimization problems. However, its global convergence for general functions is still open. In this paper, under a new line search technique, this problem is solved, and it is shown that other methods in the Broyden class also possess this property. Moreover, the global convergence of the PRP method is established in the case of this new line search. Numerical results are reported to show that the new line search technique is competitive to that of the normal line search.     

On the sufficient descent property of the Shanno’s conjugate gradient method

Satisfying in the sufficient descent condition is a strength of a conjugate gradient method. Here, it is shown that under the Wolfe line search conditions the search directions generated by the memoryless BFGS conjugate gradient algorithm proposed by Shanno satisfy the sufficient descent condition for uniformly convex functions.     

建立在修正BFGS公式基础上的新的共轭梯度法

共轭梯度法是一类非常重要的用于解决大规模无约束优化问题的方法. 本文通过修正的BFGS公式提出了一个新的共轭梯度方法. 该方法具有不依赖于线搜索的充分下降性. 对于一般的非线性函数, 证明了该方法的全局收敛性. 数值结果表明该方法是有效的.