DIMACS TR: 93-73

Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program



Author: Robert J. Vanderbei

ABSTRACT

Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield valuable insight into the behavior of the underlying linear programming algorithm when the number of constraints or the number of variables is very large. In this paper, we study the behavior of the affine-scaling algorithm on a particular semi-infinite linear programming problem. We show that the continuous trajectories converge to the optimal solution but that, for any strictly positive step, there are starting points for which the discrete algorithm converges to nonoptimal boundary points.

Key words: semi-infinite programming, affine-scaling algorithms, interior point methods, linear programming theory, linear programming algorithms

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-73.ps


DIMACS Home Page