<p>The primal-dual hybrid gradient method (PDHG), also known as the Chambolle–Pock method (CPM), is a widely used first-order algorithm for solving saddle-point problems and composite convex optimization models. It is known that CPM reduces to the Douglas–Rachford splitting method (DRSM) when the extrapolation parameter <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11075_2025_2207_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta = 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and to the Arrow–Hurwicz method when <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11075_2025_2207_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta = 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. However, for the general case <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11075_2025_2207_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \in (0,1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, the convergence behavior of CPM remains incompletely understood and typically requires additional restrictive assumptions. Moreover, the standard CPM applies extrapolation only to one of the primal or dual variables, which may limit its theoretical flexibility and practical performance. In this work, we propose a simple yet effective modification of CPM that introduces extrapolation in both the primal and dual updates. The resulting algorithm achieves global convergence with <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11075_2025_2207_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \in (0,1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> under relaxed conditions on the step sizes. We further establish a nonergodic <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11075_2025_2207_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {O}(1/\sqrt{N})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msqrt> <mi>N</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> convergence rate and demonstrate that the proposed algorithm corresponds to a strictly contractive variant of the Peaceman–Rachford splitting method (PRSM) applied to the underlying monotone inclusion. This connection enables the transfer of known results from the PRSM framework to our setting. Additionally, when applied to convex problems with linear constraints, it is equivalent to a relaxed linearized augmented Lagrangian method. Numerical experiments on imaging and sparse regression problems illustrate the practical advantages of the proposed method.</p>

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

A primal-dual algorithm with coupled extrapolation: bridging the Chambolle–Pock and Peaceman–Rachford methods

  • Jiazhuo Wu,
  • Feng Ma

摘要

The primal-dual hybrid gradient method (PDHG), also known as the Chambolle–Pock method (CPM), is a widely used first-order algorithm for solving saddle-point problems and composite convex optimization models. It is known that CPM reduces to the Douglas–Rachford splitting method (DRSM) when the extrapolation parameter \(\theta = 1\) θ = 1 , and to the Arrow–Hurwicz method when \(\theta = 0\) θ = 0 . However, for the general case \(\theta \in (0,1)\) θ ( 0 , 1 ) , the convergence behavior of CPM remains incompletely understood and typically requires additional restrictive assumptions. Moreover, the standard CPM applies extrapolation only to one of the primal or dual variables, which may limit its theoretical flexibility and practical performance. In this work, we propose a simple yet effective modification of CPM that introduces extrapolation in both the primal and dual updates. The resulting algorithm achieves global convergence with \(\theta \in (0,1)\) θ ( 0 , 1 ) under relaxed conditions on the step sizes. We further establish a nonergodic \(\mathcal {O}(1/\sqrt{N})\) O ( 1 / N ) convergence rate and demonstrate that the proposed algorithm corresponds to a strictly contractive variant of the Peaceman–Rachford splitting method (PRSM) applied to the underlying monotone inclusion. This connection enables the transfer of known results from the PRSM framework to our setting. Additionally, when applied to convex problems with linear constraints, it is equivalent to a relaxed linearized augmented Lagrangian method. Numerical experiments on imaging and sparse regression problems illustrate the practical advantages of the proposed method.