On a Newton-like method for constrained nonlinear minimization via slack variables

We show that Tapia's quasi-Newton diagonalized approach to constrained minimization can be formulated in such a way that no linear systems have to be solved of dimension larger than the natural ones or which present singularities. Numerical experiments indicate fast local convergence, but also substantial difficulties of global convergence.This work was supported by the National Science Council of Italy in the framework of the SOFTMAT project. Part of the work was done during visits at the Computer Science Department, Stanford University, and at the Numerical Optimization Centre, Hatfield Polytechnic; the author thanks Prof. G. Golub and Prof. L. Dixon for providing a stimulating atmosphere. Thanks are also due to Dr. M. Bertocchi, University of Bergamo, for collaboration in performing the numerical experiments.     

Three new algorithms based on the sequential secant method

We introduce three new implementations of the sequential secant method for solving nonlinear simultaneous equations. Following the ideas of Gragg and Stewart, we store orthogonal factorizations of some of the matrices involved. Degeneracy in the increments of the independent variable is corrected according to simple and theoretically justified procedures. Some numerical experiences are also given.     

A RESTARTING DIRECTION FOR THE CONJUGATE GRADIENT METHOD

The main purpose of this paper is to provide a restarting direction for improving on the standard conjugate gradient method.If a drastic non-quadratic behaviour of the objective function is observed in the neighbour of xk,then a restart should be done.The scaling symmetric rank-one update with Davidon's optimal criterion is applied to generate the restarting direction.It is proved that the conjugate gradient method with this strategy retains the quadratic termination.Numerical experiments show that it is successful.     

基于修正拟牛顿方程的两阶段步长非单调稀疏对角变尺度梯度投影算法

基于修正拟牛顿方程, 利用Goldstein-Levitin-Polyak (GLP)投影技术, 建立了 求解带凸集约束的优化问题的两阶段步长Zhang H.C.非单调变尺度梯度投影方法, 证明了算法的全局收敛性. 数值实验表明算法是有效的, 适合求解大规模问题.     

A Globally Convergent Trust-Region Method for Large-Scale Symmetric Nonlinear Systems

This study presents a novel adaptive trust-region method for solving symmetric nonlinear systems of equations. The new method uses a derivative-free quasi-Newton formula in place of the exact Jacobian. The global convergence and local quadratic convergence of the new method are established without the nondegeneracy assumption of the exact Jacobian. Using the compact limited memory BFGS, we adapt a version of the new method for solving large-scale problems and develop the dogleg scheme for solving the associated trust-region subproblems. The sufficient decrease condition for the adapted dogleg scheme is established. While the efficiency of the present trust-region approach can be improved by using adaptive radius techniques, utilizing the compact limited memory BFGS adjusts this approach to handle large-scale symmetric nonlinear systems of equations. Preliminary numerical results for both medium- and large-scale problems are reported.     

A heuristic algorithm for nonlinear programming

In this paper, a heuristic algorithm for nonlinear programming is presented. The algorithm uses two search directions, and the Hessian of the Lagrangian function is approximated with the BFGS secant update. We show that the sequence of iterates convergeq-superlinearly if the sequence of approximating matrices satisfies a particular condition. Numerical results are presented.     

Preconditioned low-order Newton methods

In this paper, low-order Newton methods are proposed that make use of previously obtained second-derivative information by suitable preconditioning. When applied to a particular 2-dimensional Newton method (the LS method), it is shown that a member of the Broyden family of quasi-Newton methods is obtained. Algorithms based on this preconditioned LS model are tested against some variations of the BFGS method and shown to be much superior in terms of number of iterations and function evaluations, but not so effective in terms of number of gradient evaluations.     

Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems

In this paper, some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences {x _k } convergingq-superlinearly to the solution. Furthermore, under mild assumptions, aq-quadratic convergence rate inx is also attained. Other features of these algorithms are that only the solution of linear systems of equations is required at each iteration and that the strict complementarity assumption is never invoked. First, the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied, and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle, and Wang is given.This research was supported by the National Research Program Metodi di Ottimizzazione per la Decisioni, MURST, Roma, Italy.     

A Modified Rank One Update Which Converges Q-Superlinearly

Quasi-Newton methods are generally held to be the most efficient minimization methods for small to medium sized problems. From these the symmetric rank one update of Broyden (Math. Comp., vol. 21, pp. 368–381, 1967) has been disregarded for a long time because of its potential failure. The work of Conn, Gould and Toint (Math. Prog., vol. 50, pp. 177–195, 1991), Kelley and Sachs (COAP, vol. 9, pp. 43–64, 1998) and Khalfan, Byrd and Schnabel (SIOPT, vol. 3, pp. 1–24, 1993; SIOPT, vol. 6, pp. 1025–1039, 1996) has renewed the interest in this method. However the question of boundedness of the generated matrix sequence has not been resolved by this work. In the present paper it is shown that a slightly modified version of this update generates bounded updates and converges superlinearly for uniformly convex functions. Numerical results support these theoretical considerations.