Abstract
A vertex exchange method is proposed for solving the strongly convex quadratic program subject to the generalized simplex constraint. We conduct rigorous convergence analysis for the proposed algorithm and demonstrate its essential roles in solving some important classes of constrained convex optimization. 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 extensive numerical experiments. Our theoretical and numerical results further motivate the potential applications of the considered model and the proposed algorithms.
Introduction
Many critical problems in data science and engineering—such as D-optimal experimental design, portfolio optimization, and support vector machines—involve minimizing a "self-concordant" function. These functions, including logarithms or $-\log \det$, possess a mathematical structure well-suited for second-order Newton-type methods. However, these problems often involve generalized simplex constraints ($e^T x = b, \ell \le x \le u$), which present scalability challenges.
Standard Interior Point Methods (IPMs) struggle with high-dimensional data due to the cost of solving massive linear systems at every step. Conversely, first-order methods like Frank-Wolfe are more scalable but suffer from slow "zigzagging" convergence. This research introduces NewVEM, a two-level algorithm that achieves "fast $\times$ fast" linear convergence, significantly outperforming state-of-the-art solvers in both speed and scalability.
Methodology
The NewVEM framework utilizes a nested optimization strategy:
- Outer Loop (Inexact Projected Newton): The algorithm employs a second-order approximation of the objective. By using an "inexact" approach, the resulting quadratic subproblem does not require a perfect solution, saving significant computational time.
- Inner Loop (Vertex Exchange Method): To solve the quadratic subproblems, the authors implement a Vertex Exchange strategy. This greedy coordinate-descent-style approach moves "mass" between two variables (one increasing, one decreasing) to maintain the simplex constraint while improving the objective. This avoids expensive matrix inversions.
- Initialization (Semismooth Newton): A specialized semismooth Newton (SSN) method was developed specifically for projecting points onto the generalized simplex to provide a feasible starting point.
Key Insights
- Greedy Efficiency: The Vertex Exchange Method (VEM) acts as a greedy version of block-coordinate descent, optimizing the selection of variables to exchange.
- Projection Performance: The SSN method for projection reaches machine precision in just a few iterations, proving orders of magnitude faster than commercial solvers.
- Sparsity Induction: NewVEM tends to return sparser solutions, which reduces the cost of computing gradients and Hessians in subsequent iterations.
- Line-Search Free: The outer loop can often take "full steps" without a line search once it enters the local convergence region, reducing function evaluations.
Experimental Results
The researchers evaluated the algorithms using randomly generated Quadratic Programs (QPs) and D-optimal experimental design tasks.
Performance Benchmarks
- Projection Speed: For a vector of size $10^7$, the proposed SSN method computed the projection in 0.32 seconds, compared to 50.88 seconds for GUROBI—a roughly 150x speedup.
- Optimization Throughput: In D-optimal design tasks, NewVEM was consistently 2-3 times faster than the previous state-of-the-art "FWPN" (Frank-Wolfe Projected Newton) method.
- Robustness: The method maintained high accuracy (relative error $\approx 10^{-10}$ to $10^{-12}$) across varying problem sizes and active constraint counts.
Discussion and Future Work
While NewVEM demonstrates superior practical performance, the theoretical proof for the inner loop's linear convergence currently relies on a "non-degeneracy" condition. Future research will focus on relaxing this assumption. Additionally, as problem scales continue to grow, the evaluation of the Hessian matrix itself may become a bottleneck, suggesting a need for more efficient implementation strategies. Finally, extending this "fast $\times$ fast" framework to more complex polyhedral constraints remains a promising avenue for future study.
Summary updated