NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908593044848640 |
|---|---|
| author | Liang, Ling Toh, Kim-Chuan Yang, Haizhao |
| author_facet | Liang, Ling Toh, Kim-Chuan Yang, Haizhao |
| contents | We propose \textbf{NewVEM}, a Newton vertex exchange method for efficiently solving self-concordant minimization problems under generalized simplex constraints. The algorithm features a two-level structure: the outer loop employs a projected Newton method, and the inner loop uses a vertex exchange approach to solve strongly convex quadratic subproblems. Both loops converge locally at linear rates under technical conditions, resulting in a ``fast $\times$ fast'' framework that demonstrates high efficiency and scalability in practice. To get a feasible initial point to execute the algorithm, we also present and analyze a highly efficient semismooth Newton method for computing the projection onto the generalized simplex. The excellent practical performance of the proposed algorithms is demonstrated by a set of numerical experiments. Our results further motivate the potential real-world applications of the considered model and the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03294 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems Liang, Ling Toh, Kim-Chuan Yang, Haizhao Optimization and Control Machine Learning 90C06, 90C22, 90C25 We propose \textbf{NewVEM}, a Newton vertex exchange method for efficiently solving self-concordant minimization problems under generalized simplex constraints. The algorithm features a two-level structure: the outer loop employs a projected Newton method, and the inner loop uses a vertex exchange approach to solve strongly convex quadratic subproblems. Both loops converge locally at linear rates under technical conditions, resulting in a ``fast $\times$ fast'' framework that demonstrates high efficiency and scalability in practice. To get a feasible initial point to execute the algorithm, we also present and analyze a highly efficient semismooth Newton method for computing the projection onto the generalized simplex. The excellent practical performance of the proposed algorithms is demonstrated by a set of numerical experiments. Our results further motivate the potential real-world applications of the considered model and the proposed algorithms. |
| title | NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems |
| topic | Optimization and Control Machine Learning 90C06, 90C22, 90C25 |
| url | https://arxiv.org/abs/2407.03294 |