Scholarlink

<p>In this paper, we propose new linearly convergent second-order methods for minimizing convex quartic polynomials. This framework is applied for designing optimization schemes, which can solve general convex problems satisfying a new condition of quartic regularity. It assumes positive definiteness and boundedness of the fourth derivative of the objective function. For such problems, an appropriate quartic regularization of Damped Newton Method has global linear rate of convergence. We discuss several important consequences of this result. In particular, it can be used for constructing new second-order methods in the framework of high-order proximal-point schemes (Nesterov, Math. Program. <b>197</b>, 1–26, <CitationRef CitationID="CR21">2023</CitationRef> and Nesterov, SIAM J. Optim. <b>31</b>, 2807–2828, <CitationRef CitationID="CR20">2021</CitationRef>). These methods have convergence rate <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10013_2024_720_Article_IEq1.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tilde{O}(k^{-p})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mrow> <mo>-</mo> <mi>p</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <i>k</i> is the iteration counter, <i>p</i> is equal to 3, 4, or 5, and tilde indicates the presence of logarithmic factors in the complexity bounds for the auxiliary problems, which are solved at each iteration of the schemes.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Quartic Regularity

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年3月12日

查看全文
  • Yurii Nesterov

摘要

In this paper, we propose new linearly convergent second-order methods for minimizing convex quartic polynomials. This framework is applied for designing optimization schemes, which can solve general convex problems satisfying a new condition of quartic regularity. It assumes positive definiteness and boundedness of the fourth derivative of the objective function. For such problems, an appropriate quartic regularization of Damped Newton Method has global linear rate of convergence. We discuss several important consequences of this result. In particular, it can be used for constructing new second-order methods in the framework of high-order proximal-point schemes (Nesterov, Math. Program. 197, 1–26, 2023 and Nesterov, SIAM J. Optim. 31, 2807–2828, 2021). These methods have convergence rate \(\tilde{O}(k^{-p})\) O ~ ( k - p ) , where k is the iteration counter, p is equal to 3, 4, or 5, and tilde indicates the presence of logarithmic factors in the complexity bounds for the auxiliary problems, which are solved at each iteration of the schemes.