An inexact regularized proximal Newton method without line search

Abstract In this paper, we introduce an inexact regularized proximal Newton method (IRPNM) that does not require any line search. The method is designed to minimize the sum of a twice continuously differentiable function f and a convex (possibly non-smooth and extended-valued) function $$\varphi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>φ</mml:mi> </mml:math> . Instead of controlling a step size by a line search procedure, we update the regularization parameter in a suitable way, based on the success of the previous iteration. The global convergence of the sequence of iterations and its superlinear convergence rate under a local Hölderian error bound assumption are shown. Notably, these convergence results are obtained without requiring a global Lipschitz property for $$ \nabla f $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>∇</mml:mi> <mml:mi>f</mml:mi> </mml:mrow> </mml:math> , which, to the best of the authors’ knowledge, is a novel contribution for proximal Newton methods. To highlight the efficiency of our approach, we provide numerical comparisons with an IRPNM using a line search globalization and a modern FISTA-type method.