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.
Entry Submitted: 04/08/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|