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