Optimization Online


On the Grassmann condition number

Javier Pena (jfp***at***andrew.cmu.edu)
Vera Roshchina (vera.roshchina***at***gmail.com)

Abstract: We give new insight into the Grassmann condition of the conic feasibility problem \[ x \in L \cap K \setminus\{0\}. \] Here $K\subseteq V$ is a regular convex cone and $L\subseteq V$ is a linear subspace of the finite dimensional Euclidean vector space $V$. The Grassmann condition of this problem is the reciprocal of the distance from $L$ to the set of ill-posed instances in the Grassmann manifold where $L$ lives. We consider a very general distance in the Grassmann manifold defined by two possibly different norms in $V$. We establish the equivalence between the Grassmann distance to ill-posedness of the above problem and a natural measure of the least violated trial solution to its alternative feasibility problem. We also show a tight relationship between the Grassmann and Renegar's condition measures, and between the Grassman measure and a symmetry measure of the above feasibility problem. Our approach can be readily specialized to a canonical norm in $V$ induced by $K$, a prime example being the one-norm for the non-negative orthant. For this special case we show that the Grassmann distance ill-posedness of is equivalent to a measure of the most interior solution to the above conic feasibility problem.

Keywords: Grassmann manifold, distance to ill-posedness, condition

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming

Citation: Working Paper. Tepper School of Business. Carnegie Mellon University.

Download: [PDF]

Entry Submitted: 04/15/2016
Entry Accepted: 04/15/2016
Entry Last Modified: 04/26/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society