Journal of Convex Analysis 23 (2016), No. 2, 531--565
Copyright Heldermann Verlag 2016
Splitting Forward-Backward Penalty Scheme for Constrained Variational Problems
Marc-Olivier Czarnecki
Institut de Mathématiques et Modélisation, Université Montpellier 2, Place Eugène Bataillon, 34095 Montpellier cedex 5, France
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
[Abstract-pdf]
\newcommand{\R}{\mathbf{R}} \renewcommand{\H}{\mathcal{H}} We study a forward backward splitting algorithm that solves the variational inequality \begin{equation*} A x +\nabla \Phi(x)+ N_C (x) \ni 0 \end{equation*} where $\H$ is a real Hilbert space, $A: \H\rightrightarrows \H$ is a maximal monotone operator, $\Phi: \H\to\R$ is a smooth convex function, and $N_C$ is the outward normal cone to a closed convex set $C\subset\H$. The constraint set $C$ is represented as the intersection of the sets of minima of two convex penalization function $\Psi_1:\H\to\R$ and $\Psi_2:\H\to\R\cup \{+\infty\}$. The function $\Psi_1$ is smooth, the function $\Psi_2$ is proper and lower semicontinuous. Given a sequence $(\beta_n)$ of penalization parameters which tends to infinity, and a sequence of positive time steps $(\lambda_n)$, the algorithm (SFBP), $n\geq 1$, \begin{equation*} \ \left\{\begin{array}{rcl} x_1 & \in & \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. \end{equation*} 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 $(x_n)$ to a solution of the variational inequality. Convergence is strong when either $A$ is strongly monotone or $\Phi$ is strongly convex. We also obtain weak convergence of the whole sequence $(x_n)$ when $A$ 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.
Keywords: Constrained convex optimization, forward-backward algorithms, hierarchical optimization, maximal monotone operators, penalization methods, variational inequalities.
MSC: 37N40, 46N10, 49M30, 65K05, 65K10, 90B50, 90C25
[ Fulltext-pdf (254 KB)] for subscribers only.