How Good Are Global Newton Methods? Part 2

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1988
Accession Number
ADA201099

Entities

People

  • Allen A. Goldstein

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Banach Space
  • Computational Complexity
  • Computer Programming
  • Construction
  • Equations
  • Heuristic Methods
  • Hilbert Space
  • Inequalities
  • Iterations
  • Linear Programming
  • Mathematics
  • Sequences
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Operations Research