A one-phase algorithm for semi-infinite linear programming |
| |
Authors: | Hui Hu |
| |
Institution: | (1) Department of Operations Research, Stanford University, 94305 Stanford, CA, USA |
| |
Abstract: | We present 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. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give 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. |
| |
Keywords: | Semi-infinite linear programming generalized linear programming convex programming linear programming duality |
本文献已被 SpringerLink 等数据库收录! |
|