Content deleted Content added
Tag: references removed |
Citation bot (talk | contribs) Add: authors 1-1. Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 406/1032 |
||
| (12 intermediate revisions by 6 users not shown) | |||
Line 1:
{{Short description|Primal-Dual algorithm optimization for convex problems}}
{{multiple image
}}
In [[mathematics]], the '''
The
The algorithm is based on a primal-dual formulation, which allows for simultaneous updates of primal and [[Duality (mathematics)|dual]] variables. By employing the [[proximal operator]], the
==Problem statement==
Line 47:
where <math> \partial F^* </math> and <math> \partial G</math> are the [[Subderivative|subgradient]] of the convex functions <math> F^* </math> and <math> G </math>, respectively.<ref name=":4" />
The
:<math display="block"> \min_{x\in\mathcal{X}} \max_{y\in\mathcal{Y}} \langle Kx, y \rangle + G(x) - F^*(y)
Line 55:
==Algorithm==
The
{{nowrap|Input: <math> F, G, K, \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''.
{{nowrap|<math> k \leftarrow 0 </math>}}
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 extended by S. Banert et al.<ref>{{Cite arXiv |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 \lVert L \rVert^{2} < 4 / ( 1 + 2 \theta )</math> |class=math.OC |eprint=2309.03998 }}</ref> to hold whenever <math>\theta>1/2</math> and <math>\tau \sigma \lVert K \rVert^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
==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
In case of <math> G </math> uniformly convex, with <math> \gamma>0 </math> the uniform-convexity constant, the modified algorithm becomes<ref name=":0" />
Line 89:
'''end do'''
{{algorithm-end}}
Moreover, the convergence of the algorithm slows down when <math>L</math>, the norm of the operator <math>K</math>, cannot be estimated easily or might be very large. Choosing proper [[Preconditioner|preconditioners]] <math>T</math> and <math>\Sigma</math>, modifying the proximal operator with the introduction of the [[Inner product space#Euclidean vector space|induced norm]] through the operators <math>T</math> and <math>\Sigma</math>, the convergence of the proposed preconditioned algorithm will be ensured.<ref>{{Cite book |last1=Pock |first1=Thomas |last2=Chambolle |first2=Antonin |title=2011 International Conference on Computer Vision |chapter=Diagonal preconditioning for first order primal-dual algorithms in convex optimization
==Application==
{{multiple image
}}
A typical application of this algorithm is in the image [[Noise reduction|denoising]] framework, based on total variation.<ref name=":2" /> It operates on the concept that signals containing excessive and potentially erroneous details exhibit a high total variation, which represents the integral of the absolute value gradient of the image.<ref name=":2" /> By adhering to this principle, the process aims to decrease the total variation of the signal while maintaining its similarity to the original signal, effectively eliminating unwanted details while preserving crucial features like edges. In the classical bi-dimensional discrete setting,<ref>{{Cite journal |last=Chambolle |first=Antonin |date=2004-01-01 |title=An Algorithm for Total Variation Minimization and Applications |url=https://doi.org/10.1023/B:JMIV.0000011325.36760.1e |journal=Journal of Mathematical Imaging and Vision |language=en |volume=20 |issue=1 |pages=89–97 |doi=10.1023/B:JMIV.0000011325.36760.1e |bibcode=2004JMIV...20...89C |issn=1573-7683 |s2cid=207622122|url-access=subscription }}</ref> consider <math>\mathcal{X} = \mathbb{R}^{NM}</math>, where an element <math> u\in\mathcal{X} </math> represents an image with the pixels values collocated in a Cartesian grid <math>N\times M</math>.<ref name=":0" />
Define the inner product on <math> \mathcal{X} </math> as<ref name=":0" />
Line 180 ⟶ 181:
\tilde{u}_{i,j}+\tau\lambda g_{i,j}}{1+\tau \lambda}
\end{align}
</math>The image total-variation denoising problem can be also treated with other algorithms<ref>{{Cite journal |last1=Esser |first1=Ernie |last2=Zhang |first2=Xiaoqun |last3=Chan |first3=Tony F. |date=2010 |title=A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science |url=http://epubs.siam.org/doi/10.1137/09076934X |journal=SIAM Journal on Imaging Sciences |language=en |volume=3 |issue=4 |pages=1015–1046 |doi=10.1137/09076934X |issn=1936-4954|url-access=subscription }}</ref> such as the '''[[Augmented Lagrangian method#Alternating direction method of multipliers|alternating direction method of multipliers]]''' (ADMM),<ref>{{Cite journal |last1=Lions |first1=P. L. |last2=Mercier |first2=B. |date=1979 |title=Splitting Algorithms for the Sum of Two Nonlinear Operators |url=https://www.jstor.org/stable/2156649 |journal=SIAM Journal on Numerical Analysis |volume=16 |issue=6 |pages=964–979 |doi=10.1137/0716071 |jstor=2156649 |bibcode=1979SJNA...16..964L |issn=0036-1429|url-access=subscription }}</ref> [[Proximal gradient methods for learning|projected (sub)-gradient]]<ref>{{Cite journal |last1=Beck |first1=Amir |last2=Teboulle |first2=Marc |date=2009 |title=A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |url=http://epubs.siam.org/doi/10.1137/080716542 |journal=SIAM Journal on Imaging Sciences |language=en |volume=2 |issue=1 |pages=183–202 |doi=10.1137/080716542 |s2cid=3072879 |issn=1936-4954|url-access=subscription }}</ref> or fast iterative shrinkage thresholding.<ref>{{Cite journal |last=Nestorov |first=Yu.E. |title=A method of solving a convex programming problem with convergence rate <math>O\bigl(\frac1{k^2}\bigr)</math> |url=https://www.mathnet.ru/eng/dan46009 |journal=Dokl. Akad. Nauk SSSR |volume=269 |issue=3 |pages=543–547}}</ref>
== Implementation ==
Line 208 ⟶ 209:
== External links ==
* [
{{Optimization algorithms|convex}}
| |||