  


Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
Robert Freund (rfreundmit.edu) Abstract: Consider the following supposedlysimple 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 lowerbound complexity analysis relies on simple features of the separation oracle model of conveying S. Keywords: convex set, separation oracle, computational complexity, aspect ratio, ellipsoid algorithm Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: MIT Operations Research Center Working Paper OR 38309, January 2009, MIT, 77 Massachusetts Ave., Cambridge, MA 02142 Download: [PDF] Entry Submitted: 02/07/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  