- 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/2001Entry Accepted: 10/01/2001Entry Last Modified: 10/01/2001Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.