Complexity of convex optimization using geometry-based measures and a reference point
By: Robert M. Freund.
Contributors: Sloan School of Management.
Series: Sloan working paper -- 4179-01; Working paper (Sloan School of Management) -- 4179.
Publisher: Alfred P. Sloan School of Management, Massachusetts Institute of Technology
Published: 2001
Place of publication: [Cambridge, Mass
Language: eng
Number of pages: 29
Description: 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. 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 reference point xr 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.