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

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

The global and superlinear convergence of a new nonmonotone MBFGS algorithm on convex objective functions

In this paper, a new nonmonotone MBFGS algorithm for unconstrained optimization will be proposed. Under some suitable assumptions, the global and superlinear convergence of the new nonmonotone MBFGS algorithm on convex objective functions will be established. Some numerical experiments show that this new nonmonotone MBFGS algorithm is competitive to the MBFGS algorithm and the nonmonotone BFGS algorithm.     

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.     

The convergence of conjugate gradient method with nonmonotone line search

The conjugate gradient method is a useful and powerful approach for solving large-scale minimization problems. Liu and Storey developed a conjugate gradient method, which has good numerical performance but no global convergence under traditional line searches such as Armijo line search, Wolfe line search, and Goldstein line search. In this paper we propose a new nonmonotone line search for Liu-Storey conjugate gradient method (LS in short). The new nonmonotone line search can guarantee the global convergence of LS method and has a good numerical performance. By estimating the Lipschitz constant of the derivative of objective functions in the new nonmonotone line search, we can find an adequate step size and substantially decrease the number of functional evaluations at each iteration. Numerical results show that the new approach is effective in practical computation.     

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

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

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.     

Adaptive Two-Point Stepsize Gradient Algorithm

Combined with the nonmonotone line search, the two-point stepsize gradient method has successfully been applied for large-scale unconstrained optimization. However, the numerical performances of the algorithm heavily depend on M, one of the parameters in the nonmonotone line search, even for ill-conditioned problems. This paper proposes an adaptive nonmonotone line search. The two-point stepsize gradient method is shown to be globally convergent with this adaptive nonmonotone line search. Numerical results show that the adaptive nonmonotone line search is specially suitable for the two-point stepsize gradient method.     

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.     

一个新的MBFGS信赖域算法

本文研究了无约束最优化问题.利用MBFGS信赖域算法的基本思想,通过对BFGS校正公式的改进,并结合线搜索技术,提出了一种新的MBFGS信赖域算法,拓宽了信赖域算法的适用范围,并在一定条件下证明了该算法的全局收敛性和超线性收敛性.     

A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values

In this paper we propose a nonmonotone trust region method. Unlike traditional nonmonotone trust region method, the nonmonotone technique applied to our method is based on the nonmonotone line search technique proposed by Zhang and Hager [A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim. 14(4) (2004) 1043–1056] instead of that presented by Grippo et al. [A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal. 23(4) (1986) 707–716]. So the method requires nonincreasing of a special weighted average of the successive function values. Global and superlinear convergence of the method are proved under suitable conditions. Preliminary numerical results show that the method is efficient for unconstrained optimization problems.     

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.     

A new nonmonotone line search technique for unconstrained optimization

In this paper, we propose a new nonmonotone line search technique for unconstrained optimization problems. By using this new technique, we establish the global convergence under conditions weaker than those of the existed nonmonotone line search techniques.     

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.      

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

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

A nonmonotone conic trust region method based on line search for solving unconstrained optimization

In this paper, we present a nonmonotone conic trust region method based on line search technique for unconstrained optimization. The new algorithm can be regarded as a combination of nonmonotone technique, line search technique and conic trust region method. When a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength satisfies some line search condition. The function value can only be allowed to increase when trial steps are not accepted in close succession of iterations. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments are conducted to compare this method with the existing methods.     

Combining nonmonotone conic trust region and line search techniques for unconstrained optimization

In this paper, we propose a trust region method for unconstrained optimization that can be regarded as a combination of conic model, nonmonotone and line search techniques. Unlike in traditional trust region methods, the subproblem of our algorithm is the conic minimization subproblem; moreover, our algorithm performs a nonmonotone line search to find the next iteration point when a trial step is not accepted, instead of resolving the subproblem. The global and superlinear convergence results for the algorithm are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

基于非单调技术的ODE型混合方法

基于非单调线搜索技术和IMPBOT算法,提出了一个求解无约束优化问题的ODE型混合方法.该方法的主要特点是：为了求得试验步,该方法在每次迭代时不必求解带信赖域界的子问题,仅需要求解一线性方程组系统;当试验步不被接受时,该方法就执行改进的Wolfe-型非单调线搜索来获得下一个新的迭代点,从而避免了反复求解线性方程组系统. 在一定条件下,所提算法还是整体收敛和超线性收敛的. 数值试验结果表明该方法是有效的.     

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 simple conic model function,in which the Hessian approximation is a scalar matrix,is constructed by using the function values and gradient values of the minimizing function.Based on this conic model function,a new nonmonotone line search method is proposed.The convergence results of this line search method are proved under certain conditions.Numerical results show that the new algorithm is effective.     

Smoothing Newton algorithm for the second-order cone programming with a nonmonotone line search

The smoothing-type algorithms, which are in general designed based on some monotone line search, have been successfully applied to solve the second-order cone programming (denoted by SOCP). In this paper, we propose a nonmonotone smoothing Newton algorithm for solving the SOCP. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. To compare with the existing smoothing-type algorithms for the SOCP, our algorithm has the following special properties: (i) it is based on a new smoothing function of the vector-valued natural residual function; (ii) it uses a nonmonotone line search scheme which contains the usual monotone line search as a special case. Preliminary numerical results demonstrate that the smoothing-type algorithm using the nonmonotone line search is promising for solving the SOCP.