Abstract

We study a forward backward splitting algorithm that solves the variational inequality Ax+∇Φ(x)+NC(x)∋0A x +\nabla \Phi(x)+ N_C (x) \ni 0 where H\mathcal{H} is a real Hilbert space, A:H⇉HA: \mathcal{H}\rightrightarrows \mathcal{H} is a maximal monotone operator, Φ:H→R\Phi: \mathcal{H}\to\mathbf{R} is a smooth convex function, and NCN_C is the outward normal cone to a closed convex set C⊂HC\subset\mathcal{H}. The constraint set CC is represented as the intersection of the sets of minima of two convex penalization function Ψ1:H→R\Psi_1:\mathcal{H}\to\mathbf{R} and Ψ2:H→R∪{+∞}\Psi_2:\mathcal{H}\to\mathbf{R}\cup \{+\infty\}. The function Ψ1\Psi_1 is smooth, the function Ψ2\Psi_2 is proper and lower semicontinuous. Given a sequence (βn)(\beta_n) of penalization parameters which tends to infinity, and a sequence of positive time steps (λn)(\lambda_n), the algorithm (SFBP), n≥1n\geq 1,  {x1∈H,xn+1=(I+λnA+λnβn∂Ψ2)−1(xn−λn∇Φ(xn)−λnβn∇Ψ1(xn)),\ \left\{\begin{array}{rcl} x_1 & \in & \mathcal{H},\\ x_{n+1} & = & (I+\lambda_n A+\lambda_n\beta_n\partial\Psi_2)^{-1} (x_n-\lambda_n\nabla\Phi(x_n)-\lambda_n\beta_n\nabla\Psi_1(x_n)), \end{array}\right. performs forward steps on the smooth parts and backward steps on the other parts. Under suitable assumptions, we obtain weak ergodic convergence of the sequence (xn)(x_n) to a solution of the variational inequality. Convergence is strong when either AA is strongly monotone or Φ\Phi is strongly convex. We also obtain weak convergence of the whole sequence (xn)(x_n) when AA is the subdifferential of a proper lower semicontinuous convex function. This provides a unified setting for several classical and more recent results, in the line of historical research on continuous and discrete gradient-like systems.

Author information

Contact details are reproduced from the original publication and may be historical.

Marc-Olivier Czarnecki

Institut de Mathématiques et Modélisation, Université Montpellier 2, Place Eugène Bataillon, 34095 Montpellier cedex 5, France
and: CNRS

marco@univ-montp2.fr

Nahla Noun

Département de Mathématiques, Faculté des Sciences 1, Université Libanaise, Hadath, Beyrouth, Lebanon

nahla.noun@ul.edu.lb

Juan Peypouquet

Departamento de Matemática, Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso, Chile

juan.peypouquet@usm.cl

Keywords

  • Constrained convex optimization
  • forward-backward algorithms
  • hierarchical optimization
  • maximal monotone operators
  • penalization methods
  • variational inequalities

Mathematics Subject Classification

37N40, 46N10, 49M30, 65K05, 65K10, 90B50, 90C25

References

  1. F. Álvarez, J. Peypouquet: Asymptotic almost-equivalence of Lipschitz evolution systems in Banach spaces, Nonlinear Anal. 73(9) (2010) 3018–3033.https://doi.org/10.1016/j.na.2010.06.070Google Scholar
  2. H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, J. Differ. Equations 128 (1996) 519–540.https://doi.org/10.1006/jdeq.1996.0104Google Scholar
  3. H. Attouch, M.-O. Czarnecki: Asymptotic behavior of coupled dynamical systems with multiscale aspects, J. Differ. Equations 248(6) (2010) 1315–1344.https://doi.org/10.1016/j.jde.2009.06.014Google Scholar
  4. H. Attouch, M.-O. Czarnecki, J. Peypouquet: Prox-penalization and splitting methods for constrained variational problems, SIAM J. Optim. 21(1) (2011) 149–173https://doi.org/10.1137/100789464Google Scholar
  5. H. Attouch, M.-O. Czarnecki, J. Peypouquet: Coupling forward-backward with penalty schemes and parallel splitting for constrained variational inequalities, SIAM J. Optim. 21(4) (2011) 1251–1274.https://doi.org/10.1137/110820300Google Scholar
  6. J.-B. Baillon: Un exemple concernant le comportement asymptotique de la solution du problème du/dt + ∂φ(u) = 0, J. Funct. Anal. 28, (1978) 369–376.https://doi.org/10.1016/0022-1236(78)90093-9Google Scholar
  7. J.-B. Baillon: Comportement Asymptotique des Contractions et Semi-Groupes de Contractions - Equations de Schroedinger non Lineaires et Divers, Thèse, Université Paris VI, Paris (1978).Google Scholar
  8. J.-B. Baillon, H. Brézis: Une remarque sur le comportement asymptotique des semi-groupes non linéaires, Houston J. Math. 2 (1976) 5–7.Google Scholar
  9. J.-B. Baillon, R. Cominetti: A convergence result for nonautonomous subgradient evolution equations and its application to the steepest descent exponential penalty trajectory in linear programming, J. Funct. Anal. 187 (2001) 263–273.https://doi.org/10.1006/jfan.2001.3828Google Scholar
  10. J.-B. Baillon, G. Haddad: Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones, Israel J. Math. 26(2) (1977) 137–150.https://doi.org/10.1007/BF03007664Google Scholar
  11. H.-H. Bauschke, P.-L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, Berlin (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  12. D. Bertsekas: Nonlinear Programming, 2nd Ed., Athena Scientific, Belmont (2003).Google Scholar
  13. R. I. Boţ, E. R. Csetnek: Forward-backward and Tseng’s type penalty schemes for monotone inclusion problems, Set-Valued Var. Anal. 22(2) (2014) 313–331.https://doi.org/10.1007/s11228-014-0274-7Google Scholar
  14. H. Brézis: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North Holland, Amsterdam (1973).Google Scholar
  15. H. Brézis, P.-L. Lions: Produits infinis de résolvantes, Israel J. Math. 29 (1978) 329–345.https://doi.org/10.1007/BF02761171Google Scholar
  16. R.-E. Bruck: Asymptotic convergence of nonlinear contraction semigroups in Hilbert spaces, J. Funct. Anal. 18 (1975) 15–26.https://doi.org/10.1016/0022-1236(75)90027-0Google Scholar
  17. R.-E. Bruck: On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space, J. Math. Anal. Appl. 61 (1977) 159–164.https://doi.org/10.1016/0022-247X(77)90152-4Google Scholar
  18. R. Burachik, L.-M. Grana Drummond, A.-N. Iseum, B.-F. Svaiter: Full convergence of the steepest descent method with inexact line searches, Optimization 32 (1995) 137–146.https://doi.org/10.1080/02331939508844042Google Scholar
  19. A. Cabot: The steepest descent dynamical system with control. Applications to constrained minimization, ESAIM, Control Optim. Calc. Var. 10 (2004) 243–258.https://doi.org/10.1051/cocv:2004005Google Scholar
  20. A. Cabot: Proximal point algorithm controlled by a slowly vanishing term. Applications to hierarchical minimization, SIAM J. Optim. 15(8) (2005) 1207–1223.https://doi.org/10.1137/S105262340343467XGoogle Scholar
  21. A.-L. Cauchy: Méthode générale pour la résolution des systèmes d’équations simultanées, C. R. Acad. Sci. Paris 25 (1847) 536–538.Google Scholar
  22. P.-L. Combettes: Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization 53(5-6) (2004) 475–504.https://doi.org/10.1080/02331930412331327157Google Scholar
  23. L.-C. Evans: Partial Differential Equations, 2nd Ed., Graduate Studies in Mathematics 19, American Mathematical Society, Providence (2010).https://doi.org/10.1090/gsm/019Google Scholar
  24. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim. 29(2) (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  25. P.-L. Lions: Une methode iterative de resolution d’une inequation variationnelle, Israel J. Math. 31(2) (1978) 204–208.https://doi.org/10.1007/BF02760552Google Scholar
  26. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (1970) 154–159.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  27. B. Martinet: Détermination approchée d’un point fixe d’une application pseudocontractante, C. R. Acad. Sci., Paris, Sér. A 274 (1972) 163–165.Google Scholar
  28. J.-J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  29. J.-J. Moreau: Fonctionnelles convexes, Séminaire Jean Leray 2 (1966–1967) 1–108.Google Scholar
  30. N. Noun: Convergence et Stabilisation de Systèmes Dynamiques Couplés et Multi-Échelles vers des Équilibres sous Contraintes: Application à l’Optimisation Hiérarchique, PhD Thesis, Université Montpellier 2, Montpellier; Université Libanaise à Beyrouth, Beirut (2013).Google Scholar
  31. N. Noun, J. Peypouquet: Forward-backward-penalty scheme for constrained convex minimization without inf-compactness, J. Optim. Theory Appl. 158(3) (2013) 787–795.https://doi.org/10.1007/s10957-013-0296-6Google Scholar
  32. Z. Opial: Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc. 73 (1967) 591–597.https://doi.org/10.1090/S0002-9904-1967-11761-0Google Scholar
  33. G. Passty: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl. 72(2) (1979) 383–390.https://doi.org/10.1016/0022-247X(79)90234-8Google Scholar
  34. J. Peypouquet: Convex Optimization in Normed Spaces: Theory, Methods and Examples, Springer, Cham (2015).https://doi.org/10.1007/978-3-319-13710-0Google Scholar
  35. J. Peypouquet: Coupling the gradient method with a general exterior penalization scheme for convex minimization, J. Optim. Theory Appl. 153(1) (2012) 123–138.https://doi.org/10.1007/s10957-011-9936-xGoogle Scholar
  36. J. Peypouquet, S. Sorin: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time, J. Convex Analysis 17 (2010) 1113–1163.https://doi.org/10.68381/jca17068Google Scholar
  37. R.-T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  38. R.-T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–897.https://doi.org/10.1137/0314056Google Scholar

Suggested citation

M.-O. Czarnecki, N. Noun, J. Peypouquet. “Splitting Forward-Backward Penalty Scheme for Constrained Variational Problems.” Journal of Convex Analysis 23 (2016), No. 2, 531–565. https://doi.org/10.68381/jca23020

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2016. Rights now held by Banach Press.