Inhalt des Dokuments
Prof. Dr. Peter Bürgisser
[1]- © Peter Bürgisser
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
Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Publikationen
| 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 $Csubseteqmathbb 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. |
Zurück [7]
isser/persons/peter_buergisser.jpg
g/fachgebiet_algorithmische_algebra/v_menue/members/bea
te_niessen/
nfrage/id/138731/?no_cache=1&ask_mail=YvoQ8wAGr%2BO
w8YiRpeEVf0HC%2FDUKtrsWlyZwON1oSIs%3D&ask_name=PBUE
RG
nate-free.condition.number.for.convex.programming.pdf
g/fachgebiet_algorithmische_algebra/v_menue/members/pro
f_dr_peter_buergisser/?no_cache=1&tx_sibibtex_pi1%5
Bdownload_bibtex_uid%5D=1351079&tx_sibibtex_pi1%5Bc
ontentelement%5D=tt_content%3A721853
g/fachgebiet_algorithmische_algebra/v_menue/members/pro
f_dr_peter_buergisser/
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
Copyright TU Berlin 2008