A nonmonotone scaled conjugate gradient algorithm for large-scale unconstrained optimization

This paper proposes a nonmonotone scaled conjugate gradient algorithm for solving large-scale unconstrained optimization problems, which combines the idea of scaled memoryless Broyden–Fletcher–Goldfarb–Shanno preconditioned conjugate gradient method with the nonmonotone technique. An attractive property of the proposed method is that the search direction always provides sufficient descent step at each iteration. This property is independent of the line search used. Under appropriate assumptions, the method is proven to possess global convergence for nonconvex smooth functions, and R-linear convergence for strongly convex functions. Preliminary numerical results and related comparisons show the efficiency of the proposed method in practical computation.     

A cubic regularization algorithm for unconstrained optimization using line search and nonmonotone techniques

In recent years, cubic regularization algorithms for unconstrained optimization have been defined as alternatives to trust-region and line search schemes. These regularization techniques are based on the strategy of computing an (approximate) global minimizer of a cubic overestimator of the objective function. In this work we focus on the adaptive regularization algorithm using cubics (ARC) proposed in Cartis et al. [Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Mathematical Programming A 127 (2011), pp. 245–295]. Our purpose is to design a modified version of ARC in order to improve the computational efficiency preserving global convergence properties. The basic idea is to suitably combine a Goldstein-type line search and a nonmonotone accepting criterion with the aim of advantageously exploiting the possible good descent properties of the trial step computed as (approximate) minimizer of the cubic model. Global convergence properties of the proposed nonmonotone ARC algorithm are proved. Numerical experiments are performed and the obtained results clearly show satisfactory performance of the new algorithm when compared to the basic ARC algorithm.     

An affine scaling interior trust-region method combining with nonmonotone line search filter technique for linear inequality constrained minimization

This paper proposes an affine scaling interior trust-region method in association with nonmonotone line search filter technique for solving nonlinear optimization problems subject to linear inequality constraints. Based on a Newton step which is derived from the complementarity conditions of linear inequality constrained optimization, a trust-region subproblem subject only to an ellipsoidal constraint is defined by minimizing a quadratic model with an appropriate quadratic function and scaling matrix. The nonmonotone schemes combining with trust-region strategy and line search filter technique can bring about speeding up the convergence progress in the case of high nonlinear. A new backtracking relevance condition is given which assures global convergence without using the switching condition used in the traditional line search filter technique. The fast local convergence rate of the proposed algorithm is achieved which is not depending on any external restoration procedure. The preliminary numerical experiments are reported to show effectiveness of the proposed algorithm.     

A nonmonotone SQP-filter method for equality constrained optimization

In this paper, we propose a nonmonotone sequential quadratic programming-filter method for solving nonlinear equality constrained optimization. This new method has more flexibility for the acceptance of the trial step and requires less computational costs compared with the monotone methods. Under reasonable conditions, we give the global convergence properties. Further, the second-order correction step and nonmonotone reduction conditions are used to overcome Maratos effect so that quadratic local convergence is achieved. The numerical experiments are reported to show the effectiveness of the proposed algorithm.     

基于谱投影梯度追踪的压缩感知重建算法

为了改进方向追踪法的重建精度和算法效率, 提出了一种基于谱投影梯度(Spectral projected gradient, SPG)追踪的压缩感知(Compressed sensing, CS) 重建算法. 该算法采用方向追踪法框架, 运用谱投影梯度方法计算更新方向和步长, 引进非单调线性搜索策略使算法避免收敛至局部最优解. 实验结果证明了该算法的有效性, 通过设定合适的阈值参数可以取得重建精度和算法效率之间的平衡.     

A new nonmonotone filter Barzilai–Borwein method for solving unconstrained optimization problems

In this paper, a finite filter is used in the structure of the Barzilai–Browein (BB) gradient method in order to propose a new modified BB algorithm for solving large-scale unconstrained optimization problems. Our algorithm is equipped with a relaxed nonmonotone line search technique which allows the algorithm to enjoy the nonmonotonicity properties from scratch. Under some suitable conditions, the global convergence property of the new proposed algorithm is established. Numerical results on some test problems in CUTEr library show the efficiency and effectiveness of the new algorithm in practice too.     

The higher-order Levenberg–Marquardt method with Armijo type line search for nonlinear equations

To save more Jacobian calculations and achieve a faster convergence rate, Yang [A higher-order Levenberg-Marquardt method for nonlinear equations, Appl. Math. Comput. 219(22)(2013), pp. 10682–10694, doi:10.1016/j.amc.2013.04.033, 65H10] proposed a higher-order Levenberg–Marquardt (LM) method by computing the LM step and another two approximate LM steps for nonlinear equations. Under the local error bound condition, global and local convergence of this method is proved by using trust region technique. However, it is clear that the last two approximate LM steps may be not necessarily a descent direction, and standard line search technique cannot be used directly to obtain the convergence properties of this higher-order LM method. Hence, in this paper, we employ the nonmonotone second-order Armijo line search proposed by Zhou [On the convergence of the modified Levenberg-Marquardt method with a nonmonotone second order Armijo type line search, J. Comput. Appl. Math. 239 (2013), pp. 152–161] to guarantee the global convergence of this higher-order LM method. Moreover, the local convergence is also preserved under the local error bound condition. Numerical results show that the new method is efficient.     

