Adaptive nonmonotone line search method for unconstrained optimization

In this paper, an adaptive nonmonotone line search method for unconstrained minimization problems is proposed. At every iteration, the new algorithm selects only one of the two directions: a Newton-type direction and a negative curvature direction, to perform the line search. The nonmonotone technique is included in the backtracking line search when the Newton-type direction is the search direction. Furthermore, if the negative curvature direction is the search direction, we increase the steplength under certain conditions. The global convergence to a stationary point with second-order optimality conditions is established. Some numerical results which show the efficiency of the new algorithm are reported.      

A new subspace minimization conjugate gradient method with nonmonotone line search for unconstrained optimization

A new subspace minimization conjugate gradient algorithm with a nonmonotone Wolfe line search is proposed and analyzed. In the scheme, we propose two choices of the search direction by minimizing a quadratic approximation of the objective function in special subspaces, and state criterions on how to choose the direction. Under given conditions, we obtain the significant conclusion that each choice of the direction satisfies the sufficient descent property. Based on the idea on how the function is close to a quadratic function, a new strategy for choosing the initial stepsize is presented for the line search. With the used nonmonotone Wolfe line search, we prove the global convergence of the proposed method for general nonlinear functions under mild assumptions. Numerical comparisons are given with well-known CGOPT and CG_DESCENT and show that the proposed algorithm is very promising.     

An Adaptive Nonmonotone Projected Barzilai-Borwein Gradient Method with Active Set Prediction for Nonnegative Matrix Factorization

In this paper, we first present an adaptive nonmonotone term to improve the efficiency of nonmonotone line search, and then an active set identification technique is suggested to get more efficient descent direction such that it improves the local convergence behavior of algorithm and decreases the computation cost. By means of the adaptive nonmonotone line search and the active set identification technique, we put forward a global convergent gradient-based method to solve the nonnegative matrix factorization (NMF) based on the alternating nonnegative least squares framework, in which we introduce a modified Barzilai-Borwein (BB) step size. The new modified BB step size and the larger step size strategy are exploited to accelerate convergence. Finally, the results of extensive numerical experiments using both synthetic and image datasets show that our proposed method is efficient in terms of computational speed.     

On the Nonmonotone Line Search

The technique of nonmonotone line search has received many successful applications and extensions in nonlinear optimization. This paper provides some basic analyses of the nonmonotone line search. Specifically, we analyze the nonmonotone line search methods for general nonconvex functions along different lines. The analyses are helpful in establishing the global convergence of a nonmonotone line search method under weaker conditions on the search direction. We explore also the relations between nonmonotone line search and R-linear convergence assuming that the objective function is uniformly convex. In addition, by taking the inexact Newton method as an example, we observe a numerical drawback of the original nonmonotone line search and suggest a standard Armijo line search when the nonmonotone line search condition is not satisfied by the prior trial steplength. The numerical results show the usefulness of such suggestion for the inexact Newton method.     

A nonmonotone trust-region line search method for large-scale unconstrained optimization

We consider an efficient trust-region framework which employs a new nonmonotone line search technique for unconstrained optimization problems. Unlike the traditional nonmonotone trust-region method, our proposed algorithm avoids resolving the subproblem whenever a trial step is rejected. Instead, it performs a nonmonotone Armijo-type line search in direction of the rejected trial step to construct a new point. Theoretical analysis indicates that the new approach preserves the global convergence to the first-order critical points under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed approach for solving unconstrained optimization problems.     

A modified SQP algorithm for minimax problems

In this paper, a modified nonmonotone line search SQP algorithm for nonlinear minimax problems is presented. During each iteration of the proposed algorithm, a main search direction is obtained by solving a reduced quadratic program (QP). In order to avoid the Maratos effect, a correction direction is generated by solving the reduced system of linear equations. Under mild conditions, the global and superlinear convergence can be achieved. Finally, some preliminary numerical results are reported.     

一类新的非单调信赖域算法

提出了一类带线性搜索的非单调信赖域算法.算法将非单调Armijo线性搜索技术与信赖域方法相结合,使算法不需重解子问题.而且由于采用了MBFGS校正公式,使矩阵Bk能较好地逼近目标函数的Hesse矩阵并保持正定传递.在较弱的条件下,证明了算法的全局收敛性.数值结果表明算法是有效的.     

基于非单调线搜索的对角二阶拟牛顿法

在二阶拟牛顿方程的基础上,结合Zhang H.C.提出的非单调线搜索构造了一种求解大规模无约束优化问题的对角二阶拟牛顿算法.算法在每次迭代中利用对角矩阵逼近Hessian矩阵的逆,使计算搜索方向的存储量和工作量明显减少,为大型无约束优化问题的求解提供了新的思路.在通常的假设条件下,证明了算法的全局收敛性和超线性收敛性.数值实验表明算法是有效可行的.     

A New Nonmonotone Linesearch SQP Algorithm for Unconstrained Minimax Problem

