A one-phase algorithm for semi-infinite linear programming

The paper presents an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. The paper proves the convergence of this algorithm in two steps. First, it shows that the algorithm can find an •-optimal solution after finitely many iterations. Then, the paper uses this result to show that it can find an optimal solution in the limit. It also estimates how good an •-optimal solution is compared to an optimal solution and gives an upper bound on the total number of iterations needed for finding an •-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.