Browsing by Author "Freund, Robert M."

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
    (INFORMS, 2009) Freund, Robert M.; Vera, Jorge R.
    Consider the supposedly simple problem of computing a point in a convex set that is conveyed by a separation oracle with no further information (e. g., no domain ball containing or intersecting the set, etc.). The authors' interest in this problem stems from fundamental issues involving the interplay of (i) the computational complexity of computing a point in the set, (ii) the geometry of the set, and (iii) the stability or conditioning of the set under perturbation. Under suitable definitions of these terms, the authors show herein that problem instances with favorable geometry have favorable computational complexity, validating conventional wisdom. The authors also show a converse of this implication by showing that there exist problem instances that require more computational effort to solve in certain families characterized by unfavorable geometry. This in turn leads, under certain assumptions, to a form of equivalence among computational complexity, geometry, and the conditioning of the set. The authors' measures of the geometry, relative to a given reference point, are based on the radius of a certain domain ball whose intersection with the set contains a certain inscribed ball.