The structured distance to ill-posedness for conic systems

Adrian Lewis (aslewissfu.ca)

Abstract: An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a linear map.

Keywords: condition number, conic system, distance to infeasibility, structured singular value, sublinear map, surjectivity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

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

Citation: Technical report, Simon Fraser University, submitted to Mathematics of Operations Research

Download: [Postscript][PDF]

Entry Submitted: 09/05/2003
Entry Accepted: 09/05/2003
Entry Last Modified: 09/05/2003

Modify/Update this entry