A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910035505840128 |
|---|---|
| author | Zhang, Rui-Jin Diao, Ruoyu Liu, Xin-Wei Dai, Yu-Hong |
| author_facet | Zhang, Rui-Jin Diao, Ruoyu Liu, Xin-Wei Dai, Yu-Hong |
| contents | Symmetric cone programming covers a broad class of convex optimization problems, including linear programming, second-order cone programming, and semidefinite programming. Although the augmented Lagrangian method (ALM) is well-suited for large-scale problems, its subproblems are often not twice continuously differentiable, preventing the direct use of classical Newton methods. To address this issue, we observe that barrier functions used in interior-point methods (IPMs) naturally serve as effective smoothing terms to alleviate such nonsmoothness. By combining the strengths of ALM and IPMs, we construct a novel augmented Lagrangian function and subsequently develop a Newton augmented Lagrangian (NAL) method. By leveraging the self-concordance property of the barrier function, the proposed method is shown to achieve an $\mathcal{O}(1/ε)$ complexity bound. In addition, a spectral analysis reveals that the condition numbers of the Schur complement matrices arising in the NAL method are of order $\mathcal{O}(1/μ)$, which is better than the $\mathcal{O}(1/{μ^2})$ order of classical IPMs. This improvement is further illustrated by a heatmap of condition numbers. Numerical experiments conducted on standard benchmarks indicate that the NAL method exhibits significant performance improvements compared to several existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04802 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis Zhang, Rui-Jin Diao, Ruoyu Liu, Xin-Wei Dai, Yu-Hong Optimization and Control 49M15, 90C05, 90C22, 90C25 Symmetric cone programming covers a broad class of convex optimization problems, including linear programming, second-order cone programming, and semidefinite programming. Although the augmented Lagrangian method (ALM) is well-suited for large-scale problems, its subproblems are often not twice continuously differentiable, preventing the direct use of classical Newton methods. To address this issue, we observe that barrier functions used in interior-point methods (IPMs) naturally serve as effective smoothing terms to alleviate such nonsmoothness. By combining the strengths of ALM and IPMs, we construct a novel augmented Lagrangian function and subsequently develop a Newton augmented Lagrangian (NAL) method. By leveraging the self-concordance property of the barrier function, the proposed method is shown to achieve an $\mathcal{O}(1/ε)$ complexity bound. In addition, a spectral analysis reveals that the condition numbers of the Schur complement matrices arising in the NAL method are of order $\mathcal{O}(1/μ)$, which is better than the $\mathcal{O}(1/{μ^2})$ order of classical IPMs. This improvement is further illustrated by a heatmap of condition numbers. Numerical experiments conducted on standard benchmarks indicate that the NAL method exhibits significant performance improvements compared to several existing methods. |
| title | A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis |
| topic | Optimization and Control 49M15, 90C05, 90C22, 90C25 |
| url | https://arxiv.org/abs/2506.04802 |