An adaptive interior-point method with backtracking line search for convex constrained optimization
arXiv:2607.12318
The paper proposes and analyzes an adaptive interior‑point algorithm that uses a regularized Newton step with backtracking line search on a log‑barrier function to solve convex problems with smooth constraints, achieving an ε‑approximate solution in roughly O(ε⁻²⁄³) iterations.
Abstract
Interior-point methods (IPMs) are widely adopted due to their high practical efficiency in solving linear, convex, and nonconvex optimization problems. For convex optimization, this performance is theoretically well-supported: there are strong complexity guarantees for self-concordant barrier setups \cite{nesterov1994interior}, which cover linear and conic optimization. On the other hand, unconstrained convex optimization is well-studied. However, there is limited analysis of constrained convex optimization methods without the self-concordance assumption. We develop and analyze a regularized Newton method with line search applied to the log barrier function in the setting that the objective and constraints are thrice differentiable and have Lipschitz continuous first and second derivatives. Starting from a strictly feasible point, our method finds an -approximately optimal solution in iterations.