direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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
Zitatschlüssel AB-A-Coordinate-Free-Condition-Number-For-Convex-Programming
Autor Dennis Amelunxen and Peter Bürgisser
Seiten 1029-1041
Jahr 2012
Journal SIAM Journal on Optimization
Jahrgang 22
Nummer 3
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe