A superlinearly convergent ODE-type trust region algorithm for nonsmooth nonlinear equations

This paper presents a new trust region algorithm for solving nonsmooth nonlinear equation problems which posses the smooth plus non-smooth decomposition. At each iteration, this method obtains a trial step by solving a system of linear equations, hence avoiding the need for solving a quadratic programming subproblem with a trust region bound. From a computational point of view, this approach may reduce computational effort and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and locally super-linearly convergent. Some numerical examples are reported.     

A new trust region method for nonlinear equations

In this paper, a new trust region method for the system of nonlinear equations is presented in which the determining of the trust region radius incorporates the information of its natural residual. The global convergence is obtained under mild conditions. Unlike traditional trust region method, the superlinear convergence of the method is proven under the local error bound condition. This condition is weaker than the nondegeneracy assumption which is necessary for superlinear convergence of traditional trust region method. We also propose an approximate algorithm for the trust region subproblem. Preliminary numerical experiments are reported. Acknowledgements.The authors are indebted to our supervisor, Professor Y.-X. Yuan, for his excellent guidance and Jorge J. Moré for his subroutine. And we would like to thank the referees for their valuable suggestions and comments.     

An interior trust region algorithm for solving linearly constrained nonlinear optimization

In this paper, an interior point algorithm based on trust region techniques is proposed for solving nonlinear optimization problems with linear equality constraints and nonnegative variables. Unlike those existing interior-point trust region methods, this proposed method does not require that a general quadratic subproblem with a trust region bound be solved at each iteration. Instead, a system of linear equations is solved to get a search direction, and then a linesearch of Armijo type is performed in this direction to obtain a new iteration point. From a computational point of view, this approach may in general reduce a computational effort, and thus improve the computational efficiency. Under suitable conditions, it is proven that any accumulation of the sequence generated by the algorithm satisfies the first-order optimality condition.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

An improved trust region method for unconstrained optimization

In this paper,we propose an improved trust region method for solving unconstrained optimization problems.Different with traditional trust region methods,our algorithm does not resolve the subproblem within the trust region centered at the current iteration point,but within an improved one centered at some point located in the direction of the negative gradient,while the current iteration point is on the boundary set.We prove the global convergence properties of the new improved trust region algorithm and give the computational results which demonstrate the effectiveness of our algorithm.     

非线性优化的非单调信赖域算法及全局收敛性

Abstract. A trust region algorithm for equality constrained optimization is given in this paper.The algorithm does not enforce strict monotonicity of the merit function for every iteration.Global convergence of the algorithm is proved under the same conditions of usual trust regionmethod.     

A trust region algorithm for a class of nonlinear optimization

Abstract. This paper presents a trust region algorithm for nonlinear optimization with linear in-equality constraints. The global convergence of the algorithm is proved. Local quadratic con-vergence is obtained for a strong local minimizer.     

An interior algorithm for nonlinear optimization that combines line search and trust region steps

An interior-point method for nonlinear programming is presented. It enjoys the flexibility of switching between a line search method that computes steps by factoring the primal-dual equations and a trust region method that uses a conjugate gradient iteration. Steps computed by direct factorization are always tried first, but if they are deemed ineffective, a trust region iteration that guarantees progress toward stationarity is invoked. To demonstrate its effectiveness, the algorithm is implemented in the Knitro [6,28] software package and is extensively tested on a wide selection of test problems. These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579, and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004. This author was supported by Asociación Mexicana de Cultura, A.C. and CONACyT grant 39372-A.     

Inexact trust region method for large sparse systems of nonlinear equations

The main purpose of this paper is to prove the global convergence of the new trust region method based on the smoothed CGS algorithm. This method is surprisingly convenient for the numerical solution of large sparse systems of nonlinear equations, as is demonstrated by numerical experiments. A modification of the proposed trust region method does not use matrices, so it can be used for large dense systems of nonlinear equations.     

A trust region interior point algorithm for infinite dimensional nonlinear programming

A trust region interior point algorithm for infinite dimensional nonlinear problem, which is motivated by the application of black-box approach to the distributed parameter system optimal control problem with equality and inequality constraints on states and controls, and with bounds on the controls is formulated. By introducing a proper functional which is analogous to the Lagrange function, both equality and inequality constraints can be treated identically and the first order optimality condition is given, then based on the works of Coleman, Ulbrich and Heinkenschloss, the trust region interior point algorithm which is employed to solve the optimization problem under consideration is presented.     

A nonmonotone filter trust region method for the system of nonlinear equations

