Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path Following

We present improved running time and iteration complexities of interior point methods for linear programs parametrized by the straight line complexity, i.e., the minimum number of segments of any piecewise linear curve traversing a particular neighborhood of the central path. While the standard measure of progress is the reduction in duality gap, the straight line complexity provides a stronger instance-wise bound, reflecting the combinatorial structure of the problem.

Our first main result focuses on interior point methods that stay in the ℓ 2 -neighborhood. We give a much stronger analysis of the trust region interior point method introduced by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009), proving that it is approximately instance optimal in this neighborhood. Namely, we show that the iteration complexity of this algorithm is a constant factor of the straight line complexity of the ℓ 2 -neighborhood. Further, each iteration can be implemented in current matrix multiplication time.

Our second main result is a wide-neighborhood interior point method whose running time is the wide-neighborhood straight line complexity times current matrix multiplication time, improving in essence a factor 𝑛 over the algorithm by Allamigeon, Dadush, Loho, Natura, and Végh (SIAM J. Comput. 2025). The algorithm can be seen as a boosted version of the robust interior point methods of Cohen, Lee and Song (JACM 2021) and van den Brand (SODA 2020) that can reduce the gap by a polynomial factor in current matrix multiplication time: our algorithm is also able to traverse any sufficiently straight segment of the central path in current matrix multiplication time, independently of the length of the segment.

A main ingredient in both methods is to solve trust region problems with ℓ 2 and ℓ ∞ -constraints, respectively. We develop fast and strongly polynomial algorithms for solving them to high accuracy. In the ℓ 2 -setting, this answers an open question by Lan, Monteiro and Tsuchiya.