On some perturbation properties of nonsmooth optimization on Riemannian manifolds with applications
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914065020878848 |
|---|---|
| author | Zhou, Yuexin Ding, Chao Zhang, Yangjing |
| author_facet | Zhou, Yuexin Ding, Chao Zhang, Yangjing |
| contents | This paper presents a perturbation analysis framework for nonsmooth optimization on connected Riemannian manifolds to bridge the gap between the rapid development of algorithmic approaches and a robust theoretical foundation. Using tangent-space local models, we transport core notions from Euclidean variational analysis, such as strong regularity, the Aubin property, and isolated calmness of the Karush-Kuhn-Tucker (KKT) solution mapping, to the manifold setting. Furthermore, we introduce the manifold (strong) variational sufficiency and show that its strong version is intrinsic, i.e., independent of the chosen retraction, and for polyhedral, second-order cone, and semidefinite programs, it coincides with the manifold strong second-order sufficient condition. These insights yield concrete algorithmic consequences. We show that the Riemannian Sequential Quadratic Programming achieves local superlinear and, under mild additional assumptions, quadratic convergence without strict complementarity, while the Riemannian Augmented Lagrangian Method attains R-linear convergence even when Lagrange multipliers are nonunique. Moreover, the proposed condition guarantees positive definiteness of the generalized Hessians associated with the augmented Lagrangian, enabling superlinear semismooth Newton steps in inner solves. Numerical experiments on robust matrix completion and compressed modes validate the theoretical predictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_06793 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On some perturbation properties of nonsmooth optimization on Riemannian manifolds with applications Zhou, Yuexin Ding, Chao Zhang, Yangjing Optimization and Control This paper presents a perturbation analysis framework for nonsmooth optimization on connected Riemannian manifolds to bridge the gap between the rapid development of algorithmic approaches and a robust theoretical foundation. Using tangent-space local models, we transport core notions from Euclidean variational analysis, such as strong regularity, the Aubin property, and isolated calmness of the Karush-Kuhn-Tucker (KKT) solution mapping, to the manifold setting. Furthermore, we introduce the manifold (strong) variational sufficiency and show that its strong version is intrinsic, i.e., independent of the chosen retraction, and for polyhedral, second-order cone, and semidefinite programs, it coincides with the manifold strong second-order sufficient condition. These insights yield concrete algorithmic consequences. We show that the Riemannian Sequential Quadratic Programming achieves local superlinear and, under mild additional assumptions, quadratic convergence without strict complementarity, while the Riemannian Augmented Lagrangian Method attains R-linear convergence even when Lagrange multipliers are nonunique. Moreover, the proposed condition guarantees positive definiteness of the generalized Hessians associated with the augmented Lagrangian, enabling superlinear semismooth Newton steps in inner solves. Numerical experiments on robust matrix completion and compressed modes validate the theoretical predictions. |
| title | On some perturbation properties of nonsmooth optimization on Riemannian manifolds with applications |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2308.06793 |