<p>The trust-region (TR) method is renowned historically for its robustness in nonconvex problems and extraordinary numerical performance, but the study of its performance in convex optimization has been limited. This paper complements the existing literature by presenting a universal trust-region method that simultaneously incorporates the quadratic regularization and ball constraint. In particular, we introduce a novel descent property tailored to trust-region-type algorithms, enabling us to unify and streamline the analysis for both convex and nonconvex optimization. Our method exhibits an iteration complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\tilde{O}(\epsilon ^{-3/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> to find an <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-approximate second-order stationary point for nonconvex optimization. Meanwhile, the analysis reveals that the universal method attains an <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(\epsilon ^{-1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <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> complexity bound for convex optimization. Finally, we use the adaptive universal method to address practical implementations. The numerical results show the effectiveness of our method in both nonconvex and convex problems.</p>

Beyond Nonconvexity: A Universal Trust-Region Method with New Analyses

期刊论文
发表日期：

2025年12月12日

查看全文

Yuntian Jiang,
Chang He,
Chuwen Zhang,
Dongdong Ge,
Bo Jiang,
Yinyu Ye

摘要

The trust-region (TR) method is renowned historically for its robustness in nonconvex problems and extraordinary numerical performance, but the study of its performance in convex optimization has been limited. This paper complements the existing literature by presenting a universal trust-region method that simultaneously incorporates the quadratic regularization and ball constraint. In particular, we introduce a novel descent property tailored to trust-region-type algorithms, enabling us to unify and streamline the analysis for both convex and nonconvex optimization. Our method exhibits an iteration complexity of $\tilde{O}(\epsilon ^{-3/2})$ $\tilde{O} (ϵ^{- 3 / 2})$ to find an $\epsilon $ $ϵ$ -approximate second-order stationary point for nonconvex optimization. Meanwhile, the analysis reveals that the universal method attains an $O(\epsilon ^{-1/2})$ $O (ϵ^{- 1 / 2})$ complexity bound for convex optimization. Finally, we use the adaptive universal method to address practical implementations. The numerical results show the effectiveness of our method in both nonconvex and convex problems.