direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Dr. Dennis Amelunxen


City University of Hong Kong
Department of Mathematics
G6613 (Green Zone), 6/F Academic 1
Tat Chee Avenue, Kowloon Tong, Hong Kong
Persönliche Homepage

Publikationen in der Arbeitsgruppe

A coordinate-free condition number for convex programming
Citation key AB-A-Coordinate-Free-Condition-Number-For-Convex-Programming
Author Dennis Amelunxen and Peter Bürgisser
Pages 1029-1041
Year 2012
Journal SIAM Journal on Optimization
Volume 22
Number 3
Abstract We introduce and analyze a natural geometric version of Renegar's condition number $R$ for the homogeneous convex feasibility problem associated with a regular cone $C\subseteq\mathbb R^n$. Let $\mathrm\\\Gr\\\_n,m$ denote the Grassmann manifold of $m$-dimensional linear subspaces of $\mathbb R^n$ and consider the projection distance $d_p(W_1,W_2) := \|\pi_W_1 - \pi_W_2\|$ (spectral norm) between $W_1$ and $W_2$ in $\mathrmGr_n,m$, where $\pi_W_i$ denotes the orthogonal projection onto $W_i$. We call $C_G(W) := \max \ d_p(W,W')^-1 \mid W' \in Sigma_m \$ the Grassmann condition number of $W$ in $\mathrmGr_n,m$, where the set of ill-posed instances $\Sigma_m$ subset $\mathrmGr_n,m$ is defined as the set of linear subspaces touching $C$. We show that if $W = \mathrmim(A^T)$ for a matrix $A$ in $\mathbb R^m× n$, then $C_G(W) łe R(A) łe C_G(W) \kappa(A)$, 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). Furthermore, we show that $C_G(W)$ can as well be characterized in terms of the Riemannian distance metric on $\mathrmGr_n,m$. This differential geometric characterization of $C_G(W)$ is the starting point of the sequel [arXiv:1112.2603] to this paper, where the first probabilistic analysis of Renegar's condition number for an arbitrary regular cone $C$ is achieved.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.