一类锥模型非单调信赖域算法及收敛性分析

本文对无约束优化问题提出了一类基于锥模型的非单调信赖域算法.二次模型非单调信赖域算法是新算法的特例.在适当的条件下,证明了算法的全局收敛性及Q-二次收敛性.     

一类非单调保守BFGS算法研究

基于非单调线搜索在寻求优化问题最优解中的优越性,提出了一类新的非单调保守BFGS算法.同已有方法不同,该算法中用来控制非单调性程度的算法参数不是取固定值,而是利用已有目标函数和梯度函数的信息自动调整其取值,以改善算法的数值表现.在合适的假设条件下,建立了新的非单调保守BFGS算法的全局收敛性.用基准测试优化问题测试了算...     

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.     

Nonmonotone derivative-free methods for nonlinear equations

In this paper we study nonmonotone globalization techniques, in connection with iterative derivative-free methods for solving a system of nonlinear equations in several variables. First we define and analyze a class of nonmonotone derivative-free linesearch techniques for unconstrained minimization of differentiable functions. Then we introduce a globalization scheme, which combines nonmonotone watchdog rules and nonmonotone linesearches, and we study the application of this scheme to some recent extensions of the Barzilai–Borwein gradient method and to hybrid stabilization algorithms employing linesearches along coordinate directions. Numerical results on a set of standard test problems show that the proposed techniques can be of value in the solution of large-dimensional systems of equations.     

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.     

Monotone and nonmonotone trust-region-based algorithms for large scale unconstrained optimization problems

Two trust regions algorithms for unconstrained nonlinear optimization problems are presented: a monotone and a nonmonotone one. Both of them solve the trust region subproblem by the spectral projected gradient (SPG) method proposed by Birgin, Martínez and Raydan (in SIAM J. Optim. 10(4):1196?C1211, 2000). SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. The simplicity (only requires matrix-vector products, and one projection per iteration) and rapid convergence of this scheme fits nicely with globalization techniques based on the trust region philosophy, for large-scale problems. In the nonmonotone algorithm the trial step is evaluated by acceptance via a rule which can be considered a generalization of the well known fraction of Cauchy decrease condition and a generalization of the nonmonotone line search proposed by Grippo, Lampariello and Lucidi (in SIAM J. Numer. Anal. 23:707?C716, 1986). Convergence properties and extensive numerical results are presented. Our results establish the robustness and efficiency of the new algorithms.     

Nonmonotone Levenberg–Marquardt Algorithms and Their Convergence Analysis

In this paper, two nonmonotone Levenberg–Marquardt algorithms for unconstrained nonlinear least-square problems with zero or small residual are presented. These algorithms allow the sequence of objective function values to be nonmonotone, which accelerates the iteration progress, especially in the case where the objective function is ill-conditioned. Some global convergence properties of the proposed algorithms are proved under mild conditions which exclude the requirement for the positive definiteness of the approximate Hessian T(x). Some stronger global convergence properties and the local superlinear convergence of the first algorithm are also proved. Finally, a set of numerical results is reported which shows that the proposed algorithms are promising and superior to the monotone Levenberg–Marquardt algorithm according to the numbers of gradient and function evaluations.     

Nonmonotone Globalization Techniques for the Barzilai-Borwein Gradient Method

In this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems.     

Secant algorithms with nonmonotone trust region that employs fletcher penalty function for constrained optimization

In this paper, we present a family of secant algorithms in association with nonmonotone trust region strategy for nonlinear equality constrained optimization problems. The proposed algorithms are globally convergent while keeping the local superlinear rate by introducing Fletcher's penalty function as merit function.     

Nonmonotone and Monotone Active-Set Methods for Image Restoration,Part 1: Convergence Analysis

Active-set methods based on augmented Lagrangian smoothing of nondifferentiable optimization problems arising in image restoration are discussed. One-dimensional image restoration problems and two different formulations of two-dimensional image restoration problems are given. Both nonmonotone and monotone active-set algorithms are described and finite-step convergence of the algorithms is considered.     

一类新的信赖域算法的全局收敛性

本文对于无约束最优化问题提出了一类非单调的信赖域算法，它是通常的单调信赖域算法的推广。当目标函数是有下界的连续可微函数，而且它的二阶导数的近似的模是线性地依赖于迭代次数时，我们证明了新算法的整体收敛性。     

单值优化的非单调信赖域方法

提供了一种单值优化的非调信赖技术结合投影牛顿法的算法，在合理的条件下，证明了算法的整体收敛性和局部二阶收敛速率。     

一类带非单调线搜索的信赖域算法

通过将非单调Wolfe线搜索技术与传统的信赖域算法相结合,我们提出了一类新的求解无约束最优化问题的信赖域算法.新算法在每一迭代步只需求解一次信赖域子问题,而且在每一迭代步Hesse阵的近似都满足拟牛顿条件并保持正定传递.在一定条件下,证明了算法的全局收敛性和强收敛性.数值试验表明新算法继承了非单调技术的优点,对于求解某...     

Strong convergence properties of a modified nonmonotone smoothing algorithm for the SCCP

The smoothing algorithms have been successfully applied to solve the symmetric cone complementarity problem (denoted by SCCP), which in general have the global and local superlinear/quadratic convergence if the solution set of the SCCP is nonempty and bounded. Huang, Hu and Han [Science in China Series A: Mathematics, 52: 833–848, 2009] presented a nonmonotone smoothing algorithm for solving the SCCP, whose global convergence is established by just requiring that the solution set of the SCCP is nonempty. In this paper, we propose a new nonmonotone smoothing algorithm for solving the SCCP by modifying the version of Huang-Hu-Han’s algorithm. We prove that the modified nonmonotone smoothing algorithm not only is globally convergent but also has local superlinear/quadratical convergence if the solution set of the SCCP is nonempty. This convergence result is stronger than those obtained by most smoothing-type algorithms. Finally, some numerical results are reported.     

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.     

一类优化问题的非单调信赖域算法

本文提出了一类带不等式约束和简单边界的非线性优化问题的非单调信赖域算法,在一定的条件下,证明了算法的全局收敛性,并通过数值实验验证了算法的合理性。     

Levenberg-Marquardt method with a general LM parameter and a nonmonotone trust region technique

We propose a new Levenberg-Marquardt (LM) method for solving the nonlinear equations. The new LM method takes a general LM parameter \lambda_k=\mu_k[(1-\theta)\|F_k\|^\delta+\theta\|J_k^TF_k\|^\delta] where \theta\in[0,1] and \delta\in(0,3) and adopts a nonmonotone trust region technique to ensure the global convergence. Under the local error bound condition, we prove that the new LM method has at least superlinear convergence rate with the order \min\{1+\delta,4-\delta,2\}. We also apply the new LM method to solve the nonlinear equations arising from the weighted linear complementarity problem. Numerical experiments indicate that the new LM method is efficient and promising.     

A nonmonotone filter method for nonlinear optimization

We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.     

A nonmonotone PSB algorithm for solving unconstrained optimization

PSB (Powell-Symmetric-Broyden) algorithm is a very important algorithm and has been extensively used in trust region methods. However, there are few studies on the line search type PSB algorithm. The primary reason is that the direction generated by this class of algorithms is not necessarily a descent direction of the objective function. In this paper, by combining a nonmonotone line search technique with the PSB method, we propose a nonmonotone PSB algorithm for solving unconstrained optimization. Under proper conditions, we establish global convergence and superlinear convergence of the proposed algorithm. At the same time we verify the efficiency of the proposed algorithm by some numerical experiments.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.