In this paper, we propose a Hessian-free inexact regularized Newton method for composite optimization problems (COPs) that utilizes a first-order approximation of the Hessian matrix. At each iteration, the method solves an auxiliary subproblem inexactly, guided by an inexact condition. Additionally, the method incorporates an adaptive criterion, enabling dynamic adjustment of problem-specific parameters. We show that, for general convex COPs, the global complexity bound of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}(n\varepsilon ^{-1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mi>ε</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> function and gradient evaluations is established for our proposed Hessian-free method to achieve an <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-stationary solution, where n is the dimension of the problem. When the smooth component f of the composite objective function is strongly convex, the method exhibits the local superlinear convergence. Furthermore, when the smooth part f is uniformly convex of degree three, the method enjoys global linear convergence with complexity <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}\left( n\ln (1/\varepsilon )\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mfenced close=")" open="("> <mi>n</mi> <mo>ln</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Finally, we report preliminary numerical experiments demonstrating the effectiveness of the proposed method.

A Hessian-free Inexact Regularized Newton Method for Composite Convex Optimization

期刊论文
发表日期：

2026年5月13日

查看全文

Jueyou Li,
Taojie Meng

摘要

In this paper, we propose a Hessian-free inexact regularized Newton method for composite optimization problems (COPs) that utilizes a first-order approximation of the Hessian matrix. At each iteration, the method solves an auxiliary subproblem inexactly, guided by an inexact condition. Additionally, the method incorporates an adaptive criterion, enabling dynamic adjustment of problem-specific parameters. We show that, for general convex COPs, the global complexity bound of $\mathcal {O}(n\varepsilon ^{-1/2})$ $O (n ε^{- 1 / 2})$ function and gradient evaluations is established for our proposed Hessian-free method to achieve an $\varepsilon $ $ε$ -stationary solution, where n is the dimension of the problem. When the smooth component f of the composite objective function is strongly convex, the method exhibits the local superlinear convergence. Furthermore, when the smooth part f is uniformly convex of degree three, the method enjoys global linear convergence with complexity $\mathcal {O}\left( n\ln (1/\varepsilon )\right) $ $O (n ln (1 / ε))$ . Finally, we report preliminary numerical experiments demonstrating the effectiveness of the proposed method.