Alternate step gradient method*

The Barzilai and Borwein (BB) gradient method does not guarantee a descent in the objective function at each iteration, but performs better than the classical steepest descent (SD) method in practice. So far, the BB method has found many successful applications and generalizations in linear systems, unconstrained optimization, convex-constrained optimization, stochastic optimization, etc. In this article, we propose a new gradient method that uses the SD and the BB steps alternately. Hence the name “alternate step (AS) gradient method.” Our theoretical and numerical analyses show that the AS method is a promising alternative to the BB method for linear systems. Unconstrained optimization algorithms related to the AS method are also discussed. Particularly, a more efficient gradient algorithm is provided by exploring the idea of the AS method in the GBB algorithm by Raydan (1997).

To establish a general R-linear convergence result for gradient methods, an important property of the stepsize is drawn in this article. Consequently, R-linear convergence result is established for a large collection of gradient methods, including the AS method. Some interesting insights into gradient methods and discussion about monotonicity and nonmonotonicity are also given.     

An efficient gradient method with approximate optimal stepsize for the strictly convex quadratic minimization problem

In this paper, a new type of stepsize, approximate optimal stepsize, for gradient method is introduced to interpret the Barzilai–Borwein (BB) method, and an efficient gradient method with an approximate optimal stepsize for the strictly convex quadratic minimization problem is presented. Based on a multi-step quasi-Newton condition, we construct a new quadratic approximation model to generate an approximate optimal stepsize. We then use the two well-known BB stepsizes to truncate it for improving numerical effects and treat the resulted approximate optimal stepsize as the new stepsize for gradient method. We establish the global convergence and R-linear convergence of the proposed method. Numerical results show that the proposed method outperforms some well-known gradient methods.     

The cyclic Barzilai--Borwein method for unconstrained optimization

^** Email: dyh{at}lsec.cc.ac.cn^*** Email: hager{at}math.ufl.edu^**** Email: klaus.schittkowski{at}uni-bayreuth.de^***** Email: hzhang{at}math.ufl.edu In the cyclic Barzilai–Borwein (CBB) method, the sameBarzilai–Borwein (BB) stepsize is reused for m consecutiveiterations. It is proved that CBB is locally linearly convergentat a local minimizer with positive definite Hessian. Numericalevidence indicates that when m > n/2 3, where n is the problemdimension, CBB is locally superlinearly convergent. In the specialcase m = 3 and n = 2, it is proved that the convergence rateis no better than linear, in general. An implementation of theCBB method, called adaptive cyclic Barzilai–Borwein (ACBB),combines a non-monotone line search and an adaptive choice forthe cycle length m. In numerical experiments using the CUTErtest problem library, ACBB performs better than the existingBB gradient algorithm, while it is competitive with the well-knownPRP+ conjugate gradient algorithm.     

Global convergence of conjugate gradient method

In this article, we consider the global convergence of the Polak–Ribiére–Polyak conjugate gradient method (abbreviated PRP method) for minimizing functions that have Lipschitz continuous partial derivatives. A novel form of non-monotone line search is proposed to guarantee the global convergence of the PRP method. It is also shown that the PRP method has linear convergence rate under some mild conditions when the non-monotone line search reduces to a related monotone line search. The new non-monotone line search needs to estimate the Lipschitz constant of the gradients of objective functions, for which two practical estimations are proposed to help us to find a suitable initial step size for the PRP method. Numerical results show that the new line search approach is efficient in practical computation.     

低秩稀疏矩阵恢复的快速非单调交替极小化方法

针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.     

A family of three-term nonlinear conjugate gradient methods close to the memoryless BFGS method

Based on the memoryless BFGS quasi-Newton method, a family of three-term nonlinear conjugate gradient methods are proposed. For any line search, the directions generated by the new methods are sufficient descent. Using some efficient techniques, global convergence results are established when the line search fulfills the Wolfe or the Armijo conditions. Moreover, the r-linear convergence rate of the methods are analyzed as well. Numerical comparisons show that the proposed methods are efficient for the unconstrained optimization problems in the CUTEr library.     

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

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

