# NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems

arXiv: https://arxiv.org/abs/2407.03294 · HTML: https://mlsanity.com/paper/2407.03294/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 81 references that are in the map.
- First posted on arXiv 3 Jul 2024.

## Builds on (most cited first, 19 of 19)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier](https://mlsanity.com/paper/2010.08999/) (2020)
- [Composite Self-Concordant Minimization](https://mlsanity.com/paper/1308.2867/) (2013)
- [On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope](https://mlsanity.com/paper/1702.05934/) (2017)
- [A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization](https://mlsanity.com/paper/2002.07003/) (2020)
- [QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs](https://mlsanity.com/paper/2010.02653/) (2020)
- [QPPAL: A two-phase proximal augmented Lagrangian method for high dimensional convex quadratic programming problems](https://mlsanity.com/paper/2103.13108/) (2021)
- [A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions](https://mlsanity.com/paper/1409.2679/) (2014)
- [Efficient AutoML Pipeline Search with Matrix and Tensor Factorization](https://mlsanity.com/paper/2006.04216/) (2020)
- [An Inexact Augmented Lagrangian Method for Second-order Cone Programming with Applications](https://mlsanity.com/paper/2010.08772/) (2020)
- [Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods](https://mlsanity.com/paper/2312.11200/) (2023)
- [An Away-Step Frank-Wolfe Method for Minimizing Logarithmically-Homogeneous Barriers](https://mlsanity.com/paper/2305.17808/) (2023)
- [A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization](https://mlsanity.com/paper/1812.05243/) (2018)
- [A Gradient-Based Implementation of the Polyhedral Active Set Algorithm](https://mlsanity.com/paper/2202.05353/) (2022)

## Abstract (arXiv)

We propose 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 × 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.