A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
SIAM Journal on Optimization · 30.09.2023 · 33 (3) · 1361-1390
DOI: 10.1137/22m1474539 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 12.07.2023. Verfasst von Yifei Wang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
We develop a decomposition method based on the augmented Lagrangian framework to solve a broad family of semidefinite programming problems, possibly with nonlinear objective functions, nonsmooth regularization, and general linear equality/inequality constraints. In particular, the positive semidefinite variable along with a group of linear constraints can be transformed into a variable on a smooth manifold via matrix factorization. The nonsmooth regularization and other general linear constraints are handled by the augmented Lagrangian method. Therefore, each subproblem can be solved by a semismooth Newton method on a manifold. Theoretically, we show that the first and second-order necessary optimality conditions for the factorized subproblem are also sufficient for the original subproblem under certain conditions. Convergence analysis is established for the Riemannian subproblem and the augmented Lagrangian method. Extensive numerical experiments on large-scale semidefinite programming problems such as max-cut, nearest correlation estimation, clustering, and sparse principal component analysis demonstrate the strength of our proposed method compared to other state-of-the-art methods.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Wang, Y., Deng, K., Liu, H., & Wen, Z. (2023). A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming. SIAM Journal on Optimization, 33(3), 1361-1390. https://doi.org/10.1137/22m1474539
Vancouver
Wang Y, Deng K, Liu H, Wen Z. A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming. SIAM Journal on Optimization. 2023;33(3):1361-1390. doi:10.1137/22m1474539
BibTeX
@article{Wang2023,
author = {Wang, Yifei and Deng, Kangkang and Liu, Haoyang and Wen, Zaiwen},
title = {A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming},
journal = {SIAM Journal on Optimization},
year = {2023},
volume = {33},
number = {3},
pages = {1361--1390},
doi = {10.1137/22m1474539}
}
EUVIMED