An Interior Point Framework Employing Higher-Order Derivatives of Central Path-like Trajectories: Application to Convex Quadratic Programming

This paper revisits the idea of employing higher-order derivatives of interior point trajectories within an algorithmic framework. The paper carefully outlines the trajectories of relevance and introduces the importance of their expansion's radius of convergence. This is supplemented with significant computational results, which highlight the computational potential of using higher-order algorithms for certain classes of problems. A theoretical complexity analysis also proves that a second-order trajectory-following algorithm for linear programming retains the O(root nlog 1/epsilon) iteration dependency of current primal-dual methods. (C) 2022 Elsevier Ltd. All rights reserved.

Automated summary

This paper revisits the idea of employing higher-order derivatives of interior point trajectories within an algorithmic framework, emphasizing the importance of their expansion's radius of convergence. The significant computational results highlight the potential of using higher-order algorithms for certain problems, and the theoretical complexity analysis shows that a second-order trajectory-following algorithm for linear programming retains the iteration dependency of current primal-dual methods.