Convex Separation from Optimization via Heuristics
<|reference_start|>Convex Separation from Optimization via Heuristics: 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.<|reference_end|>
@article{ioannou2006convex,
    title={Convex Separation from Optimization via Heuristics},
    author={Lawrence M. Ioannou and Benjamin C. Travaglione and Donny Cheung},
    journal={arXiv preprint arXiv:cs/0603089},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0603089},
    primaryClass={cs.DS math.OC}
}