Chambolle–Pock algorithm: Difference between revisions

Revision as of 12:39, 8 September 2023

Revision as of 12:46, 8 September 2023

Line 65:

{{nowrap|<math>k\leftarrow k+1</math>}}

'''end do'''

{{algorithm-end}}

{{algorithm-end}}To ensure the convergence of the algorithm, it is advisable to select the step size parameters such that <math>\tau \sigma \lVert K \rVert^2 \leq 1</math>. This straightforward selection guarantees the convergence of the algorithm.<ref name=":0" /> Moreover, with these hypotheses it is proved that for <math>\theta = 1</math> the proposed algorithm has <math> \mathcal{O}(1/N)</math> as rate of convergence for the primal-dual gap,<ref name=":0" /> that [[Yurii Nesterov|Nesterov]] showed it is optimal for the class of known structured convex optimization problems.<ref>{{Cite journal |last=Nesterov |first=Yu. |date=2005-05-01 |title=Smooth minimization of non-smooth functions |url=https://doi.org/10.1007/s10107-004-0552-5 |journal=Mathematical Programming |language=en |volume=103 |issue=1 |pages=127–152 |doi=10.1007/s10107-004-0552-5 |s2cid=2391217 |issn=1436-4646}}</ref>

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.

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" />