A characterization of the distance to infeasibility under block-structured perturbations

Javier Pena (jfpandrew.cmu.edu)

Abstract: We discuss several generalizations of the classical Eckart and Young identity. We show that a natural extension of this identity holds for rectangular matrices defining conic systems of constraints, and for perturbations restricted to a particular block structure, such as those determined by a sparsity pattern. Our results extend and unify the classical Eckart and Young identity, Renegar's characterization of the distance to infeasibility [Math. Programming 70 (1995), 279--351], Rohn's characterization of the componentwise distance to singularity [Linear Algebra Appl. 126 (1989), 39--78], and Cheung and Cucker's characterization of the normalized distance to ill-posedness [Math. Programming 91 (2001), 163--174].

Keywords: condition numbers, sparse matrices, conic systems, distance to infeasibility, singular values

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Linear Algebra and its Applications 370 (2003) 193--216.

Download:

Entry Submitted: 04/08/2002
Entry Accepted: 04/08/2002
Entry Last Modified: 08/11/2003

Modify/Update this entry