一个线性约束优化问题的广义梯度投影法

本文对线性约束优化问题提出了一个新的广义梯度投影法，该算法采用了非精确线性搜索，并在每次迭代运算中结合了广义投影矩阵和变尺度方法的思想确定其搜索方向．在通常的假设条件下，证明了该算法的整体收敛性和超线性收敛速度．     

A Modified Nonmonotone Hestenes–Stiefel Type Conjugate Gradient Methods for Large-Scale Unconstrained Problems

In this article, by slightly modifying the search direction of the nonmonotone Hestenes–Stiefel method, a variant Hestenes–Stiefel conjugate gradient method is proposed that satisfies the su?cient descent condition independent of any line search. This algorithm also possesses information about the gradient value and the function value. We establish the global convergence of our methods without the assumption that the steplength is bounded away from zero. Numerical results illustrate that our method can e?ciently solve the test problems, and therefore is promising.     

基于非单调线搜索非拟牛顿法的全局收敛性

本文就非拟牛顿法在无约束最优化问题上，对采用非单调线搜索的情况下是否具有全局收敛性进行了研究，在目标函数满足一致凸的条件下，证明了非拟牛顿族是全局收敛的．     

一类基于广义梯度的求解非线性互补问题的算法

1 引言非线性互补问题(下称NCP)的应用十分广泛,自本世纪六十年代以来,人们对这一问题解的存在唯一性、灵敏度分析、算法与应用等方面进行深入的研究,取得很大的进展。关于NCP的解法通常是将其化为序列线性互补问题,而对线性问题则有若干现成算法,如Lemke算法。但一般说来,此类方法工作量大,效果也难以令人满意。J.S.Pang于七十年代提出了B-可微算法,即将NCP转化为一个B-可微函数的零点问题。近年来提出的一些算法大多属于此类方法。 本文提出的算法也属于B-可微算法,虽同是从广义梯度出发,但不同的是,我们不是通过二次规划而是通过线性规划来获得搜寻方向。由于所涉及的线性规划问题特别的简单,我们可以很快而方便地求得其解,所以算法简易可行,速度较快。     

Convergence of descent method with new line search

An efficient descent method for unconstrained optimization problems is line search method in which the step size is required to choose at each iteration after a descent direction is determined. There are many ways to choose the step sizes, such as the exact line search, Armijo line search, Goldstein line search, and Wolfe line search, etc. In this paper we propose a new inexact line search for a general descent method and establish some global convergence properties. This new line search has many advantages comparing with other similar inexact line searches. Moreover, we analyze the global convergence and local convergence rate of some special descent methods with the new line search. Preliminary numerical results show that the new line search is available and efficient in practical computation.     

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.     

Projected gradient trust-region method for solving nonlinear systems with convex constraints

In this paper, a projected gradient trust region algorithm for solving nonlinear equality systems with convex constraints is considered. The global convergence results are developed in a very general setting of computing trial directions by this method combining with the line search technique. Close to the solution set this method is locally Q-superlinearly convergent under an error bound assumption which is much weaker than the standard nonsingularity condition.     

三项记忆梯度法及其投影算法的收敛性分析

对于无约束优化问题,提出了一类新的三项记忆梯度算法．这类算法是在参数满足某些假设的条件下,确定它的取值范围,从而保证三项记忆梯度方向是使目标函数充分下降的方向．在非单调步长搜索下讨论了算法的全局收敛性．为了得到具有更好收敛性质的算法,结合Solodov and Svaiter(2000)中的部分技巧,提出了一种新的记忆梯度投影算法,并证明了该算法在函数伪凸的情况下具有整体收敛性．     

On Weak and Strong Convergence of the Projected Gradient Method for Convex Optimization in Real Hilbert Spaces

This work focuses on convergence analysis of the projected gradient method for solving constrained convex minimization problems in Hilbert spaces. We show that the sequence of points generated by the method employing the Armijo line search converges weakly to a solution of the considered convex optimization problem. Weak convergence is established by assuming convexity and Gateaux differentiability of the objective function, whose Gateaux derivative is supposed to be uniformly continuous on bounded sets. Furthermore, we propose some modifications in the classical projected gradient method in order to obtain strong convergence. The new variant has the following desirable properties: the sequence of generated points is entirely contained in a ball with diameter equal to the distance between the initial point and the solution set, and the whole sequence converges strongly to the solution of the problem that lies closest to the initial iterate. Convergence analysis of both methods is presented without Lipschitz continuity assumption.     

