Convergence of quasi-Newton method with new inexact line search

Quasi-Newton method is a well-known effective method for solving optimization problems. Since it is a line search method, which needs a line search procedure after determining a search direction at each iteration, we must decide a line search rule to choose a step size along a search direction. In this paper, we propose a new inexact line search rule for quasi-Newton method and establish some global convergent results of this method. These results are useful in designing new quasi-Newton methods. Moreover, we analyze the convergence rate of quasi-Newton method with the new line search rule.     

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.     

Modified nonmonotone Armijo line search for descent method

Nonmonotone line search approach is a new technique for solving optimization problems. It relaxes the line search range and finds a larger step-size at each iteration, so as to possibly avoid local minimizer and run away from narrow curved valley. It is helpful to find the global minimizer of optimization problems. In this paper we develop a new modification of matrix-free nonmonotone Armijo line search and analyze the global convergence and convergence rate of the resulting method. We also address several approaches to estimate the Lipschitz constant of the gradient of objective functions that would be used in line search algorithms. Numerical results show that this new modification of Armijo line search is efficient for solving large scale unconstrained optimization problems.     

Accelerated gradient descent methods with line search

We introduced an algorithm for unconstrained optimization based on the transformation of the Newton method with the line search into a gradient descent method. Main idea used in the algorithm construction is approximation of the Hessian by an appropriate diagonal matrix. The steplength calculation algorithm is based on the Taylor’s development in two successive iterative points and the backtracking line search procedure. The linear convergence of the algorithm is proved for uniformly convex functions and strictly convex quadratic functions satisfying specified conditions.     

Two new self-adaptive descent methods without line search for co-coercive structured variational inequality problems

This paper presents two new self-adaptive descent methods without line search for co-coercive structured variational inequality problems whose mapping does not have any explicit analytic form and only the functional value is available through exogenous evaluation or direct observation. The first method only needs functional values for given variables in the solution process, and can be viewed as a modification of Zhang and Han’s method (Comput. Math. Appl. 57(7):1168–1178, 2009), by adopting a self-adaptive technique to adjust parameter β _k . The second method is an extension of the first one for another type of constrained variational inequality problems. The optimal step size along the descent direction improves the efficiency of the new methods. Some numerical results illustrate that the new methods are effective in practice.     

A descent algorithm without line search for unconstrained optimization

In this paper, a new descent algorithm for solving unconstrained optimization problem is presented. Its search direction is descent and line search procedure can be avoided except for the first iteration. It is globally convergent under mild conditions. The search direction of the new algorithm is generalized and convergence of corresponding algorithm is also proved. Numerical results show that the algorithm is efficient for given test problems.     

A note on convergence of PRP method with new nonmonotone line search

We in this note drop a Lipschitz constant in a Grippo-Lucidi-type step length rule recently proposed by Shi and Shen [Z. Shi, J. Shen, Convergence of PRP method with new nonmonotone line search, Applied Mathematics and Computation 181(1) (2006) 423-431], and the original convergence remains valid.     

Convergence of the steepest descent method for accretive operators

Let be a uniformly smooth Banach space and let be a bounded demicontinuous mapping, which is also -strongly accretive on . Let and let be an arbitrary initial value in . Then the approximating scheme

converges strongly to the unique solution of the equation , provided that the sequence fulfills suitable conditions.

     

A descent method with inexact linear search for nonsmooth equilibrium problems

A descent method with respect to the gap function is formulated and justified for the nonsmooth equilibrium problem. It uses the procedure of inexact linear search of the Armijo type. The proposed method converges under the same assumptions as the methods with exact linear search.     

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.     

Convergence of the steepest descent method for minimizing quasiconvex functions

To minimize a continuously differentiable quasiconvex functionf: ⁿ , Armijo's steepest descent method generates a sequencex ^k+1 =x ^k –t _k f(x ^k ), wheret _k >0. We establish strong convergence properties of this classic method: either , s.t. ; or arg minf = , x ^k andf(x ^k ) inff. We also discuss extensions to other line searches.The research of the first author was supported by the Polish Academy of Sciences. The second author acknowledges the support of the Department of Industrial Engineering, Hong Kong University of Science and Technology.We wish to thank two anonymous referees for their valuable comments. In particular, one referee has suggested the use of quasiconvexity instead of convexity off.     

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.     

半监督度量学习内蕴最速下降算法的收敛性分析

主要研究对称正定矩阵群上的内蕴最速下降算法的收敛性问题.首先针对一个可转化为对称正定矩阵群上无约束优化问题的半监督度量学习模型,提出对称正定矩阵群上一种自适应变步长的内蕴最速下降算法.然后利用李群上的光滑函数在任意一点处带积分余项的泰勒展开式,证明所提算法在对称正定矩阵群上是线性收敛的.最后通过在分类问题中的数值实验说明算法的有效性.     

Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds

This paper extends the full convergence of the steepest descent method with a generalized Armijo search and a proximal regularization to solve minimization problems with quasiconvex objective functions on complete Riemannian manifolds. Previous convergence results are obtained as particular cases and some examples in non-Euclidian spaces are given. In particular, our approach can be used to solve constrained minimization problems with nonconvex objective functions in Euclidian spaces if the set of constraints is a Riemannian manifold and the objective function is quasiconvex in this manifold.     

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.     

Goldstein线搜索下Levenberg-Marquardt方法的全局收敛性

给出在Goldstein线搜索条件下求解非线性方程的Levenberg-Marquardt方法, 在较为温和的条件下证明了该方法的全局收敛性, 并且利用该方法对广义互补问题进行了求解分析.     

Convergence theorems for continuous descent methods

We examine continuous descent methods for the minimization of Lipschitzian functions defined on a general Banach space. We establish several convergence theorems for those methods which are generated by regular vector fields. Since the complement of the set of regular vector fields is -porous, we conclude that our results apply to most vector fields in the sense of Baires categories.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)