An adaptive nonmonotone global Barzilai–Borwein gradient method for unconstrained optimization

The Barzilai–Borwein (BB) gradient method has received many studies due to its simplicity and numerical efficiency. By incorporating a nonmonotone line search, Raydan (SIAM J Optim. 1997;7:26–33) has successfully extended the BB gradient method for solving general unconstrained optimization problems so that it is competitive with conjugate gradient methods. However, the numerical results reported by Raydan are poor for very ill-conditioned problems because the effect of the degree of nonmonotonicity may be noticeable. In this paper, we focus more on the nonmonotone line search technique used in the global Barzilai–Borwein (GBB) gradient method. We improve the performance of the GBB gradient method by proposing an adaptive nonmonotone line search based on the morphology of the objective function. We also prove the global convergence and the R-linear convergence rate of the proposed method under reasonable assumptions. Finally, we give some numerical experiments made on a set of unconstrained optimization test problems of the CUTEr collection. The results show the efficiency of the proposed method in the sense of the performance profile introduced (Math Program. 2002;91:201–213) by Dolan and Moré.     

New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds

There are many applications related to singly linearly constrained quadratic programs subjected to upper and lower bounds. In this paper, a new algorithm based on secant approximation is provided for the case in which the Hessian matrix is diagonal and positive definite. To deal with the general case where the Hessian is not diagonal, a new efficient projected gradient algorithm is proposed. The basic features of the projected gradient algorithm are: 1) a new formula is used for the stepsize; 2) a recently-established adaptive non-monotone line search is incorporated; and 3) the optimal stepsize is determined by quadratic interpolation if the non-monotone line search criterion fails to be satisfied. Numerical experiments on large-scale random test problems and some medium-scale quadratic programs arising in the training of Support Vector Machines demonstrate the usefulness of these algorithms. This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grants (no. 10171104 and 40233029).     

An inexact line search approach using modified nonmonotone strategy for unconstrained optimization

This paper concerns with a new nonmonotone strategy and its application to the line search approach for unconstrained optimization. It has been believed that nonmonotone techniques can improve the possibility of finding the global optimum and increase the convergence rate of the algorithms. We first introduce a new nonmonotone strategy which includes a convex combination of the maximum function value of some preceding successful iterates and the current function value. We then incorporate the proposed nonmonotone strategy into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. The global convergence to first-order stationary points is subsequently proved and the R-linear convergence rate are established under suitable assumptions. Preliminary numerical results finally show the efficiency and the robustness of the proposed approach for solving unconstrained nonlinear optimization problems.     

A non-monotone line search multidimensional filter-SQP method for general nonlinear programming

In this paper, we propose a non-monotone line search multidimensional filter-SQP method for general nonlinear programming based on the Wächter–Biegler methods for nonlinear equality constrained programming. Under mild conditions, the global convergence of the new method is proved. Furthermore, with the non-monotone technique and second order correction step, it is shown that the proposed method does not suffer from the Maratos effect, so that fast local convergence to second order sufficient local solutions is achieved. Numerical results show that the new approach is efficient.     

Preconditioning non-monotone gradient methods for retrieval of seismic reflection signals

The core problem in seismic exploration is to invert the subsurface reflectivity from the surface recorded seismic data. However, most of the seismic inverse problems are ill-posed by nature. To overcome the ill-posedness, different regularized least squares methods are introduced in the literature. In this paper, we developed a preconditioning non-monotone gradient method, proved it converges with R-superlinear rate and applied it to seismic deconvolution and imaging. Numerical examples demonstrate that the method is efficient. It helps to improve the resolution of the seismic inversions.     

The Ziegler Spectrum of a Locally Coherent Grothendieck Category

