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

Abstract

In this note we consider a large step modification of the Mizuno-Todd-Ye O(square root of nL) predictor-corrector interior-point algorithm for linear programming. We demonstrate that the modified algorithm maintains its O(square root of nL)-iteration complexity, while exhibiting superlinear convergence for general problems and quadratic convergence for nondegenerate problems. To our knowledge, this is the first construction of a superlinearly convergent algorithm with O(square root of nL)-iteration complexity.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1991
Accession Number
ADA452256

Entities

People

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

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Information Operations
  • Iterations
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Numbers
  • Operations Research
  • Simplex Method
  • Square Roots

Fields of Study

  • Mathematics

Readers

  • Operations Research