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

Pierre Frankel

doi:10.3934/dcdss.2012.5.545

Article Contents

2012, Volume 5, Issue 3: 545-557. Doi: 10.3934/dcdss.2012.5.545

This issue Previous Article An identity involving exterior derivatives and applications to Gaffney inequality Next Article Exponential decay for solutions to semilinear damped wave equation

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

Received: April 2010

Revised: May 2010

Published: June 2012

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.