Title: How good are Global Newton methods?
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)
Subjects: LINEAR PROGRAMMING, INEQUALITIES, ITERATIONS, NUMERICAL METHODS AND PROCEDURES