On an Extension of Condition Number Theory to Non-Conic Convex Optimization

Robert M. Freund (rfreundmit.edu)
Fernando Ordonez (fordonusc.edu)

Abstract: 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'x | Ax-b \in C_Y, x \in C_X }, to the more general non-conic format: (GP_d): z_* := min_x {c'x | Ax-b \in C_Y, x \in 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.

Keywords: condition number, convex optimization, conic optimization, duality, sensitivity analysis, perturbation theory

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: Working paper #2003-01, USC-Department of Indstrial and Systems Engineering, Feb/2003

Download: [PDF]

Entry Submitted: 02/14/2003
Entry Accepted: 02/14/2003
Entry Last Modified: 02/14/2003

Modify/Update this entry