INTERIOR-POINT ALGORITHMS FOR SEMIINFINITE PROGRAMMING

In order to study the behavior of interior-point methods on very large -scale linear programming problems, we consider the application of suc h methods to continuous semi-infinite linear programming problems in b oth primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite- dimensional) interior-point methods. We find that while many methods a re invariant, several, including all those with the currently best com plexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our beli ef that for a method to work well on large-scale linear programming pr oblems, it should be effective on fine discretizations of a semi-infin ite problem and it should have a natural extension to the limiting sem i-infinite case.