Optimization Online


A Simple Variant of the Mizuno-Todd-Ye Predictor-Corrector Algorithm and its Objective-Function-Free Complexity

Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)
Takashi Tsuchiya (tsuchiya***at***grips.ac.jp)

Abstract: In this paper, we propose a simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming problem (LP). Our variant executes a natural finite termination procedure at each iteration and it is easy to implement the algorithm. Our algorithm admits an objective-function free polynomial-time complexity when it is applied to LPs whose dual feasible region is bounded.

Keywords: Linear programming problem,, Interior point method, Layered least squares interior point method, Iteration complexity, Strong polynomiality.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: First author: Tokyo Institute of Technology Second author: National Graduate Institute for Policy Studies Date: April 2011.

Download: [PDF]

Entry Submitted: 04/28/2011
Entry Accepted: 04/28/2011
Entry Last Modified: 05/01/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society