Accession Number:

ADA495929

Title:

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

Descriptive Note:

Working paper

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s):

Report Date:

2009-01-01

Pagination or Media Count:

22.0

Abstract:

Consider the following supposedly-simple problem compute x satisfying 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 i the computational complexity of computing a point x in S, ii the geometry of S, and iii the stability or conditioning of S under perturbation. Under suitable definitions of these terms, 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 in turn leads, under certain assumptions, to a form of equivalence among computational complexity, the geometry of S, and the conditioning of S. Our measures of the geometry of S, relative to a given reference point x, are the aspect ratio A Rr, as well as R and 1r, where Bx,R intersection of S contains a ball of radius r. The aspect ratio arises in the analyses of many algorithms for convex problems, and its importance in convex algorithm analysis has been well-known for several decades. However, the terms R and 1r in our complexity results are a bit counter-intuitive nevertheless, we show that the computational complexity must involve these terms in addition to the aspect ratio even when the aspect ratio itself is small. This lower-bound complexity analysis relies on simple features of the separation oracle model of conveying S if we instead assume that S is conveyed by a self-concordant barrier function, then it is an open challenge to prove such complexity lower-bound.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE