ON THE LIMITING PROPERTIES OF THE AFFINE-SCALING DIRECTIONS

Hugo J. Lara (hugolucla.edu.ve)
Clovis C. Gonzaga (clovismtm.ufsc.br)
Levent Tuncel (ltuncelmath.uwaterloo.ca)

Abstract: We study the limiting properties of the affine-scaling directions for linear programming problems. The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms. We establish new relations between this measure and some other complexity measures which are used in the complexity analyses of algorithms for linear programming. We also provide a new characterization of the smallest large variable complexity measure of Ye.

Keywords: Affine-scaling direction, linear programming, complexity measures, interior-point methods

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

Citation: Research Report 2003--24, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, August 2003

Download: [Postscript][PDF]

Entry Submitted: 08/27/2003
Entry Accepted: 08/27/2003
Entry Last Modified: 08/27/2003

Modify/Update this entry