Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
This work addresses the scalability bottleneck of interior-point trust-region methods for large-scale linearly constrained nonconvex optimization, offering a practical speedup while preserving convergence guarantees.
The authors propose an approximate first-order interior-point trust-region (IPTR) framework that reduces per-iteration cost by replacing exact trust-region subproblem solves with an approximate projector maintained via low-rank updates, achieving up to a 2.48× speedup over existing first-order IPTR algorithms in large-scale settings.
Computing approximate Karush--Kuhn--Tucker (KKT) points for constrained nonconvex programs is a fundamental problem in mathematical programming. Interior-point trust-region (IPTR) methods are particularly attractive for such problems because they maintain strictly feasible iterates throughout the iterative process and converge to a first-order and second-order KKT solution. Their scalability, however, is limited by the repeated computation of trust-region search directions. In this paper, we propose an approximate first-order IPTR framework that addresses this bottleneck by replacing exact trust-region subproblem solves with an approximate projector maintained through low-rank updates. The resulting method preserves feasibility and the global convergence guarantees of standard IPTR schemes while substantially reducing the per-iteration cost. We further extend the framework to obtain approximate second-order KKT points using only first-order information by integrating a gradient-based negative-curvature routine, thus avoiding explicit Hessian computations. We conduct numerical experiments to demonstrate the scalability of our approximate first-order IPTR framework in large-scale settings, where it achieves up to a $2.48\times$ speedup over the existing first-order IPTR algorithm.