一个松弛非单调线搜索法

对于无约束优化问题,我们用松弛技术改进了一般非单调线搜索准则,建立了相应的求解算法,并证明了算法的整体收敛性.部分数值实验结果表明,这个松弛非单调算法有效.     

An adaptive nonmonotone trust region algorithm

Based on an eigenvalue analysis conducted on the scaled memoryless quasi-Newton updating formulas BFGS and DFP, an adaptive choice for the trust region radius is proposed. Then, using a trust region ratio obtained from a nonmonotone line search strategy, an adaptive nonmonotone trust region algorithm is developed. Under proper conditions, it is briefly shown that the proposed algorithm is globally and locally superlinearly convergent. Numerical experiments are done on a set of unconstrained optimization test problems of the CUTEr collection, using the Dolan–Moré performance profile. They show efficiency of the proposed algorithm.     

On the nonmonotonicity degree of nonmonotone line searches

The nonmonotone globalization technique is useful in difficult nonlinear problems, because of the fact that it may help escaping from steep sided valleys and may improve both the possibility of finding the global optimum and the rate of convergence. This paper discusses the nonmonotonicity degree of nonmonotone line searches for the unconstrained optimization. Specifically, we analyze some popular nonmonotone line search methods and explore, from a computational point of view, the relations between the efficiency of a nonmonotone line search and its nonmonotonicity degree. We attempt to answer this question how to control the degree of the nonmonotonicity of line search rules in order to reach a more efficient algorithm. Hence in an attempt to control the nonmonotonicity degree, two adaptive nonmonotone rules based on the morphology of the objective function are proposed. The global convergence and the convergence rate of the proposed methods are analysed under mild assumptions. Numerical experiments are made on a set of unconstrained optimization test problems of the CUTEr (Gould et al. in ACM Trans Math Softw 29:373–394, 2003) collection. The performance data are first analysed through the performance profile of Dolan and Moré (Math Program 91:201–213, 2002). In the second kind of analyse, the performance data are analysed in terms of increasing dimension of the test problems.     

Optimal control of viscous Burgers equation via an adaptive nonmonotone Barzilai–Borwein gradient method

An adaptive nonmonotone spectral gradient method for the solution of distributed optimal control problem (OCP) for the viscous Burgers equation is presented in a black-box framework. Regarding the implicit function theorem, the OCP is transformed into an unconstrained nonlinear optimization problem (UNOP). For solving UNOP, an adaptive nonmonotone Barzilai–Borwein gradient method is proposed in which to make a globalization strategy, first an adaptive nonmonotone strategy which properly controls the degree of nonmonotonicity is presented and then is incorporated into an inexact line search approach to construct a more relaxed line search procedure. Also an adjoint technique is used to effectively evaluate the gradient. The low memory requirement and the guaranteed convergence property make the proposed method quite useful for large-scale OCPs. The efficiency of the presented method is supported by numerical experiments.     

记忆梯度追踪压缩感知图像重构

目的：重构算法是压缩感知理论的关键问题之一,为了减少压缩感知方向追踪算法重建时间,并确保相对较高的重建精度,提出了一种非单调记忆梯度追踪（memory gradient pursuit,MGP）重构信号处理算法。方法：该算法建立在方向追踪框架下,采用正则化正交匹配策略实现了原子集的快速有效选择,对所选原子集利用非单调线性搜索准则确定步长,用记忆梯度算法计算更新方向,从而得到稀疏信号估计值。结果：该算法充分利用记忆梯度算法在Armijo线搜索下全局收敛性快速稳定的优点避免收敛到局部最优解,提升收敛效率。提出的MGP算法运行时间上比近似共轭梯度追踪算法缩短30%,可以精确重构一维信号和二维图像信号。结论：实验结果表明,该算法兼顾了效率和重建精度,有效提高信号重建性能,在相同测试条件下优于其他同类的重构算法。     

Gradient methods exploiting spectral properties

We propose a new stepsize for the gradient method. It is shown that this new stepsize will converge to the reciprocal of the largest eigenvalue of the Hessian, when Dai-Yang's asymptotic optimal gradient method (Computational Optimization and Applications, 2006, 33(1): 73–88) is applied for minimizing quadratic objective functions. Based on this spectral property, we develop a monotone gradient method that takes a certain number of steps using the asymptotically optimal stepsize by Dai and Yang, and then follows by some short steps associated with this new stepsize. By employing one step retard of the asymptotic optimal stepsize, a nonmonotone variant of this method is also proposed. Under mild conditions, R-linear convergence of the proposed methods is established for minimizing quadratic functions. In addition, by combining gradient projection techniques and adaptive nonmonotone line search, we further extend those methods for general bound constrained optimization. Two variants of gradient projection methods combining with the Barzilai-Borwein stepsizes are also proposed. Our numerical experiments on both quadratic and bound constrained optimization indicate that the new proposed strategies and methods are very effective.     

