Paper Info
Title
Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
Abstract
In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve <img src="/fulltext-image.asp?format=htmlnonpaginated&src=M58Q126882XM7272_html\10107_2005_Article_BF01585181_TeX2GIFIE1.gif" border="0" alt=" $$O\left( {\sqrt {nL} } \right)$$ " /> step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
Year
DOI
Venue
1993
10.1007/BF01585181
Math. Program.
Keywords
DocType
Volume
Linear programming, Karmarkar's algorithm, Projective algorithm, Standard form
Journal
62
Issue
ISSN
Citations 
1-3
1436-4646
1
PageRank 
References 
Authors
0.35
18
1
Name
Order
Citations
PageRank
Kurt M. Anstreicher163386.40