A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs

详细信息    查看全文

• 关键词：Multiplicative weights update ; Robust optimization ; Second ; order cone programming ; Packing and covering
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10138
• 期：1
• 页码：78-91
• 丛书名：Approximation and Online Algorithms
• ISBN：978-3-319-51741-4
• 卷排序：10138

文摘

We consider the following semi-infinite linear programming problems: \(\max \) (resp., \(\min \)) \(c^Tx\) s.t. \(y^TA_ix+(d^i)^Tx \le b_i\) (resp., \(y^TA_ix+(d^i)^Tx \ge b_i)\), for all \(y \in \mathcal Y_i\), for \(i=1,\ldots ,N\), where \(\mathcal Y_i\subseteq \mathbb {R}^{m_i}_+\) are given compact convex sets and \(A_i\in \mathbb {R}^{m_i\times n}_+\), \(b=(b_1,\ldots ,b_N)\in \mathbb {R}_+^N\), \(d_i\in \mathbb {R}_+^n\), and \(c\in \mathbb {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 \(\mathcal Y_i\), and the goal is to optimize the objective function for the worst-case choice in each \(\mathcal Y_i\). When the uncertainty sets \(\mathcal 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 \(\mathcal Y_i\) are simple, such as ellipsoids or boxes, this yields substantial improvements in the running time over general convex programming solvers.