Semi-Infinite Programming
Hui Hu · 1989
We consider an extension of the affine scaling algorithm for linear programming problems with free variables to problems having infinitely many constraints, and explore the relationship between this algorithm and the finite affine scaling method applied to a discretization of the problem. Key words: Affine scaling, semi-infinite linear programming, free variables. In this note we are concerned with the generalization given by Ferris and Philpott [3] of the affine scaling algorithm discovered by Dikin [2] to solve semi-infinite linear programming problems, in which the number of variables is finite, but the number of constraints is not. In [3] a discrepancy is pointed out between the classical algorithm and its generalization. The purpose of this note is to explain the dis-crepancy. Ferris and Philpott [3] propose an affine scaling algorithm for linear programs of the following form: minimize c V x subject to Ax- z = b, z~>0. Since the variables x are unrestricted in sign, it seems natural that only the z variables should undergo the scaling transformation at each stage. Given a feasible point (x (k~, z(k~), with zJ k)> 0 for each component j, a single iteration of the algorithm in [3] performs the following steps.