A coordinate-free condition number for convex programming

Details A coordinate-free condition number for convex programming A coordinate-free condition number for convex programming

2011-05-20

arxiv.org/abs/1105.4049v1

Mathematics

Optimization and Control

13 pages

Scientific paper

We introduce and analyze a natural geometric version of Renegar's condition number R, which we call Grassmann condition number, for the homogeneous convex feasibility problem associated with a regular cone C\subseteq R^n. Let Gr_{n,m} denote the Grassmann manifold of m-dimensional linear subspaces of R^n with the Riemannian distance metric d_g. The set of ill-posed instances \Sigma_m\subset Gr_{n,m} consists of the linear subspaces W touching C. We define the Grassmann condition number \CG(W) of an m-dimensional subspace W\in\Gr_{n,m} as \CG(W)^{-1} := sin d_g(W,\Sigma_m). We also provide other characterizations of \CG(W) and prove that \CG(W) <= R(A) <= \CG(W) \kappa(A), where W =\im A^T, and where \kappa(A) =||A|| ||A^\dagger|| denotes the matrix condition number. This extends work by Belloni and Freund in Math. Program. 119:95-107 (2009). Based on the Grassmann condition number, in a forthcoming paper, we shall provide, for the first time, a probabilistic analysis of Renegar's condition number for an arbitrary regular cone C.

Affiliated with

Also associated with

No associations

Rating

A coordinate-free condition number for convex programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A coordinate-free condition number for convex programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A coordinate-free condition number for convex programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649174