Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908995456860160 |
|---|---|
| author | Su, Yuexin Zhang, Chenyi Huang, Peiyuan Li, Tongyang Ye, Yinyu |
| author_facet | Su, Yuexin Zhang, Chenyi Huang, Peiyuan Li, Tongyang Ye, Yinyu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24488 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization Su, Yuexin Zhang, Chenyi Huang, Peiyuan Li, Tongyang Ye, Yinyu Data Structures and Algorithms Optimization and Control 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. |
| title | Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2604.24488 |