A semi-Lagrangian level set method for structural optimization

In level set based structural optimization, semi-Lagrange method has an advantage to allow for a large time step without the limitation of Courant–Friedrichs–Lewy (CFL) condition for numerical stability. In this paper, a line search algorithm and a sensitivity modulation scheme are introduced for the semi-Lagrange method. The line search attempts to adaptively determine an appropriate time step in each iteration of optimization. With consideration of some practical characteristics of the topology optimization process, incorporating the line search into semi-Lagrange optimization method can yield fewer design iterations and thus improve the overall computational efficiency. The sensitivity modulation is inspired from the conjugate gradient method in finite-dimensions, and provides an alternative to the standard steepest descent search in level set based optimization. Two benchmark examples are presented to compare the sensitivity modulation and the steepest descent techniques with and without the line search respectively.     

Optimization of unconstrained problems using a developed algorithm of spectral conjugate gradient method calculation

This paper presents a numerical investigation of the spectral conjugate directions formulation for optimizing unconstrained problems. A novel modified algorithm is proposed based on the conjugate gradient coefficient method. The algorithm employs the Wolfe inexact line search conditions to determine the optimum step length at each iteration and selects the appropriate conjugate gradient coefficient accordingly. The algorithm is evaluated through several numerical experiments using various unconstrained functions. The results indicate that the algorithm is highly stable, regardless of the starting point, and has better convergence rates and efficiency compared to classical methods in certain cases. Overall, this research provides a promising approach to solving unconstrained optimization problems.     

一类基于Armijo搜索的改进DY共轭梯度法及其全局收敛性

本文通过结合MFR方法与MDY方法,对搜索方向进行调整,提出了一类求解无约束优化问题的修正DY共轭梯度法,该法在每步迭代都能不依赖于任何搜索而自行产生充分下降方向．在适当的条件下,证明了在Armijo搜索下对于非凸的优化问题,本文算法是全局收敛的．数值实验表明本文算法是有效的．     

An affine-scaling derivative-free trust-region method for solving nonlinear systems subject to linear inequality constraints

In this paper, an affine-scaling derivative-free trust-region method with interior backtracking line search technique is considered for solving nonlinear systems subject to linear inequality constraints. The proposed algorithm is designed to take advantage of the problem structured by building polynomial interpolation models for each function in the nonlinear system function F. The proposed approach is developed by forming a quadratic model with an appropriate quadratic function and scaling matrix: there is no need to handle the constraints explicitly. By using both trust-region strategy and interior backing line search technique, each iteration switches to backtracking step generated by the trust-region subproblem and satisfies strict interior point feasibility by line search backtracking technique. Under reasonable conditions, the global convergence and fast local convergence rate of the proposed algorithm are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithms.     

An adaptive nonmonotone truncated Newton method for optimal control of a class of parabolic distributed parameter systems

A black-box method using the finite elements, the Crank–Nicolson and a nonmonotone truncated Newton (TN) method is presented for solving optimal control problems (OCPs) governed by partial differential equations (PDEs). The proposed method finds the optimal control of a class of linear and nonlinear parabolic distributed parameter systems with a quadratic cost functional. To this end, the piecewise linear finite elements method and the well-known Crank–Nicolson method are used for discretizing in space and in time, respectively. Afterwards, regarding the implicit function theorem (IFT), the optimal control problem is transformed into an unconstrained nonlinear optimization problem. Considering that in a gradient-based method for solving optimal control problems, the evaluations of gradients and Hessians of the cost functional is important, hence, an adjoint technique is used to evaluate them effectively. In addition, to make a globalization strategy, we first introduce an adaptive nonmonotone strategy which properly controls the degree of nonmonotonicity and then incorporate it into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. Finally, the obtained unconstrained nonlinear optimization problem is solved by utilizing the proposed nonmonotone truncated Newton method. Results gained from the new offered method compared with existing methods show that the new method is promising.     

A nonmonotone accelerated Levenberg–Marquardt method for the -eigenvalues of symmetric tensors

The eigenvalues of tensors become more and more important in the numerical multilinear algebra. In this paper, based on the nonmonotone technique, an accelerated Levenberg–Marquardt (LM) algorithm is presented for computing the -eigenvalues of symmetric tensors, in which an LM step and an accelerated LM step are computed at each iteration. We establish the global convergence of the proposed algorithm using properties of symmetric tensors and norms. Under the local error-bound condition, the cubic convergence of the nonmonotone accelerated LM algorithm is derived. Numerical results show that this method is efficient.     

A new trust-region method with line search for solving symmetric nonlinear equations

A new trust-region method is proposed for symmetric nonlinear equations. In this given algorithm, if the trial step is unsuccessful, one line search will be used instead of repeatedly solving the subproblem of the normal trust-region method. Moreover, the global convergence is established under mild conditions by a new way. The quadratic convergence of the presented method is also proved. Numerical results show that the method is interesting for the given problems.