A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910824285601792 |
|---|---|
| author | Liao, Feng-Yi Zheng, Yang |
| author_facet | Liao, Feng-Yi Zheng, Yang |
| contents | We propose a new bundle-based augmented Lagrangian framework for solving constrained convex problems. Unlike the classical (inexact) augmented Lagrangian method (ALM) that has a nested double-loop structure, our framework features a $\textit{single-loop}$ process. Motivated by the proximal bundle method (PBM), we use a $\textit{bundle}$ of past iterates to approximate the subproblem in ALM to get a computationally efficient update at each iteration. We establish sub-linear convergences for primal feasibility, primal cost values, and dual iterates under mild assumptions. With further regularity conditions, such as quadratic growth, our algorithm enjoys $\textit{linear}$ convergences. Importantly, this linear convergence can happen for a class of conic optimization problems, including semidefinite programs. Our proof techniques leverage deep connections with inexact ALM and primal-dual principles with PBM. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08835 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles Liao, Feng-Yi Zheng, Yang Optimization and Control Systems and Control We propose a new bundle-based augmented Lagrangian framework for solving constrained convex problems. Unlike the classical (inexact) augmented Lagrangian method (ALM) that has a nested double-loop structure, our framework features a $\textit{single-loop}$ process. Motivated by the proximal bundle method (PBM), we use a $\textit{bundle}$ of past iterates to approximate the subproblem in ALM to get a computationally efficient update at each iteration. We establish sub-linear convergences for primal feasibility, primal cost values, and dual iterates under mild assumptions. With further regularity conditions, such as quadratic growth, our algorithm enjoys $\textit{linear}$ convergences. Importantly, this linear convergence can happen for a class of conic optimization problems, including semidefinite programs. Our proof techniques leverage deep connections with inexact ALM and primal-dual principles with PBM. |
| title | A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2502.08835 |