How good are Global Newton methods?
Goldstein, Allen A.
MetadataShow full item record
Pt.1. 1) Relying on a theorem of Nemerovsky and Yuden(1979) a lower bound is given for the efficiency of global Newton methods over the class C1(mu, Lambda). 2) The efficiency of Smale's global Newton method in a simple setting with a nonsingular, Lipschitz-continuous Jacobian is considered. The efficiency is characterized by 2 parameters, the condition number Q and the smoothness S. The efficiency is sensitive to S, and insensitive to Q. Keywords: Unconstrained optimization, Computational complexity, Algorithms. (JD)--Pt. 2. Newton's method applied to certain problems with a discontinuous derivative operator is shown to be effective. A global Newton method in this setting is exhibited and its computational complexity is estimated. As an application a method is proposed to solve problems of linear inequalities (linear programming, phase 1). Using an example of the Klee-Minty type due to Blair, it was found that the simplex method (used in super-lindo) required over 2,000 iterations, while the method above required an average of 8 iterations (Newton steps) over 15 random starting values. Keywords; Linear programming; Computational complexity. (JHD)
Approved for public release; distribution is unlimited.
NPS Report NumberNPS-53-88-010
Showing items related by title, author, creator and subject.
Romano, M.; Agrawal, B. (2004);The dynamics equations of a spacecraft consisting of two bodies mutually rotating around a common gimbal axis are derived by the use of the Newton–Euler approach. One of the bodies contains a cluster of single-gimbal var ...
Scott, Melvin; Neta, Beny; Chun, Changbum (2011);There are many methods for the solution of a nonlinear algebraic equation. The methods are classified by the order, informational efficiency and efficiency index. Here we consider other criteria, namely the basin of ...
Appleget, Jeffrey; Fox, William P. (2001);Newton's Method is used to find roots of differentiable functions, and is easily adapted to find critical points of twice-differentiable functions. Students often rely on the numerical results of Newton's Method without ...