How good are Global Newton methods?
By: Allen Goldstein
Contributors: Naval Postgraduate School (U.S.). Dept. of Mathematics
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1988
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Subjects: LINEAR PROGRAMMING; INEQUALITIES; ITERATIONS; NUMERICAL METHODS AND PROCEDURES
Other titles: NPS-53-88-010.; NPS-53-89-010.
Description: 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)
Notes: Title from cover.

"NPS-53-89-010."--part I.

"NPS-53-88-010."--part II.

"February 1989."--part I.

"September 1988."--part II.

AD A208 390--pat I.

AD A201 099--part II.

Includes bibliographical references.

aq/aq cc:9116 06/25/98