This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Freund, R. M. Articles by Ordóñez, F. Search for Related Content

On an Extension of Condition Number Theory to Nonconic Convex Optimization

Sloan School of Management, Massachusetts Institute of Technology, 50 Memorial Drive, Cambridge, Massachusetts 02142
Industrial and Systems Engineering, University of Southern California, GER-247, Los Angeles, California 90089-0193
rfreund{at}mit.edu
fordon{at}usc.edu

The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization:

z_* min_x c^t x, s.t. Ax–b C_Y, x C_X,

to the more general nonconic format:

z_* min_x c^tx, (GP_d) s.t. Ax – b C_Y, x P,

where P is any closed convex set, not necessarily a cone, which we call the ground-set. Although any convex problem can be transformed to conic form, such transformations are neither unique nor natural given the natural description of many problems, thereby diminishing the relevance of data-based condition number theory. Herein we extend the modern theory of condition numbers to the problem format (GP_d). As a byproduct, we are able to state and prove natural extensions of many theorems from the conic-based theory of condition numbers to this broader problem format.

Key Words: condition number; convex optimization; conic optimization; duality; sensitivity analysis; perturbation theory
History: Received: February 16, 2003; revision received: May 11, 2004;