    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 $$\begin{equation} \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. \end{equation}$$ 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:
  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. Google Scholar  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. Google Scholar  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). Google Scholar  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., ().   Google Scholar  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.  Google Scholar  H. H. Bauschke, P. L. Combettes and S. Reich, The asymptotic behavior of the composition of two resolvents,, Nonlinear Analysis, 60 (2005), 283. Google Scholar  A. Cabot and P. Frankel, Alternating proximal algorithms with costs-to-move and asymptotically vanishing coupling,, accepted in Optimization., ().   Google Scholar  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.  Google Scholar

show all references

##### References:
  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. Google Scholar  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. Google Scholar  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). Google Scholar  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., ().   Google Scholar  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.  Google Scholar  H. H. Bauschke, P. L. Combettes and S. Reich, The asymptotic behavior of the composition of two resolvents,, Nonlinear Analysis, 60 (2005), 283. Google Scholar  A. Cabot and P. Frankel, Alternating proximal algorithms with costs-to-move and asymptotically vanishing coupling,, accepted in Optimization., ().   Google Scholar  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.  Google Scholar
  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  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  Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020103  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  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  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  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  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  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  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  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  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  Rongliang Chen, Jizu Huang, Xiao-Chuan Cai. A parallel domain decomposition algorithm for large scale image denoising. Inverse Problems & Imaging, 2019, 13 (6) : 1259-1282. doi: 10.3934/ipi.2019055  Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034  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  Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009  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  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  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  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

2018 Impact Factor: 0.545