In this article, unconstrained minimax problems are discussed, and a sequential quadratic programming (SQP) algorithm with a new nonmonotone linesearch is presented. At each iteration, a search direction of descent is obtained by solving a quadratic programming (QP). To circumvent the Maratos effect, a high-order correction direction is achieved by solving another QP and a new nonmonotone linesearch is performed. Under reasonable conditions, the global convergence and the rate of superlinear convergence are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

一类新的非单调记忆梯度法及其全局收敛性

在非单调Armijo线搜索的基础上提出一种新的非单调线搜索,研究了一类在该线搜索下的记忆梯度法,在较弱条件下证明了其全局收敛性。与非单调Armijo线搜索相比,新的非单调线搜索在每次迭代时可以产生更大的步长,从而使目标函数值充分下降,降低算法的计算量。     

一类非单调修正PRP算法的全局收敛性

本文给出一类非单调线性搜索下的修正PRP算法,该方法保证每次迭代中的搜索方向是充分下降的.在较弱的条件下,我们证明了此类非单调修正PRP算法具有全局收敛性.     

非单调滤子曲率线搜索算法解无约束非凸优化

宇和濮在文[Yu Z S,Pu D G.A new nonmonotone line search technique for unconstrained optimization[J].J Comput Appl Math,2008,219:134-144]中提出了一种非单调的线搜索算法解无约束优化问题.和他们的工作不同,当优化问题非凸时,本文给出了一种非单调滤子曲率线搜索算法.通过使用海森矩阵的负曲率信息,算法产生的迭代序列被证明收敛于一个满足二阶充分性条件的点.在不需要假设极限点存在的情况下,证明了算法具有整体收敛性,而且分析了该算法的收敛速率.数值试验表明算法的有效性.     

A NONMOTOTONE ALGORITHM FOR MINIMIZING NONSMOOTH COMPOSITE FUNCTIONS

In this paper, we present a nonmonotone algorithm for solving nonsmooth composite optimization problems. The objective function of these problems is composited by a nonsmooth convex function and a differentiable function. The method generates the search directions by solving quadratic programming successively, and makes use of the nonmonotone line search instead of the usual Armijo-type line search. Global convergence is proved under standard assumptions. Numerical results are given.     

Convergence of nonmonotone line search method

In this paper, we develop a new nonmonotone line search for general line search method and establish some global convergence theorems. The new nonmonotone line search is a novel form of the nonmonotone Armijo line search and allows one to choose a larger step size at each iteration, which is available in constructing new line search methods and possibly reduces the function evaluations at each iteration. Moreover, we analyze the convergence rate of some special line search methods with the new line search. Preliminary numerical results show that some line search methods with the new nonmonotone line search are available and efficient in practical computation.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

A nonmonotone trust region method with new inexact line search for unconstrained optimization

In this paper, a new nonmonotone inexact line search rule is proposed and applied to the trust region method for unconstrained optimization problems. In our line search rule, the current nonmonotone term is a convex combination of the previous nonmonotone term and the current objective function value, instead of the current objective function value . We can obtain a larger stepsize in each line search procedure and possess nonmonotonicity when incorporating the nonmonotone term into the trust region method. Unlike the traditional trust region method, the algorithm avoids resolving the subproblem if a trial step is not accepted. Under suitable conditions, global convergence is established. Numerical results show that the new method is effective for solving unconstrained optimization problems.     

一种新的非单调谱共轭梯度算法

提出了一类新的非单调谱共轭梯度方法.该方法通过引入混合因子,将HS方法和PRP方法结合得到共轭系数的新的选取方式.以此为基础,通过合适地选取谱系数保证了所有搜索方向不依赖于线搜索条件,恒为充分下降方向.其次,该方法还修正了Zhang和Hager提出的非单调线搜索规则,在更弱的假设条件下证明了全局收敛性.数值试验说明了该方法的计算性能优良.     

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.     

Use of the Minimum-Norm Search Direction in a Nonmonotone Version of the Gauss-Newton Method

In this work, a new stabilization scheme for the Gauss-Newton method is defined, where the minimum norm solution of the linear least-squares problem is normally taken as search direction and the standard Gauss-Newton equation is suitably modified only at a subsequence of the iterates. Moreover, the stepsize is computed by means of a nonmonotone line search technique. The global convergence of the proposed algorithm model is proved under standard assumptions and the superlinear rate of convergence is ensured for the zero-residual case. A specific implementation algorithm is described, where the use of the pure Gauss-Newton iteration is conditioned to the progress made in the minimization process by controlling the stepsize. The results of a computational experimentation performed on a set of standard test problems are reported.     

A Modified SQP Method with Nonmonotone Linesearch Technique

In this paper, a modified SQP method with nonmonotone line search technique is presented based on the modified quadratic subproblem proposed in Zhou (1997) and the nonmonotone line search technique. This algorithm starts from an arbitrary initial point, adjusts penalty parameter automatically and can overcome the Maratos effect. What is more, the subproblem is feasible at each iterate point. The global and local superlinear convergence properties are obtained under certain conditions.