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

Ling Liang, Kim-Chuan Toh, Haizhao YangJ. Sci. Comput 2025 · DOI

TL;DR

This paper introduces NewVEM, a novel and efficient algorithm for solving a specific type of optimization problem involving self-concordant functions and generalized simplex constraints. NewVEM combines a projected Newton method with a vertex exchange method, achieving a "fast x fast" framework that demonstrates superior practical performance and scalability compared to existing state-of-the-art solvers.

What Problem Does This Paper Address?

The paper tackles a class of optimization problems known as constrained self-concordant minimization problems with generalized simplex constraints. These problems are mathematically represented as:

min f(x) s.t. e^T x = b, l <= x <= u

where f(x) is a self-concordant function, e is a vector of ones, b is a scalar, and l and u are lower and upper bound vectors, respectively. Self-concordant functions are crucial because they guarantee strong theoretical properties and enable robust algorithms, finding applications in areas like optimal experimental design, portfolio optimization, and logistic regression. The generalized simplex constraint is also important as it models various real-world problems.

Existing methods for these problems, such as interior-point methods, struggle with scalability for large datasets. While first-order methods offer better scalability, they often require many iterations or complex projection steps. The paper aims to bridge this gap by developing an algorithm that is both efficient and scalable, with strong theoretical convergence guarantees.

Methods

The core of the paper is the NewVEM algorithm, which employs a two-level structure:

  • Outer Loop: Projected Newton Method: This is an inexact projected Newton method adapted from existing work [41]. It iteratively refines an estimate of the solution by solving quadratic subproblems. A key feature is its ability to quickly enter a region where linear convergence is guaranteed.
  • Inner Loop: Vertex Exchange Method: This novel approach is used to efficiently solve the strongly convex quadratic subproblems that arise in the outer loop. It's inspired by vertex exchange methods used for simpler problems and is designed to be robust and globally convergent with a local linear convergence rate.

To initialize the algorithm, the paper also proposes and analyzes a fast semismooth Newton method for computing the projection onto the generalized simplex. This is crucial because the projected Newton method requires a feasible starting point.

Datasets

The paper does not use datasets for training. Instead, it focuses on generating synthetic test problems to evaluate the performance of its proposed algorithms. These synthetic problems are generated for:

  • Projection onto the generalized simplex: Problems of varying sizes (up to 10^7 dimensions) are created to test the efficiency and accuracy of the semismooth Newton projection method.
  • Quadratic programming (QP) with generalized simplex constraints: These problems are generated with varying matrix sizes, condition numbers, and constraint tightness to assess the performance of the Vertex Exchange Method (VEM) against other solvers.
  • D-optimal experimental design: Problems are generated using both randomly generated data and real-world datasets (specifically, three different design spaces: X1(n), X2(n), and X3(n)) to evaluate the overall NewVEM framework.

Key Insights and Ideas

  • "Fast x Fast" Framework: The combination of an efficient outer projected Newton loop and a fast inner vertex exchange loop leads to a highly efficient algorithm that converges quickly in both stages.
  • Vertex Exchange for QP Subproblems: Adapting the vertex exchange idea to solve the quadratic subproblems within the projected Newton framework proves to be a powerful strategy, offering global convergence and local linear rates.
  • Semismooth Newton for Projection: Developing an efficient semismooth Newton method for projecting onto the generalized simplex is critical for providing a feasible starting point, enabling the overall algorithm to function effectively.
  • Scalability: The proposed methods demonstrate excellent scalability, handling problems with millions of variables, which is a significant advantage over traditional interior-point methods.
  • Practical Performance: Numerical experiments consistently show that NewVEM outperforms state-of-the-art solvers in terms of both computational time and solution accuracy.

Key Results

  • Projection Performance: The semismooth Newton projection method is shown to be significantly faster and more accurate than commercial solvers like GUROBI and a specialized dual active set method (PPROJ) for projecting onto the generalized simplex. For instance, it achieves near-machine-epsilon accuracy in much less time.
  • QP Solver Performance: The Vertex Exchange Method (VEM) is compared against projected gradient methods (PG, FISTA), a polyhedral active set method (PASA), and the Frank-Wolfe (FW) algorithm for solving QPs with generalized simplex constraints. VEM consistently achieves high-quality solutions and is significantly faster than FW, which often hits time limits. It also shows competitive performance against PG, FISTA, and PASA, especially when optimal solutions have many active constraints.
  • D-optimal Design Performance: When applied to D-optimal experimental design problems, NewVEM (using VEM for QP subproblems) is found to be substantially more efficient than the FWPN method (which uses ASFW for QP subproblems). This efficiency stems from faster QP solving and potentially sparser solutions.

Limitations and Future Work

  • Nondegeneracy Condition: The linear convergence rate of the vertex exchange method depends on a nondegeneracy condition, which the authors acknowledge might be restrictive. Future work could explore relaxing this assumption.
  • Newton Method Convergence Rate: While the inexact projected Newton method achieves linear convergence, the authors note that this contrasts with the typical expectation of superlinear or quadratic convergence for Newton-type methods. Bridging this gap would require more advanced analytical tools.
  • SC¹ Functions: The paper briefly touches upon SC¹ functions and suggests that the framework could be extended to them. Further investigation into implementing and analyzing NewVEM for SC¹ functions is proposed.
  • Broader Applications: The authors suggest exploring the framework's practical performance across a wider range of applications, including exact optimal experimental design.
  • Gradient and Hessian Evaluation: For specific problems like D-optimal experimental design, evaluating the gradient and Hessian can be computationally expensive. Future research could focus on efficiently implementing Algorithm 1 to minimize these costs.

Summary updated

BibTeX
@article{liang2025newvem,
  author = {Ling Liang and Kim-Chuan Toh and Haizhao Yang},
  title = {{NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems}},
  journal = {J. Sci. Comput.},
  year = {2025},
  doi = {10.1007/s10915-025-03096-5},
}
Figure