Chambolle–Pock algorithm: Difference between revisions

Revision as of 14:07, 7 July 2023

Revision as of 14:27, 7 July 2023

Line 18:

==Problem statement==

Let be <math> \mathcal{X}, \mathcal{Y} </math> two real [[Vector space|vector spaces]] equipped with an [[Inner product space|inner product]] <math> \langle \cdot, \cdot \rangle </math> and a [[Norm (mathematics)|norm]] <math> \lVert \,\cdot \,\rVert = \langle \cdot, \cdot \rangle^{\frac{1}{2}} </math>. From up to now, a function <math>F</math> is called ''simple'' if its [[proximal operator]] <math> \text{prox}_{\tau F} </math> has a [[Closed-form expression|closed-form representation]] or can be accurately computed, for <math>\tau >0</math>.<ref name=":0" />

Consider the following constrained primal problem:<ref name=":0" />

Line 51:

==Algorithm==

The Chambolle-Pock algorithm primarily involves iteratively alternating between ascending in the dual variable <math> y </math> and descending in the primal variable <math> x </math> using a [[Gradient method|gradient]]-like approach, in order to simultaneously solve the primal and the dual problem.<ref name=":1" />. Furthermore, an over-[[Relaxation (iterative method)|relaxation]] technique is employed for the primal variable.<ref name=":0" />{{algorithm-begin|name=Chambolle-Pock algorithm}}

{{nowrap|Input: <math> F, G, \tau, \sigma >0, \, \theta \in[0,1],\, (x^0,y^0)\in\mathcal{X}\times\mathcal{Y}</math> and set <math> \overline{x}^0 = x^0</math>,}} ''stopping criterion''.

Line 61:

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

'''end do'''

{{algorithm-end}}To ensure the convergence of the algorithm, it is advisable to select the step size parameters such that <math>\tau \sigma \leq \lVert L \rVert</math>, where <math> L = \lVert K \rVert </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>

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

==Acceleration==

There are special cases in which the rate of convergence has a theoretical speed up.<ref name=":0" /> In fact, if <math>G </math>, respectively <math> F^* </math>, is [[Convex function#Uniformly convex functions|uniformly convex]] then <math> G^* </math>, respectively <math> F </math>, has a [[Lipschitz continuity|Lipschitz continuous]] gradient. Then, the rate of convergence can be improved to <math> \mathcal{O}(1/N^2)</math>, providing a slightly changes in the Chambolle-Pock algorithm. It leads to an accelerated version of the method and it consists in choosing iteratively <math> \tau_n, \sigma_n</math>, and also <math> \theta_n</math>, instead of fixing these values.<ref name=":0" />

In case of <math> G </math> uniformly convex, with <math> \gamma>0 </math> the uniform-convexity constant, the modified algorithm becomes<ref name=":0" />