We give simple iterative methods for computing approximately optimal primal and dual solutions for the problem of maximizing a linear functional over a convex set $K$ given by a separation oracle. In contrast to prior work, our algorithms directly output primal and dual solutions and avoid a common requirement of binary search on the objective value. Under the assumption that $K$ contains a ball of radius $r$ and is contained inside the origin centered ball of radius $R$, using $O(\frac{R^4}{r^2 \varepsilon^2})$ iterations and calls to the oracle, our main method outputs a point $x \in K$ together with a non-negative combination of the inequalities outputted by the oracle and one inequality of the $R$-ball certifying that $x$ is an additive $\varepsilon$-approximate solution. In the setting where the inner $r$-ball is centered at the origin, we give a simplified variant which outputs a multiplicative $(1 + \varepsilon)$-approximate primal and dual solutions using $O(\frac{R^2}{r^2 \varepsilon^2})$ iterations and calls to the oracle. Similar results hold for packing type problems. Our methods are based on variants of the classical Von Neumann and Frank-Wolfe algorithms. Our algorithms are also easy to implement, and we provide an experimental evaluation of their performance on a testbed of maximum matching and stable set instances. We further compare variations of our method to the standard cut loop implemented using Gurobi. This comparison reveals that in terms of iteration count, our methods converge on average faster than the standard cut loop on our test set.
Article
View Simple Iterative Methods for Linear Optimization over Convex Sets