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

Previous Article
Exponential decay for solutions to semilinear damped wave equation
DCDS-S Home
This Issue
Next Article
An identity involving exterior derivatives and applications to Gaffney inequality

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

Pierre Frankel ^1,

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

Abstract
Related Papers

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.

Keywords: Convex minimization, proximal algorithm, alternating minimization, domain decomposition for PDE's..

Mathematics Subject Classification: 65K05, 65K10, 49J40, 90C2.

Citation: Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete and 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, Série Mathématiques, 2 (1980), 1-9.
[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-506.
[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, Society for Industrial and Applied Mathematics (SIAM), Mathematical Programming Society (MPS), Philadelphia, PA, 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-1081. 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-301.
[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-597. 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, Série Mathématiques, 2 (1980), 1-9.
[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-506.
[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, Society for Industrial and Applied Mathematics (SIAM), Mathematical Programming Society (MPS), Philadelphia, PA, 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-1081. 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-301.
[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-597. 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 and 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 and Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[3]	Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[4]	Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[5]	Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[6]	Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic and Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857
[7]	Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[8]	Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[9]	Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[10]	Armen Shirikyan. Ergodicity for a class of Markov processes and applications to randomly forced PDE'S. II. Discrete and Continuous Dynamical Systems - B, 2006, 6 (4) : 911-926. doi: 10.3934/dcdsb.2006.6.911
[11]	Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems and Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925
[12]	M. Montaz Ali. A recursive topographical differential evolution algorithm for potential energy minimization. Journal of Industrial and Management Optimization, 2010, 6 (1) : 29-46. doi: 10.3934/jimo.2010.6.29
[13]	Jie Sun, Honglei Xu, Min Zhang. A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1655-1662. doi: 10.3934/jimo.2019022
[14]	Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems and Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
[15]	Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l₁ norm fidelity term. Evolution Equations and Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[16]	Rongliang Chen, Jizu Huang, Xiao-Chuan Cai. A parallel domain decomposition algorithm for large scale image denoising. Inverse Problems and Imaging, 2019, 13 (6) : 1259-1282. doi: 10.3934/ipi.2019055
[17]	Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249
[18]	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
[19]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[20]	Lauri Oksanen. Solving an inverse problem for the wave equation by using a minimization algorithm and time-reversed measurements. Inverse Problems and Imaging, 2011, 5 (3) : 731-744. doi: 10.3934/ipi.2011.5.731

2020 Impact Factor: 2.425

Tools

Metrics

Other articles
by authors

on AIMS
Pierre Frankel
on Google Scholar
Pierre Frankel

[Back to Top]