NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems
This work addresses optimization problems with generalized simplex constraints, which is incremental as it builds on existing methods for self-concordant functions.
The authors tackled constrained self-concordant minimization problems by proposing NewVEM, a Newton vertex exchange method with a two-level structure that achieves local linear convergence rates, demonstrating high efficiency and scalability in numerical experiments.
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.