A Quadratically Convergent O(square root of nL-Iteration Algorithm for Linear Programming

Abstract

Recently it was demonstrated that Mizuno-Todd-Ye's predictor-corrector interior-point algorithm for linear programming maintains the O(square root of nL)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish he quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1991
Accession Number
ADA455490

Entities

People

  • O. Gueler
  • Richard A. Tapia
  • Y. Ye
  • Yinglong Zhang

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Convergence
  • Evolutionary Algorithms
  • Heuristic Methods
  • Information Operations
  • Iterations
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Military Research
  • Numbers
  • Operations Research
  • Sequences
  • Square Roots

Fields of Study

  • Mathematics

Readers

  • Operations Research