A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929278730371072 |
|---|---|
| author | Monteiro, Renato D. C. Sujanani, Arnesh Cifuentes, Diego |
| author_facet | Monteiro, Renato D. C. Sujanani, Arnesh Cifuentes, Diego |
| contents | This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method with inner acceleration; 2) Frank-Wolfe steps to escape from spurious local stationary points. In contrast to the low-rank method of Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances arising from maximum stable set, phase retrieval, and matrix completion show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve a maximum stable set SDP instance with dimension pair $(n,m)\approx (10^6,10^7)$ within $10^{-5}$ relative precision. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12490 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach Monteiro, Renato D. C. Sujanani, Arnesh Cifuentes, Diego Optimization and Control Numerical Analysis 90C30, 65K10, 90C26, 90C60, 90C25 This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method with inner acceleration; 2) Frank-Wolfe steps to escape from spurious local stationary points. In contrast to the low-rank method of Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances arising from maximum stable set, phase retrieval, and matrix completion show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve a maximum stable set SDP instance with dimension pair $(n,m)\approx (10^6,10^7)$ within $10^{-5}$ relative precision. |
| title | A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach |
| topic | Optimization and Control Numerical Analysis 90C30, 65K10, 90C26, 90C60, 90C25 |
| url | https://arxiv.org/abs/2401.12490 |