A Simple Variant of the Mizuno-Todd-Ye Predictor-Corrector Algorithm and its Objective-Function-Free Complexity
Tomonari Kitahara (kitahara.t.abm.titech.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.
Entry Submitted: 04/28/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|