Multiplicative Weight Update Algorithms for Packing and Covering Semi-Infinite Linear Programs

  • Waleed Najy

Student thesis: Doctoral Thesis

Abstract

We consider the following semi-infinite linear programming problems: max (resp., min) c T x s.t. y T Aix + (d i ) T x ≤ bi (resp., y T Aix + (d i ) T x ≥ bi), for all y ∈ Yi , for i = 1, . . . , N, where Yi ⊆ R m + are given compact convex sets and Ai ∈ R mi×n + , b = (b1, . . . bN ) ∈ R N + , d i ∈ R n +, and c ∈ R n + are given non-negative matrices and vectors. This general framework is useful in modelling 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 Yi , and the goal is to optimise the objective function for the every vector in each Yi . When the uncertainty sets Yi are ellipsoids, we obtain a sub-class of Second-Order Cone Programming. We show how to extend the multiplicative weight update method to derive approximation schemes for the above packing and covering problems. When the sets Yi 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. Finally, we consider extensions to the semiinfinite problem of methods that achieve oracle complexities faster than O˜( −2 ).
Date of AwardDec 2016
Original languageAmerican English
SupervisorKhaled ElBassioni (Supervisor)

Keywords

  • Linear Program
  • Semi-Infinite Linear
  • Algorithms
  • multiplicative Weight Update.

Cite this

'