Optimization Online


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

Robert Freund (rfreund***at***mit.edu)
Jorge Vera (jvera***at***ing.puc.cl)

Abstract: 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.

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 383-09, January 2009, MIT, 77 Massachusetts Ave., Cambridge, MA 02142

Download: [PDF]

Entry Submitted: 02/07/2009
Entry Accepted: 02/07/2009
Entry Last Modified: 03/03/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society