separation oracle

Simple Iterative Methods for Linear Optimization over Convex Sets

  • Daniel Dadush
  • Christopher Hojny
  • Sophie Huiberts
  • Stefan Weltge
    • Categories Linear Programming Tags , ,

    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 … Read more

    Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

  • Robert M. Freund
  • Jorge Vera
    • Categories Convex Optimization Tags , , , ,

    Consider the following supposedly-simple problem: “compute x \in S” where S is a convex set conveyed by a separation oracle, with no further information (e.g., no bounding ball containing or intersecting S, etc.). Our interest in this problem stems from fundamental issues involving the interplay of computational complexity, the geometry of S, and the stability … Read more