A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear Programs

We consider the following semi-infinite linear programming problems: max (resp., min) c ^T x s.t. yTAix+(di)Tx≤bi (resp., yTAix+(di)Tx≥bi), for all y∈ Y _i , for i= 1 , … , N, where Yi⊆R+m are given compact convex sets and Ai∈R+mi×n, b=(b1,…bN)∈R+N, di∈R+n, and c∈R+n are given non-negative matrices and vectors. This general framework is useful in modeling many interesting problems. For example, it can be used to represent a sub-class of robust optimization in which the coefficients of the constraints are drawn from convex uncertainty sets Y _i , and the goal is to optimize the objective function for the worst case choice in each Y _i . When the uncertainty sets Y _i are ellipsoids, we obtain a sub-class of second-order cone programming. We show how to extend the multiplicative weights update method to derive approximation schemes for the above packing and covering problems. When the sets Y _i are simple, such as ellipsoids or boxes, this yields substantial improvements in running time over general convex programming solvers. We also consider the mixed packing/covering problem, in which both packing and covering constraints are given, and the objective is to find an approximately feasible solution.