A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

An inexact secant algorithm for large scale nonlinear systems of equalities and inequalities

In this paper, an inexact secant algorithm in association with nonmonotone technique and filter is proposed for solving the large scale nonlinear systems of equalities and inequalities. The systems are transformed into a continuous constrained optimization solved by inexact secant algorithm. Global convergence of the proposed algorithm is established under the reasonable conditions. Numerical results validate the effectiveness of our approach.     

A Nonmonotone Trust Region Algorithm for Nonlinear Optimization Subject to General Constraints

In this paperwe present a nonmonotone trust region algorthm for general nonlinear constrained optimization problems.The main idea of this paper is to combine Yuan‘‘‘‘s technique[1]with a nonmonotone method similar to Ke and Han[2].This new algorithm may not only keep the robust properties of the algorithm given by Yuan,but also have some advantages led by the nonmonotone technique.Under very mild conditions,global convergence for the algorithm is given.Numerical experiments demostrate the efficency of the algorithm.     

解大型无约束优化的新的非单调简单模型BB-TR方法（英文）

The trust region(TR) method for optimization is a class of effective methods.The conic model can be regarded as a generalized quadratic model and it possesses the good convergence properties of the quadratic model near the minimizer.The Barzilai and Borwein(BB) gradient method is also an effective method,it can be used for solving large scale optimization problems to avoid the expensive computation and storage of matrices.In addition,the BB stepsize is easy to determine without large computational efforts.In this paper,based on the conic trust region framework,we employ the generalized BB stepsize,and propose a new nonmonotone adaptive trust region method based on simple conic model for large scale unconstrained optimization.Unlike traditional conic model,the Hessian approximation is an scalar matrix based on the generalized BB stepsize,which resulting a simple conic model.By adding the nonmonotone technique and adaptive technique to the simple conic model,the new method needs less storage location and converges faster.The global convergence of the algorithm is established under certain conditions.Numerical results indicate that the new method is effective and attractive for large scale unconstrained optimization problems.     

A NONMONOTONE TRUST REGION ALGORITHM FOR NONLINEAR OPTIMIZATION SUBJECT TO GENERAL CONSTRAINTS

In this paper we present a nonmonotone trust region algorithm for general nonlinear constrained optimization problems. The main idea of this paper is to combine Yuan's technique[1] with a nonmonotone method similar to Ke and Han [2]. This new algorithm may not only keep the robust properties of the algorithm given by Yuan, but also have some advantages led by the nonmonotone technique. Under very mild conditions, global convergence for the algorithm is given. Numerical experiments demonstrate the efficiency of the algorithm.     

Global convergence on an active set SQP for inequality constrained optimization

Sequential quadratic programming (SQP) has been one of the most important methods for solving nonlinearly constrained optimization problems. In this paper, we present and study an active set SQP algorithm for inequality constrained optimization. The active set technique is introduced which results in the size reduction of quadratic programming (QP) subproblems. The algorithm is proved to be globally convergent. Thus, the results show that the global convergence of SQP is still guaranteed by deleting some “redundant” constraints.     

A NONMOTOTONE ALGORITHM FOR MINIMIZING NONSMOOTH COMPOSITE FUNCTIONS

In this paper, we present a nonmonotone algorithm for solving nonsmooth composite optimization problems. The objective function of these problems is composited by a nonsmooth convex function and a differentiable function. The method generates the search directions by solving quadratic programming successively, and makes use of the nonmonotone line search instead of the usual Armijo-type line search. Global convergence is proved under standard assumptions. Numerical results are given.     

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.     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large scale unconstrained problems.     

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.     

A nonmonotone approximate sequence algorithm for unconstrained nonlinear optimization

A new nonmonotone algorithm is proposed and analyzed for unconstrained nonlinear optimization. The nonmonotone techniques applied in this algorithm are based on the estimate sequence proposed by Nesterov (Introductory Lectures on Convex Optimization: A Basic Course, 2004) for convex optimization. Under proper assumptions, global convergence of this algorithm is established for minimizing general nonlinear objective function with Lipschitz continuous derivatives. For convex objective function, this algorithm maintains the optimal convergence rate of convex optimization. In numerical experiments, this algorithm is specified by employing safe-guarded nonlinear conjugate gradient search directions. Numerical results show the nonmonotone algorithm performs significantly better than the corresponding monotone algorithm for solving the unconstrained optimization problems in the CUTEr (Bongartz et al. in ACM Trans. Math. Softw. 21:123–160, 1995) library.     

无记忆非拟 Newton 算法的导出和全局收敛性

In this paper, a new class of memoryless non-quasi-Newton method for solving unconstrained optimization problems is proposed, and the global convergence of this method with inexact line search is proved. Furthermore, we propose a hybrid method that mixes both the memoryless non-quasi-Newton method and the memoryless Perry-Shanno quasi-Newton method. The global convergence of this hybrid memoryless method is proved under mild assumptions. The initial results show that these new methods are efficient for the given test problems. Especially the memoryless non-quasi-Newton method requires little storage and computation, so it is able to efficiently solve large scale optimization problems.     

A Globally Convergent Method of Constrained Minimization by Solving Subproblems of the Conic Model

A new method for nonlinearly constrained optimization problems is proposed. The method consists of two steps. In the first step, we get a search direction by the linearly constrained subproblems based on conic functions. In the second step, we use a differentiable penalty function, and regard it as the metric function of the problem. From this, a new approximate solution is obtained. The global convergence of the given method is also proved.     

A stable interior penalty method for convex extremal problems

Summary For a nonlinearly constrained convex extremal problem a general interior penalty method is given, that is Hadamard-stable and needs no compactness conditions for convergence. The rate of convergence of the values iso(t) fort+0.     

Preconditioned Spectral Projected Gradient Method on Convex Sets

The spectral gradient method has proved to be effective for solving large-scale unconstrained optimization problems. It has been recently extended and combined with the projected gradient method for solving optimization problems on convex sets. This combination includes the use of nonmonotone line search techniques to preserve the fast local convergence. In this work we further extend the spectral choice of steplength to accept preconditioned directions when a good preconditioner is available. We present an algorithmthat combines the spectral projected gradient method with preconditioning strategies toincrease the local speed of convergence while keeping the global properties. We discuss implementation details for solving large-scale problems.     

Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization

This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved. A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.     

非单调广义对角拟牛顿算法

本文研究了无约束最优化的求解问题.利用新的对角拟牛顿校正和非单调技术,获得了一种非单调广义对角拟牛顿算法.新算法具有低存储、低计算量的特点,非常适合大规模问题的求解,推广了文献[8]的结果.     

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.     

A quadratically-convergent algorithm for general nonlinear programming problems

This paper presents an algorithm for solving nonlinearly constrained nonlinear programming problems. The algorithm reduces the original problem to a sequence of linearly-constrained minimization problems, for which efficient algorithms are available. A convergence theorem is given which states that if the process is started sufficiently close to a strict second-order Kuhn—Tucker point, then the sequence produced by the algorithm exists and convergesR-quadratically to that point.Work sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

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.