In this paper, we present a nonmonotone filter trust region method to attack the system of nonlinear equations. The system of nonlinear equations is transformed into a constrained nonlinear programming problem at each step: some equations are treated as constraints while the others act as objective functions. Compared with the traditional filter strategies, our algorithm is flexible to accept trail steps by means of the nonmonotone filter technique. Moreover, the restoration phase is not needed so that the scale of the calculation is decreased in a certain degree. Global convergence is proven under some suitable conditions. Numerical experiments also show the efficiency of the algorithm.     

An effective adaptive trust region algorithm for nonsmooth minimization

In this paper, an adaptive trust region algorithm that uses Moreau–Yosida regularization is proposed for solving nonsmooth unconstrained optimization problems. The proposed algorithm combines a modified secant equation with the BFGS update formula and an adaptive trust region radius, and the new trust region radius utilizes not only the function information but also the gradient information. The global convergence and the local superlinear convergence of the proposed algorithm are proven under suitable conditions. Finally, the preliminary results from comparing the proposed algorithm with some existing algorithms using numerical experiments reveal that the proposed algorithm is quite promising for solving nonsmooth unconstrained optimization problems.     

等式与界约束非线性优化信赖域算法的全局收敛

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＣｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ :ｍｉｎｉｍｉｚｅｆ(ｘ)ｓｕｂｊｅｃｔｔｏＣ(ｘ) =0 ,　ａ≤ｘ≤ｂ ,( 1 .1 )ｗｈｅｒｅｆ(ｘ) :Ｒｎ→Ｒ ,Ｃ(ｘ) =(ｃ1(ｘ) ,ｃ2 (ｘ) ,...,ｃｍ(ｘ) ) Ｔ:Ｒｎ→Ｒｍ ａｒｅｔｗｉｃｅｃｏｎｔｉｎｕｏｕｓｌｙｄｉｆｆｅｒｅｎｔｉａｂｌｅ,ｍ≤ｎ ,ａ ,ｂ∈Ｒｎ.Ｔｒｕｓｔｒｅｇｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｖｅｒｙｅｆｆｅｃｔｉｖｅｆｏｒｓｏｌｖｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉ…     

Nonmonotonic trust region algorithm

A nonmonotonic trust region method for unconstrained optimization problems is presented. Although the method allows the sequence of values of the objective function to be nonmonotonic, convergence properties similar to those for the usual trust region method are proved under certain conditions, including conditions on the approximate solutions to the subproblem. To make the solution satisfy these conditions, an algorithm to solve the subproblem is also established. Finally, some numerical results are reported which show that the nonmonotonic trust region method is superior to the usual trust region method according to both the number of gradient evaluations and the number of function evaluations.The authors would like to thank Professor L. C. W. Dixon for his useful suggestions.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

Augmented lagrangian nonlinear programming algorithm that uses SQP and trust region techniques

An augmented Lagrangian nonlinear programming algorithm has been developed. Its goals are to achieve robust global convergence and fast local convergence. Several unique strategies help the algorithm achieve these dual goals. The algorithm consists of three nested loops. The outer loop estimates the Kuhn-Tucker multipliers at a rapid linear rate of convergence. The middle loop minimizes the augmented Lagrangian functions for fixed multipliers. This loop uses the sequential quadratic programming technique with a box trust region stepsize restriction. The inner loop solves a single quadratic program. Slack variables and a constrained form of the fixed-multiplier middleloop problem work together with curved line searches in the inner-loop problem to allow large penalty wieghts for rapid outer-loop convergence. The inner-loop quadratic programs include quadratic onstraint terms, which complicate the inner loop, but speed the middle-loop progress when the constraint curvature is large.The new algorithm compares favorably with a commercial sequential quadratic programming algorithm on five low-order test problems. Its convergence is more robust, and its speed is not much slower.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

A trust region algorithm for nonsmooth optimization

A trust region algorithm is proposed for minimizing the nonsmooth composite functionF(x) = h(f(x)), wheref is smooth andh is convex. The algorithm employs a smoothing function, which is closely related to Fletcher's exact differentiable penalty functions. Global and local convergence results are given, considering convergence to a strongly unique minimizer and to a minimizer satisfying second order sufficiency conditions.     

An exponentially convergent algorithm for nonlinear differential equations in Banach spaces

An exponentially convergent approximation to the solution of a nonlinear first order differential equation with an operator coefficient in Banach space is proposed. The algorithm is based on an equivalent Volterra integral equation including the operator exponential generated by the operator coefficient. The operator exponential is represented by a Dunford-Cauchy integral along a hyperbola enveloping the spectrum of the operator coefficient, and then the integrals involved are approximated using the Chebyshev interpolation and an appropriate Sinc quadrature. Numerical examples are given which confirm theoretical results.