Convex Separation from Optimization via Heuristics

Abstract

Let $K$ be a full-dimensional convex subset of ${\mathbb{R}}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.

Cited by in corpus (1)

• Convex separation from convex optimization for large-scale problems