Complexity of Convex Optimization using Geometry-based Measures and a Reference Point

Robert M. Freund (rfreundmit.edu)

Abstract: Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given {\em reference point} x^r that might be close to the feasible region and/or the almost-optimal level set. This contrasts with other complexity bounds for convex optimization that rely on data-based condition numbers or algebraic measures, and that do not take into account any a priori reference point information.

Keywords: convex optimization, complexity, interior-point method, barrier method

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: MIT Operations Research Center Working paper, MIT, September, 2001

Download: [Postscript]

Entry Submitted: 10/01/2001
Entry Accepted: 10/01/2001
Entry Last Modified: 10/01/2001

Modify/Update this entry