Chambolle–Pock algorithm: Difference between revisions

Revision as of 15:43, 18 September 2023

Revision as of 15:45, 18 September 2023

Line 66:

'''end do'''

{{algorithm-end}}

Chambolle and Pock proved<ref name=":0" /> that the algorithm converges if <math>\theta = 1</math> and <math>\tau \sigma \lVert K \rVert^2 \leq 1</math>, sequentially and with <math>\mathcal{O}(1/N)</math> as rate of convergence for the primal-dual gap. This has been improved by S. Banert et al,<ref>{{Cite web |last1=Banert |first1=Sebastian|last2=Upadhyaya |first2=Manu|last3=Giselsson |first3=Pontus |date=2023 |title=The Chambolle-Pock method converges weakly with <math>\theta > 1/2<math> and <math>\tau \sigma \|L\|^2 < 4/(1+2\ theta)<math> |url=https://arxiv.org/pdf/2309.03998.pdf}}</ref> to hold whenever <math>\theta>1/2<math> and <math>\tau \sigma \|L\|^2<4/(1+2\theta)<math>.

The semi-implicit Arrow-Hurwicz method<ref>{{cite book |first=H. |last=Uzawa |chapter=Iterative methods for concave programming |editor1-first=K. J. |editor1-last=Arrow |editor2-first=L. |editor2-last=Hurwicz |editor3-first=H. |editor3-last=Uzawa |title=Studies in linear and nonlinear programming |url=https://archive.org/details/studiesinlinearn0000arro |url-access=registration |publisher=Stanford University Press |year=1958 }}</ref> coincides with the particular choice of <math>\theta = 0</math> in the Chambolle-Pock algorithm.<ref name=":0" />