On the Superlinear Convergence of Interior Point Algorithms for a General Class of Problems

Abstract

This paper extends the Q-superlinear convergence theory recently developed by Zhang, Tapia and Dennis for a class of interior-point linear programming algorithms to similar interior-point algorithms for quadratic programming and for linear complementary problems. Our unified approach consists of viewing all these algorithms as a damped Newton method applied to perturbations of a general problem. We establish a set of sufficient conditions for these algorithms to achieve Q-superlinear convergence. The key ingredients consist of asymptotically taking the step to the boundary of the positive orthant and letting the centering parameter approach zero at a specific rate. The construction of algorithms that have both the global property of polynomiality and the local property of superlinear convergence will be the subject of further research.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1991
Accession Number
ADA455378

Entities

People

  • Florian Potra
  • Richard A. Tapia
  • Yin Zhang

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Boundaries
  • Computer Programming
  • Convergence
  • Evolutionary Algorithms
  • Heuristic Methods
  • Information Operations
  • Linear Programming
  • Mathematics
  • Operations Research
  • Quadratic Programming
  • Statistics

Fields of Study

  • Mathematics

Readers

  • Operations Research