direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Leitung

Prof. Dr. Peter Bürgisser

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

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

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe