A Centered Projective Algorithm for Linear Programming

Abstract

We describe a projective algorithm for linear programming that shares features with Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in O the square root of n x L iterations like the latter methods. (Here n is the number of variables and L the input size of the problem.) However, it is motivated by seeking reductions in a suitable potential function as in projective algorithms, and the approximate centering is an automatic byproduct of our choice of potential function.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1988
Accession Number
ADA192100

Entities

People

  • Michael J. Todd
  • Yinyu Ye

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Automatic
  • Computer Programming
  • Economic Systems
  • Economics
  • Engineering
  • Equations
  • Heuristic Methods
  • Industrial Engineering
  • Iterations
  • Linear Programming
  • Operations Research
  • Quadratic Programming
  • Sequences
  • Systems Engineering
  • Trajectories
  • Universities

Readers

  • Operations Research