The general theory of locally coherent Grothendieck categoriesis presented. To each locally coherent Grothendieck categoryC a topological space, the Ziegler spectrum of C, is associated.It is proved that the open subsets of the Ziegler spectrum ofC are in bijective correspondence with the Serre subcategoriesof coh C the subcategory of coherent objects of C. This is aNullstellensatz for locally coherent Grothendieck categories.If R is a ring, there is a canonical locally coherent Grothendieckcategory RC (respectively, CR) used for the study of left (respectively,right) R-modules. This category contains the category of R-modulesand its Ziegler spectrum is quasi-compact, a property used toconstruct large (not finitely generated) indecomposable modulesover an artin algebra. Two kinds of examples of locally coherentGrothendieck categories are given: the abstract category theoreticexamples arising from torsion and localization and the examplesthat arise from particular modules over the ring R. The dualitybetween coh-(RC) and coh-CR is shown to give an isomorphismbetween the topologies of the left and right Ziegler spectraof a ring R. The Nullstellensatz is used to give a proof ofthe result of Crawley-Boevey that every character : K₀(coh-C) Z is uniquely expressible as a Z-linear combination of irreduciblecharacters. 1991 Mathematics Subject Classification: 16D90,18E15.     

A new regularized quasi-Newton method for unconstrained optimization

In this paper, we propose a new regularized quasi-Newton method for unconstrained optimization. At each iteration, a regularized quasi-Newton equation is solved to obtain the search direction. The step size is determined by a non-monotone Armijo backtracking line search. An adaptive regularized parameter, which is updated according to the step size of the line search, is employed to compute the next search direction. The presented method is proved to be globally convergent. Numerical experiments show that the proposed method is effective for unconstrained optimizations and outperforms the existing regularized Newton method.     

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.     

A smoothing-type algorithm for solving nonlinear complementarity problems with a non-monotone line search

The smoothing-type algorithm has been successfully applied to solve various optimization problems. In general, the smoothing-type algorithm is designed based on some monotone line search. However, in order to achieve better numerical results, the non-monotone line search technique has been used in the numerical computations of some smoothing-type algorithms. In this paper, we propose a smoothing-type algorithm for solving the nonlinear complementarity problem with a non-monotone line search. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The preliminary numerical results are also reported.     

On the worst-case evaluation complexity of non-monotone line search algorithms

A general class of non-monotone line search algorithms has been proposed by Sachs and Sachs (Control Cybern 40:1059–1075, 2011) for smooth unconstrained optimization, generalizing various non-monotone step size rules such as the modified Armijo rule of Zhang and Hager (SIAM J Optim 14:1043–1056, 2004). In this paper, the worst-case complexity of this class of non-monotone algorithms is studied. The analysis is carried out in the context of non-convex, convex and strongly convex objectives with Lipschitz continuous gradients. Despite de nonmonotonicity in the decrease of function values, the complexity bounds obtained agree in order with the bounds already established for monotone algorithms.     

Barzilai–Borwein method with variable sample size for stochastic linear complementarity problems

A smoothing method for solving stochastic linear complementarity problems is proposed. The expected residual minimization reformulation of the problem is considered, and it is approximated by the sample average approximation (SAA). The proposed method is based on sequential solving of a sequence of smoothing problems where each of the smoothing problems is defined with its own sample average approximation. A nonmonotone line search with a variant of the Barzilai–Borwein (BB) gradient direction is used for solving each of the smoothing problems. The BB search direction is efficient and low cost, particularly suitable for nonmonotone line search procedure. The variable sample size scheme allows the sample size to vary across the iterations and the method tends to use smaller sample size far away from the solution. The key point of this strategy is a good balance between the variable sample size strategy, the smoothing sequence and nonmonotonicity. Eventually, the maximal sample size is used and the SAA problem is solved. Presented numerical results indicate that the proposed strategy reduces the overall computational cost.     

Global convergence of Riemannian line search methods with a Zhang-Hager-type condition

Numerical Algorithms - In this paper, we analyze the global convergence of a general non-monotone line search method on Riemannian manifolds. For this end, we introduce some properties for the...     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...