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 or conditioning of S under perturbation. We show herein that problem instances with favorable geometry have favorable computational complexity, validating conventional wisdom. We also show a converse of this implication, by showing that there exist problem instances in certain families characterized by unfavorable geometry, that require more computational effort to solve. This lower-bound complexity analysis relies on simple features of the separation oracle model of conveying S.
Citation
MIT Operations Research Center Working Paper OR 383-09, January 2009, MIT, 77 Massachusetts Ave., Cambridge, MA 02142