# American Institute of Mathematical Sciences

June  2012, 5(3): 545-557. doi: 10.3934/dcdss.2012.5.545

## Alternating proximal algorithm with costs-to-move, dual description and application to PDE's

 1 Département de Mathématiques, Université Montpellier II, CC 051, Place Eugène, Bataillon, 34095 Montpellier Cedex 5, France

Received  April 2010 Revised  May 2010 Published  October 2011

Given real Hilbert spaces $\mathcal{X},\mathcal{Y},\mathcal{Z}$, closed convex functions $f : \mathcal{X} \longrightarrow \mathbb{R}\cup\{+\infty\}$, $g : \mathcal{Y} \longrightarrow \mathbb{R}\cup\{+\infty\}$ and linear continuous operators $A : \mathcal{X} \longrightarrow \mathcal{Z}$, $B : \mathcal{Y} \longrightarrow \mathcal{Z}$, we study the following alternating proximal algorithm $$$$\left\{ \begin{array}{ll} x_{n+1}&=argmin\{f(\zeta) + \frac{1}{2\gamma}\|A\zeta - By_n\|^2_z +\frac{\alpha}{2}\|\zeta - x_n\|^2_x; \quad \zeta\in\mathcal{X}\}\\ y_{n+1}&=argmin\{g(\eta) + \frac{1}{2\gamma}\|Ax_{n+1} - B\eta\|^2_z +\frac{\nu}{2}\|\eta - y_n\|^2_y; \quad \eta\in\mathcal{Y}\}, \end{array} \right.$$$$ where $\gamma$, $\alpha$ and $\nu$ are positive parameters. Under suitable conditions, we prove that any sequence $(x_n,y_n)$ generated by $(\mathcal{A})$ weakly converges toward a minimum point of the function $(x,y)\mapsto f(x) + g(y) + \frac{1}{2\gamma}\|Ax - By\|^2_z$ and that the sequence of dual variables $\left(-\frac{1}{\gamma}(Ax_n-By_n)\right)$ strongly converges in $\mathcal{Z}$ toward the unique minimizer of the function $z\mapsto f^*(A^*z)+g^*(-B^*z)+\frac{\gamma}{2}\|z\|^2_z$. An application is given in variational problems and PDE's.
Citation: Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545
##### References:
 [1] F. Acker and M.-A. Prestel, Convergence d'un schéma de minimisation alternée,, Annales de la Faculté des Sciences de Toulouse V, 2 (1980), 1. [2] H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE's,, Journal of Convex Analysis, 15 (2008), 485. [3] H. Attouch, G. Buttazzo and G. Michaille, "Variational Analysis in Sobolev and BV Spaces. Applications to PDE's and Optimization,", MPS/SIAM Series on Optimization, 6 (2006). [4] H. Attouch, A. Cabot, P. Frankel and J. Peypouquet, Alternating proximal algorithms for constrained variational inequalities. Applications to domain decomposition for PDE's,, accepted in Nonlinear Analysis., (). [5] H. Attouch, P. Redont and A. Soubeyran, A new class of alternating proximal minimization algorithms with costs-to-move,, SIAM Journal on Optimization, 18 (2007), 1061. doi: 10.1137/060657248. [6] H. H. Bauschke, P. L. Combettes and S. Reich, The asymptotic behavior of the composition of two resolvents,, Nonlinear Analysis, 60 (2005), 283. [7] A. Cabot and P. Frankel, Alternating proximal algorithms with costs-to-move and asymptotically vanishing coupling,, accepted in Optimization., (). [8] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, Bull. Amer. Math. Soc., 73 (1967), 591. doi: 10.1090/S0002-9904-1967-11761-0.

show all references

##### References:
 [1] F. Acker and M.-A. Prestel, Convergence d'un schéma de minimisation alternée,, Annales de la Faculté des Sciences de Toulouse V, 2 (1980), 1. [2] H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE's,, Journal of Convex Analysis, 15 (2008), 485. [3] H. Attouch, G. Buttazzo and G. Michaille, "Variational Analysis in Sobolev and BV Spaces. Applications to PDE's and Optimization,", MPS/SIAM Series on Optimization, 6 (2006). [4] H. Attouch, A. Cabot, P. Frankel and J. Peypouquet, Alternating proximal algorithms for constrained variational inequalities. Applications to domain decomposition for PDE's,, accepted in Nonlinear Analysis., (). [5] H. Attouch, P. Redont and A. Soubeyran, A new class of alternating proximal minimization algorithms with costs-to-move,, SIAM Journal on Optimization, 18 (2007), 1061. doi: 10.1137/060657248. [6] H. H. Bauschke, P. L. Combettes and S. Reich, The asymptotic behavior of the composition of two resolvents,, Nonlinear Analysis, 60 (2005), 283. [7] A. Cabot and P. Frankel, Alternating proximal algorithms with costs-to-move and asymptotically vanishing coupling,, accepted in Optimization., (). [8] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, Bull. Amer. Math. Soc., 73 (1967), 591. doi: 10.1090/S0002-9904-1967-11761-0.
 [1] Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79 [2] Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389 [3] Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067 [4] Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic & Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857 [5] Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 [6] Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341 [7] Armen Shirikyan. Ergodicity for a class of Markov processes and applications to randomly forced PDE'S. II. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 911-926. doi: 10.3934/dcdsb.2006.6.911 [8] Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 [9] M. Montaz Ali. A recursive topographical differential evolution algorithm for potential energy minimization. Journal of Industrial & Management Optimization, 2010, 6 (1) : 29-46. doi: 10.3934/jimo.2010.6.29 [10] Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645 [11] Jie Sun, Honglei Xu, Min Zhang. A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. doi: 10.3934/jimo.2019022 [12] Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249 [13] Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 0 (0) : 0-0. doi: 10.3934/mfc.2019009 [14] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [15] Lauri Oksanen. Solving an inverse problem for the wave equation by using a minimization algorithm and time-reversed measurements. Inverse Problems & Imaging, 2011, 5 (3) : 731-744. doi: 10.3934/ipi.2011.5.731 [16] Quanyi Liang, Kairong Liu, Gang Meng, Zhikun She. Minimization of the lowest eigenvalue for a vibrating beam. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2079-2092. doi: 10.3934/dcds.2018085 [17] Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027 [18] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [19] Mehdi Badsi, Martin Campos Pinto, Bruno Després. A minimization formulation of a bi-kinetic sheath. Kinetic & Related Models, 2016, 9 (4) : 621-656. doi: 10.3934/krm.2016010 [20] M. Zuhair Nashed, Alexandru Tamasan. Structural stability in a minimization problem and applications to conductivity imaging. Inverse Problems & Imaging, 2011, 5 (1) : 219-236. doi: 10.3934/ipi.2011.5.219

2018 Impact Factor: 0.545