凸约束伪单调方程组的无导数投影算法

基于HS共轭梯度法的结构,本文在弱假设条件下建立了一种求解凸约束伪单调方程组问题的迭代投影算法.该算法不需要利用方程组的任何梯度或Jacobian矩阵信息,因此它适合求解大规模问题.算法在每一次迭代中都能产生充分下降方向,且不依赖于任何线搜索条件.特别是,我们在不需要假设方程组满足Lipschitz条件下建立了算法的全...     

Global convergence of a two-parameter family of conjugate gradient methods without line search

We study the global convergence of a two-parameter family of conjugate gradient methods in which the line search procedure is replaced by a fixed formula of stepsize. This character is of significance if the line search is expensive in a particular application. In addition to the convergence results, we present computational results for various conjugate gradient methods without line search including those discussed by Sun and Zhang (Ann. Oper. Res. 103 (2001) 161–173).     

结合Armijo步长搜索的一类新的记忆梯度算法及其收敛特征

对求解无约束规划的超记忆梯度算法中线搜索方向中的参数,给了一个假设条件,从而确定了它的一个新的取值范围,保证了搜索方向是目标函数的充分下降方向,由此提出了一类新的记忆梯度算法.在去掉迭代点列有界和Armijo步长搜索下,讨论了算法的全局收敛性,且给出了结合形如共轭梯度法FR,PR,HS的记忆梯度法的修正形式.数值实验表明,新算法比Armijo线搜索下的FR、PR、HS共轭梯度法和超记忆梯度法更稳定、更有效.     

CG Global Convergence Properties with Goldstein Linesearch*

This paper explores the convergence of nonlinear conjugate gradient methods with Goldstein line search without regular restarts. Under this line search, global convergence for a subsequence is given for the famous conjugate gradient methods, Fletcher-Reeves method. The same result can be obtained for Polak-Ribiére-Polyak method and others. *This work was partially supported by National Hitech Program (863,2002AA104540) and National Natural Science Foundation of China (No.60373060).     

A smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.     

Affine scaling interior Levenberg–Marquardt method for bound-constrained semismooth equations under local error bound conditions

We develop and analyze a new affine scaling Levenberg–Marquardt method with nonmonotonic interior backtracking line search technique for solving bound-constrained semismooth equations under local error bound conditions. The affine scaling Levenberg–Marquardt equation is based on a minimization of the squared Euclidean norm of linear model adding a quadratic affine scaling matrix to find a solution that belongs to the bounded constraints on variable. The global convergence results are developed in a very general setting of computing trial directions by a semismooth Levenberg–Marquardt method where a backtracking line search technique projects trial steps onto the feasible interior set. We establish that close to the solution set the affine scaling interior Levenberg–Marquardt algorithm is shown to converge locally Q-superlinearly depending on the quality of the semismooth and Levenberg–Marquardt parameter under an error bound assumption that is much weaker than the standard nonsingularity condition, that is, BD-regular condition under nonsmooth case. A nonmonotonic criterion should bring about speed up the convergence progress in the contours of objective function with large curvature.     

共轭下降法的全局收敛性

本文提出了一种Armijo型的线搜索，并在这种线搜索下讨论了共轭下降法的全局收敛性，且可得方法在每次迭代均产生一个下降搜索方向．     

非精确线性搜索条件下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].     

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.     

Modification of the Wolfe Line Search Rules to Satisfy the Descent Condition in the Polak-Ribière-Polyak Conjugate Gradient Method

This paper proposes a line search technique to satisfy a relaxed form of the strong Wolfe conditions in order to guarantee the descent condition at each iteration of the Polak-Ribière-Polyak conjugate gradient algorithm. It is proved that this line search algorithm preserves the usual convergence properties of any descent algorithm. In particular, it is shown that the Zoutendijk condition holds under mild assumptions. It is also proved that the resulting conjugate gradient algorithm is convergent under a strong convexity assumption. For the nonconvex case, a globally convergent modification is proposed. Numerical tests are presented. This paper is based on an earlier work presented at the International Symposium on Mathematical Programming in Lausanne in 1997. The author thanks J. C. Gilbert for his advice and M. Albaali for some recent discussions which motivated him to write this paper. Special thanks to G. Liu, J. Nocedal, and R. Waltz for the availability of the software CG+ and to one of the referees who indicated to him the paper of Grippo and Lucidi (Ref. 1).     

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.