Abstract
In this paper we propose the forward–backward splitting methods with linesearches for solving nonsmooth optimization problems without the standard assumption of the Lipschitz continuity of the gradient in Banach spaces. We prove the weak convergence of the iterative sequence generated by these methods, and further prove convergence with asymptotic rate \(\frac{1}{n}\) to the optimal value under the assumption of the boundedness of the iterative sequence.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let X be a reflexive, strictly convex and smooth Banach space with dual space \(X^{*}.\) Consider the optimization problem:
where \(f:X\rightarrow (-\infty ,+\infty ]\) is proper, lower semicontinuous and convex, \(g:X\rightarrow (-\infty ,+\infty )\) is convex Gâteaux differentiable. We denote by \(\varPhi ^{*}\) the infimum value of the problem (1). The set of solutions to problem (1) is denoted by \(\mathcal {S}.\) We shall assume in what follows that the set \(\mathcal {S}\) is nonempty. Since \(\varPhi \) is proper, lower semicontinuous and convex, \(\mathcal {S}\) is a nonempty closed and convex set. Despite its simple form, problem (1) has been shown to cover a wide range of apparently unrelated signal recovery formulations (see [12,13,14, 18]).
The forward–backward splitting method is an effective method to solve (1), which allows to decouple the contributions of the functions f and g in a gradient descent step determined by f and in a backward implicit step induced by g. Forward–backward methods belong to the class of proximal splitting methods. These methods require the computation of the proximity operator and the approximation of proximal points(see [14, 20]).
The forward–backward splitting iteration procedure proposed in [14] is given in Hilbert space H and is governed by the updating rule:
Generalization of this method from Hilbert spaces to Banach spaces is not immediate. The main difficulties are due to the fact that the inner product structure of a Hilbert space is missing in a Banach space. The proposed forward–backward splitting method for solving problem (1) in Banach space suggested in this work aims at establishing a bridge between the well known forward–backward splitting in Hilbert spaces [14, 20] and that in Banach spaces. The use of a general regularizing function \(\Vert \cdot \Vert ^{p}\) instead of the square of the norm is rather natural in a Banach space, where the square of the norm loses the privileged role it enjoys in Hilbert spaces [4]. For instance, it is not hard to verify that in the spaces \(X=l_{p}\) or \(X=L_{p}(1<p<+\infty ),\) \(x_{n+1}\in \mathrm{argmin}_{y\in X}\{\frac{1}{p}\Vert y-x_{n}\Vert ^{p}+t_{n}(\langle \nabla g(x_{n}),y\rangle +f(y))\}\) becomes simpler than \(x_{n+1}\in \mathrm{argmin}_{y\in X}\{\frac{1}{2}\Vert y-x_{n}\Vert ^{2}+t_{n}(\langle \nabla g(x_{n}),y\rangle +f(y))\}.\) In [10], the following generalization of the forward–backward iteration procedure was proposed in reflexive Banach spaces X:
where, the gradient operator \(\nabla g\) is \((p-1)\) Hölder-continuous on X , i.e., there exists a constant L such that
In [16], Guan and Song proposed another type generalization of the forward–backward method in reflexive Banach spaces
where \(J_{p}:X \rightarrow X^{*}\) is the p-duality mapping and \(\{z_{n}\}\) is absolutely summable sequence.
In particular, if X is a Hilbert space and \(p=2\), then formula (3) and (4) reduces to formula (2). In [16], it is shown that the sequence of functional values converges with the convergence rate \(n^{1-p}\) to the optimal value of Problem (1) under appropriate assumptions. In [17], Guan and Song further extended forward–backward splitting method (3) to more general case, i.e., by taking a convex combination of the current step and the previous step:
and proved that the sequence of the functional values converges with an asymptotic rate \(n^{1-p}\) to the optimal value. They also proved that the sequence of the functional values converges with an asymptotic rate under an error bound assumption.
The convergence of the forward–backward splitting method to an optimal solution of (1) is usually established under the assumption that the gradient of g is Lipschitz continuous and the stepsize \(t_{n}\) is taken less than some constant related with Lipschitz modulus. When \(\nabla g\) is Lipschitz continuous but somehow the Lipschitz constant is not known or \(\nabla g\) is not Lipschitz continuous, finding the stepsize \(t_{n}\) that guarantees the convergence of (2) would be a challenge.
Beck and Teboulle [6] proposed a proximal gradient method with backtracking stepsize rules overcome this inconvenience. As far as we observe, the theory of convergence and complexity for the proximal forward–backward is almost complete under such a Lipschitz assumption. However, the Lipschitz condition fails in many natural circumstance; see, e.g., [15]. Bello Cruz and Nghia [7] introduced two new linesearches into the frame of the forward–backward splitting method and prove the convergence analysis and complexity results of cost values. These two linesearch rules were also recently studied in [19, 21, 22] in conjunction with the forward–backward splitting algorithm for convex minimization problems without the assumption of the Lipschitz continuous gradient.
Bauschke, Bolte and Teboulle [5] introduced Bregman-based proximal gradient methods which share most of the convergence properties and complexity of the classical proximal-gradient, instead of the restrictive condition of Lipschitz continuity of the gradient of the differentiable they assuming a more general and flexible convexity condition. [8] further extended the above approach to nonconvex composite model with smooth adaptable functions and proved the global convergence to a critical point under natural assumptions on the problems data.
In this paper, following the lines of [7, 21], we propose the forward–backward splitting method with linesearches in the framework of Banach spaces. The main advantage of our algorithms is that the Lipschitz constants of the gradient of functions do not require in computation. The paper is organized as follows. The next section presents some preliminary results that will be used throughout the paper. Section 4 is devoted to the study of the forward–backward splitting method (3) with Linesearch 1. We prove that the sequence of the functional values converges with an asymptotic rate \(\frac{1}{n}\) to the optimal value of the minimization Problem (1). In Sect. 5, we further study forward–backward splitting method (5) with Linesearch 2. We prove that the sequence of the functional values converges with an asymptotic rate \(\frac{1}{n}\) to the optimal value. We also prove that the sequence of the functional values Q-linear converges under an error bound assumption if \(t_{n}\ge \bar{t}>0.\)
2 Preliminaries
In this section we present some definitions and results needed for our paper. Let f be a lower semi-continuous proper convex function from X to \((-\infty ,+\infty ]\). We denote the domain of f by \(\mathrm{dom}f := \{x\in X| f(x) < +\infty \}.\) The subdifferential of f at \(x\in X\) is the convex set
It follows from definition (6) that a point \(\hat{x}\) is a minimizer of f if and only if \(0\in \partial f(\hat{x}).\) The subdifferential mapping \(x\rightarrow \partial f(x)\) has following property of monotonicity, i.e.,
The subdifferential operator \(\partial f\) is maximal monotone [2]. Moreover, the graph of \(\partial f\) is demiclosed [2], i.e., if \(\{(x_{n},x^{*}_{n})\}\subset \mathrm{Gph}(\partial f)\) satisfies that \(\{x_{n}\}\) converges weakly to x and \(\{x^{*}_{n}\}\) converges strongly to \(x^{*},\) then \((x,x^{*})\in \mathrm{Gph}(\partial f).\) If f and g are two lower semicontinuous proper convex functions and if the regularity condition \(0\in \mathrm{int( dom}f-\mathrm{dom}g)\) holds, then for any \(\bar{x}\in \mathrm{dom}f\cap \mathrm{dom}g,\) we have (see [9]) \(\partial (f+g)(\bar{x})=\partial f(\bar{x})+\partial g(\bar{x})\)
The p-duality mapping \(J_{p} : X \rightarrow X^{*}\) is defined by
The Hahn-Banach theorem guarantees that \(J_{p}(x)\ne \emptyset \) for every \(x\in X.\) It is clear that \(J_{p}(x)=\partial (\frac{1}{p}\Vert \cdot \Vert ^{p})(x)\) for all \(x\in X.\) It is well known that if X is smooth, then \(J_{p}\) is single valued and is norm-to-weak star continuous. Properties of the duality mapping have been given in [1, 11, 23].
Let \(\{x_{n}\}\) be a sequence in X that converges to \(\bar{x}.\) We say that the convergence is Q-linear if there exists a constant \(r\in (0,1)\) such that
for all n sufficiently large. We say that the convergence is R-linear if there exists a sequence of nonnegative scalars \(\{\alpha _{n}\}\) such that
and \(\{\alpha _{n}\}\) converges Q-linearly to zero.
Definition 1
[2] A functional f is called lower semicontinuous at the point \(x_{0}\in \mathrm{dom} f\) if for any sequence \(x_{n}\in \mathrm{dom} f\) such that \(x_{n}\rightarrow x_{0}\) there holds the inequality
If the inequality (7) occurs with the condition that the convergence of \({x_{n}}\) to \(x_{0}\) is weak, then the functional f is called weakly lower semicontinuous at \(x_{0}.\)
Lemma 1
[2] Let f be a convex and lower semicontinuous functional. Then it is weakly lower semicontinuous.
Lemma 2
[3] Let \(\{a_{n}\}, \{b_{n}\}\) and \(\{\epsilon _{n}\}\) be real sequences. Assume that \(\{a_{n}\}\) is bounded from below, \(\{b_{n}\}\) is nonnegative, \(\sum _{n=1}^{\infty }|\epsilon _{n}|< +\infty \) and \(a_{n+1}-a_{n}+b_{n}\le \epsilon _{n}.\) Then \(\{a_{n}\}\) converges and \(\sum _{n=1}^{\infty }b_{n}< +\infty .\)
Definition 2
[10] Let \(f:X\rightarrow (-\infty ,+\infty ]\) be proper, convex and lower semicontinuous. f is called totally convex at \(\bar{x}\in X,\) if for each \(x^{*}\in \partial f(\bar{x})\) and each sequence \(\{x_{n}\},\) the following implication holds
The following standing assumptions on the data of problem (1) will be used throughout the paper:
Assumption 1
The gradient \(\nabla g\) is uniformly continuous on any bounded subset of X and maps any bounded subset of X to a bounded set in \(X^{*}.\)
3 The FBS Method with Linesearch 1
In this section, we shall consider the convergence and convergence rate of the following forward–backward splitting method:
Iterative Method 3.1. Given \(x_{0}\in X\), for every \(n\in \mathbf {N},\) set
where \(t_n=\mathbf{Linesearch~1}(x_{n}, ~\alpha ,~\theta ,~\beta ).\)
Lemma 3
[17] For any \(x\in X\) and \(t>0,\) let
Then, for any \(0<t_{1}\le t_{2},\) we have
Lemma 4
If \(x\in \mathrm{dom}f,\) then Linesearch 1\((x,\alpha ,\theta ,\beta )\) stops after finitely many steps.
Proof
If \(x\in \mathcal {S},\) then \(x=\hat{x}_{\alpha }.\) Thus the linesearch stops at zero step and gives us the output \(\alpha .\) If \(x\notin \mathcal {S},\) by contradiction suppose that for all \(t_{k}=\alpha \theta ^{k},~k\in \mathbf {N}\)
It follows from Lemma 3 that \(\Vert x-\hat{x}_{t_{k}}\Vert \le \Vert x-\hat{x}_{\alpha }\Vert ,\) that is, \(\{\hat{x}_{t_{k}}\}\) is bounded. Thus we get from (9) that \( \Vert \hat{x}_{t_{k}}-x\Vert \rightarrow 0\) as \(k\rightarrow +\infty \) thanks to Assumption 1. The latter implies \( \Vert \nabla g(\hat{x}_{t_{k}})-\nabla g(x)\Vert \rightarrow 0\) as \(k\rightarrow +\infty \) by Assumption 1 again. From (9) we also obtain
The optimality of \(\hat{x}_{t_{k}}\) implies
Then, we have
By letting \(k\rightarrow +\infty \) in the above inclusion and using (10), we get from the demiclosedness of \(\mathrm{Gph}(\partial f) \) that \(0\in \partial f(x)+\nabla g(x).\) This contradicts the assumption that x is not an optimal solution to problem (1) and completes the proof of the lemma. \(\square \)
Remark 1
We observe from Lemma 4 that for finding the stepsize \(t_{n}\) in the above scheme is finite. Hence the choice of sequence \(\{x_{n}\}\) in Iterative Method 3.1 is well defined. Another important feature from the definition of Linesearch 1 useful for our analysis is the following inequality
Proposition 1
Let \(\{x_{n}\}\) be a sequence generated by Iterative Method 3.1 and define
Then, we have
-
(i)
\(\Vert x_{n}-x_{n+1}\Vert ^{p}\le t_{n}h(x_{n}).\)
-
(ii)
\(\varPhi (x_{n+1})\le \varPhi (x_{n})-(1-\beta )h(x_{n}).\)
-
(iii)
\(\varPhi (x_{n})\) converges and \(\sum _{n=1}^{\infty }h(x_{n})<+\infty .\)
Proof
(i) The optimality of \(x_{n+1}\) implies
Then, we have
Hence,
and so that
(ii) Using the definition of \(h(x_{n})\) and (11) we have
(iii) The conclusion follows using Lemma 2 and Proposition 1 (ii). \(\square \)
Proposition 2
Let \(\{x_{n}\}\) be a sequence generated by Iterative Method 3.1. Assume the sequence \(\{x_{n}\}\) is bounded. Then,
-
(i)
\(\lim \limits _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\)
-
(ii)
all weak accumulation points of \(\{x_{n}\}\) belong to \(\mathcal {S}.\)
Proof
(i) Let \(\hat{x}\in \mathcal {S}.\) Since \(g(x_{n})-g(\hat{x})\le \langle \nabla g(x_{n}),x_{n}-\hat{x}\rangle \) and \(\varPhi (x_{n})-\varPhi ^{*} =f(x_{n})-f(\hat{x})+g(x_{n})-g(\hat{x}),\) we have that
Then, by (12) and (13), we have
Now let us split our further analysis into two distinct cases.
Case 1 Suppose that there exists \(\bar{t}>0\) such that \(t_{n}\ge \bar{t}\) for all \(n\in \mathbf {N}.\) Then, by Proposition 1 and (14), we have
Since \(\{x_{n}\}\) is bounded and \(\alpha \ge t_{n}\ge \bar{t}>0\), there exists \(c_{1}\ge 0\) such that \(t_{n}^{-\frac{1}{p}}\Vert \hat{x}-x_{n+1}\Vert \le c_{1}.\) Hence,
Since \(\{\varPhi (x_{n})-\varPhi ^{*}\}\) is bounded by Proposition 1(iii), there exist \(c_{2}\ge 0\) such that
Then, by (15) and (16), we have
Using (17), we get that
and so that,
Hence, by (18) and Lemma 2, we easily obtain, \(\lim \nolimits _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\)
Case 2 Suppose now that \(\{t_{k}\}\subset \{t_{n}\}\) and \(\lim _{k\rightarrow +\infty }t_{k}=0.\) Since \(\{x_{n}\}\) is bounded, the set of its weak accumulation points is nonempty. Without loss of generality, we assume that \(\{x_{k}\}\) weakly converging to \(\bar{x}\). Define \(\hat{t}_{k}=\frac{t_{k}}{\theta }>t_{k}>0\) and
Due to Lemma 3 we have
which combines with the boundedness of \(\{x_{k}\}\) to show that the sequence \(\{\hat{x}_{\hat{t}_{k}}\}\) is also bounded. It follows from the definition of Linesearch 1 that
Since \(\lim _{k\rightarrow +\infty }\hat{t}_{k}=0\) and both \(\{x_{k}\}\) and \(\{\hat{x}_{\hat{t}_{k}}\}\) are bounded, (19) together with Assumption 1 tell us that \(\lim _{k\rightarrow +\infty }\Vert x_{k}-\hat{x}_{\hat{t}_{k}}\Vert =0\) and thus \(\{\hat{x}_{\hat{t}_{k}}\}\) also weakly converges to \(\bar{x}.\) Thanks to Assumption 1 again, we have
This and (19) imply that
Since
By letting \(k\rightarrow +\infty ,\) we get from (20) and (21) that \(0\in \partial (f+g)(\bar{x}),\) which means \(\bar{x}\in \mathcal {S}.\) It remains to verify (i) in this case. Indeed, we get from Lemma 3 that
This together with (21) yields
Hence, by Proposition 1(iii) and (14), we have \(\varPhi (x_{n})\rightarrow \varPhi ^{*}.\)
(ii) Since \(\lim _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*},\) the sequence \(\{x_{n}\}\) is minimizing sequence, thus, due to the weak lower semicontinuity of \(\varPhi \)(see lemma 1), all weak accumulation points of \(\{x_{n}\}\) belong to \(\mathcal {S}.\) \(\square \)
Proposition 3
Let \(\{x_{n}\}\) be a sequence generated by Iterative Method 3.1. Suppose that the sequence \(\{x_{n}\}\) is bounded and there exists \(\bar{t}>0\) such that \(t_{n}\ge \bar{t}.\) Then, \(\varPhi (x_{n})-\varPhi ^{*}\le \lambda n^{1-p}\) for some \(\lambda >0.\)
Proof
By the mean value theorem, we have
where, q is the dual exponent, i.e., \(\frac{1}{p}+\frac{1}{q}=1\) and \(\varPhi (x_{n+1})-\varPhi ^{*}\le \xi \le \varPhi (x_{n})-\varPhi ^{*}.\) Thus,
and, by (18),
where, \(\bar{c}=\left( \frac{1-\beta }{c_{2}}\right) ^{\frac{p}{p-1}}.\) Summing up then yields
and consequently,
Hence, there exists \(\lambda >0,\) such that \(\varPhi (x_{n})-\varPhi ^{*}\le \lambda n^{1-p}.\) \(\square \)
4 The FBS Method with Linesearch 2
Lemma 5
If \(x\in \mathrm{dom}f,\) then Linesearch 2\((x,\theta )\) stops after finitely many steps.
Proof
If \(x\in \mathcal {S},\) then \(x=\hat{x}.\) Thus the linesearch immediately give us the output 1 without proceeding any step. If \(x\notin \mathcal {S},\) by contradiction let us assume that Linesearch 2 does not stop after finitely many steps. Thus for all \(t\in \{1,\theta ,\theta ^{2},\cdots \},\) we obtain
Since \(f(x-t(x-\hat{x}))\le (1-t)f(x)+tf(\hat{x}),\) we have
Then we get that
Hence we have \(\hat{x}=x,\) which readily implies that \(0\in \partial f(x)+\nabla g(x).\) This contradicts the assumption that x is not an optimal solution to problem and completes the proof of the lemma. \(\square \)
In this section, we shall consider the convergence and convergence rate of the following forward–backward splitting method:
Iterative Method 4.1.
Given \(x_{0}\in X,\) for every \(n\in \mathbf {N},\) set
where \(t_n=\mathbf{Linesearch ~2}(x_{n}, ~\theta ).\)
Remark 2
Let \(\{x_{n}\}\) and \(\{y_{n}\}\) be sequences generated by Iterative Method 4.1. It follows from Linesearch 2\((x_{n}, ~\theta )\) that
If we remove the f term from Linesearch 2\((x_{n}, ~\theta ),\) we can still get this result from the convexity of f. However, if f is a strictly convex or strongly convex function, the number of iteration step for Linesearch 2 may be reduced.
Next we obtain some similar results for Iterative Method 4.1 to the ones in Sect. 4 for Iterative Method 3.1.
Proposition 4
Let \(\{x_{n}\}\) be a sequence generated by Iterative Method 4.1 and define
Then, we have
-
(i)
\(\frac{1}{t_{n}^{p}}\Vert x_{n}-x_{n+1}\Vert ^{p}\le \rho (x_{n}).\)
-
(ii)
\(\varPhi (x_{n+1})\le \varPhi (x_{n})-t_{n}(1-\frac{1}{p})\rho (x_{n}).\)
-
(iii)
\(\varPhi (x_{n})\) converges and \(\sum _{n=1}^{\infty }t_{n}\rho (x_{n})<+\infty .\)
Proof
(i) The optimality of \(y_{n}\) implies
Then, we have
Hence, by \(y_{n}=\frac{1}{t_{n}}x_{n+1}+(1-\frac{1}{t_{n}})x_{n},\) we have
and so that
(ii) Using the definition of \(\rho (x_{n})\) and Remark 2, we get that
It follows from (23) and (24) that
(iii) The conclusion follow using Lemma 2 and Proposition 4 (ii). \(\square \)
Proposition 5
Let \(\{x_{n}\}\) and \(\{y_{n}\}\) be sequences generated by Iterative Method 4.1. Assume the sequence \(\{x_{n}\}\) is bounded. Then,
-
(i)
all weak accumulation points of \(\{x_{n}\}\) belong to \(\mathcal {S}.\)
-
(ii)
if there exists \(\{t_{k}\}\subset \{t_{n}\}\) such that \(t_{k}\rightarrow \bar{t}>0,\) then \(\lim \nolimits _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\)
-
(iii)
if \(t_{n}\rightarrow 0\) and f is uniformly continuous on any bounded subset of \(\mathrm{dom}f,\) then \(\lim \nolimits _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\)
Proof
(i) Let \(\hat{x}\in \mathcal {S}\) and \(\{x_{k}\}\subset \{x_{n}\}\) weakly converging to \(\bar{x}\). Since
and
we have that
Then, by (22) and (25), we have
Now let us split our further analysis into two distinct cases.
Case 1 Without loss of generality, we assume that \(t_{k}\rightarrow \bar{t}>0.\) Then, by Proposition 4, we have \(\lim _{n\rightarrow \infty }\rho (x_{n})=0\) and \(\lim _{n\rightarrow \infty }\Vert x_{n}-x_{n+1}\Vert =0.\) Then by (26), we have \(\lim _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\) Hence, the sequence \(\{x_{k}\}\) is minimizing sequence, thus, due to the weak lower semicontinuity of \(\varPhi \), \(\bar{x}\in \mathcal {S}.\)
Case 2 Suppose now that \(\lim _{k\rightarrow +\infty }t_{k}=0.\) Define \(\hat{t}_{k}=\frac{t_{k}}{\theta }>t_{k}>0\) and
It follows from the definition of Linesearch 2\((x_{k},\theta )\) that
This together with (6) and (27) gives us that
We obtain from the latter that
which yields
On the other hand,
and
Adding the two inequalities, we get
Then we have
Hence
Due to Assumption 1, \(p>1\) and the boundedness of \(\{x_{n}\},\) the latter tells us that \(\{y_{k}\}\) is also bounded. This together with (27) and the fact \(\lim _{k\rightarrow +\infty }t_{k}=0\) implies \(\lim _{k\rightarrow +\infty }\Vert \hat{x}_{k+1}-x_{k}\Vert =0.\) Since \(\nabla g\) is uniformly continuous on bounded sets, we get \(\lim _{k\rightarrow +\infty }\Vert \nabla g(\hat{x}_{k+1})-\nabla g(x_{k})\Vert =0\) and derive from (28) that
Since \(\nabla g\) is uniformly continuous on bounded sets, (29) implies
Since \(J_{p}(x_{k}-y_{k})-\nabla g(x_{k})+\nabla g(y_{k})\in \partial f(y_{k})+\nabla g(y_{k})=\partial (f+g)(y_{k}).\) By passing to the limit over the subsequence \(\{x_{k}\}\) in the above inclusion, we get from (29) and (30) that \(0\in \partial (f+g)(\bar{x}),\) which means \(\bar{x}\in \mathcal {S}.\)
(ii) Suppose now that \(\{t_{k}\}\subset \{t_{n}\}\) and \(t_{k}\rightarrow \bar{t}>0,\) Hence, by Proposition 4 and (26), we have \(\lim _{k\rightarrow \infty }\varPhi (x_{k})=\varPhi ^{*}.\) Furthermore, we have \(\lim _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\)
(iii) By (29), we have
Since f is uniformly contionuous on any bounded set and \(\nabla g\) is uniformly continuous on bounded sets, (31) implies
Hence, by Proposition 4(i) and (26), we have \(\lim _{n\rightarrow \infty }\varPhi (x_{n})=\varPhi ^{*}.\) \(\square \)
Proposition 6
Let \(\{x_{n}\}\)and \(\{y_{n}\}\) be sequences generated by Iterative Method 4.1. Suppose that the sequence \(\{x_{n}\}\) is bounded and there exists \(\bar{t}>0\) such that \(t_{n}\ge \bar{t}\) for all \(n\in \mathbf {N}.\) Then, \(\varPhi (x_{n})-\varPhi ^{*}\le \lambda n^{1-p}\) for some \(\lambda >0.\)
Proof
By (26) and Proposition 4, we have
Since \(\{x_{n}\}\) is bounded, there exist \(c_{1}\ge 0\) such that
Hence,
Since \(\{\varPhi (x_{n})-\varPhi ^{*}\}\) is bounded by Proposition 4(iii), there exist \(c_{2}\ge 0\) such that
Then, by (32) and (33), we have
Using (34), we get that
and so that,
By the mean value theorem, we have
with \(\varPhi (x_{n+1})-\varPhi ^{*}\le \xi \le \varPhi (x_{n})-\varPhi ^{*} \) and \(\frac{1}{q}+\frac{1}{p}=1.\) Thus,
and, by (35),
where, \(\bar{c}=\left( \frac{p-1}{pc_{2}}\right) ^{\frac{p}{p-1}}.\) Summing up then yields
and consequently,
Hence, there exists \(\lambda >0,\) such that \(\varPhi (x_{n})-\varPhi ^{*}\le \lambda n^{1-p}.\) \(\square \)
Definition 3
[17] We say that the sequence of iterates generated by Iterative Method 4.1 satisfies the error bound property, if there exists \(\kappa >0\) such that
Proposition 7
Let \(\{x_{n}\}\) and \(\{y_{n}\}\) be sequences generated by Iterative Method 4.1. Assume that the error bound property (36) holds for \(\{x_{n}\}\) and the sequence \(\{x_{n}\}\) is bounded. If there exists \(\bar{t}>0\) such that \(t_{n}\ge \bar{t}\) for all \(n\in \mathbf {N},\) then the sequence \(\{\varPhi (x_{n})\}\) converges \(Q-\)linearly, that is, there exists \(0<\epsilon <1\) such that
Proof
Since \(\mathcal {S}\) is nonempty, closed and convex and X is reflexive, there exists \(\hat{x}_{n}\in \mathcal {S},\) such that \(\Vert x_{n}-\hat{x}_{n}\Vert =\min _{y\in \mathcal {S}}\Vert x_{n}-y\Vert \) and \(\varPhi (\hat{x}_{n})=\varPhi ^{*}.\) Since \(\{x_{n}\}\) is bounded, \(\{\hat{x}_{n}\}\) is also bounded. Since
and
we have that
Then, by (22) and (37), we have
By (38), we have
Now we use the error bound condition \(\min _{y\in \mathcal {S}}\Vert x_{n}-y\Vert \le \kappa \Vert x_{n}-y_{n}\Vert \) together with Proposition 4 to obtain
It follows from (39) that
where, \(0<\epsilon =\left( 1-\frac{\bar{t}(p-1)}{(2+\kappa )p}\right) <1.\) Hence, the sequence \(\{\varPhi (x_{n})\}\) converges \(Q-\)linearly. \(\square \)
Corollary 1
Let \(\{x_{n}\}\) and \(\{y_{n}\}\) be sequences generated by Iterative Method 4.1. Assume that the error bound property (36) holds for \(\{x_{n}\}\) and the sequence \(\{x_{n}\}\) is bounded. If f is totally convex and there exists \(\bar{t}>0\) such that \(t_{n}\ge \bar{t}\) for all \(n\in \mathbf {N},\) then \(\{x_{n}\}\) converges \(R-\)linearly to the unique minimizer \(\bar{x}.\)
Proof
Consider the following Bregman-like distance to the solution \(\bar{x}\) of the problem (1):
which is non-negative since \(-\nabla g(\bar{x})\in \partial f(\bar{x}).\) Note that if \( \partial f(\bar{x})\) consists of one point, R is indeed the Bregman distance. By optimality of \(\bar{x}\) and by Proposition 7, the iterates \(x_{n}\) satisfy
Hence, by Definition 2, \(x_{n}\rightarrow \bar{x}.\)
On the other hand, If f is totally convex, then \(\mathcal {S}=\{\bar{x}\}\) and
Using the error bound condition (36), we have
Then, by Proposition 4 and \(\varPhi (x_{n})-\varPhi (\bar{x})\ge \varPhi (x_{n})-\varPhi (x_{n+1})\), we have \(\{x_{n}\}\) is bounded and
and consequently
where, \(\mu =\frac{(p-1)\bar{t}}{p\kappa ^{p}}.\) Since the sequence \(\{\varPhi (x_{n})\}\) is converges \(Q-\)linearly by Proposition 7, that is, \(\varPhi (x_{n+1})-\varPhi ^{*}\le \epsilon (\varPhi (x_{n})-\varPhi ^{*}),\) then we have
Hence, the sequence \(\left\{ \left( \frac{\varPhi (x_{n})-\varPhi (\bar{x})}{\mu }\right) ^\frac{1}{p}\right\} \) is also converges \(Q-\)linearly. Thus, by (40), \(\{x_{n}\}\) converges \(R-\)linearly to an optimal solution in \(\mathcal {S}.\) \(\square \)
5 Conclusion
In this work, we discuss the modified forward–backward splitting method involving new linesearches for solving minimization problems of two convex functions in Banach space. Our algorithms do not require the Lipschitz constant of the gradient of functions. We proved the weak convergence of the iterative sequence generated by these methods, and further proved convergence with asymptotic rate \(\frac{1}{n}\) to the optimal value under the assumption of the boundedness of the iterative sequence.
References
Albert, Y.: Decomposition theorem in Banach spaces. Field Inst. Commun. 25, 77–93 (2000)
Albert, Y., Ryazantseva, I.: Nonlinear Ill-Posed Problems of Monotone Type. Springer, New York (2006)
Attouch, H., Czarnecki, M.O., Peypouquet, J.: Coupling forward–backward with penalty schemes and parallel splitting for constrained variational inequalities. SIAM J. Optim. 21(4), 1251–1274 (2011)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)
Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first order methods revisited and applications. Math. Oper. Res. 42, 330–348 (2016)
Beck, A., Teboulle, M.: Gradient-based algorithms with applications to signal recovery problems. In: Palomar, D., Eldar, Y. (eds.) Convex Optimization in Signal Processing and Communications, pp. 42–88. University Press, Cambridge (2010)
Bello Cruz, J.Y., Nghia, T.T.: On the convergence of the forward–backward splitting method with linesearches. Optim. Method Softw. 7, 1–30 (2016)
Bolte, J., Sabach, S., Teboulle, M., Vaisbourd, Y.: First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28, 2131–2151 (2018)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
Bredies, K.: A forward–backward splitting algorithm for the minimization of nonsmooth convex functionals in Banach space. Inverse Probl. 25, 015005 (2009)
Cioranescu, I.: Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems. Mathematics and Its Applications, vol. 62. Kluwer Academic Publishers, Dordrecht, The Netherlands (1990)
Combettes, P.L.: Inconsistent signal feasibility problems: least-squares solutions in a product space. IEEE Trans. Signal Process. 42, 2955–2966 (1994)
Combettes, P.L., Dũng, D., Vũ, B.C.: Dualization of signal recovery problems. Set-Valued Anal. 18, 373–404 (2010)
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward–backward splitting. Multiscale Model. Simul. 4, 1168–1200 (2005)
Combettes, P.L., Pesquet, J.C.: A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1, 564–574 (2007)
Guan, W.B., Song, W.: The generalized forward–backward splitting method for the minimization of the sum of two functions in Banach spaces. Numer. Funct. Anal. Optim. 7, 867–886 (2015)
Guan, W.B., Song, W.: The forward–backward splitting method and its convergence rate for the minimization of the sum of two functions in Banach space. Optim. Lett. 2, 1–24 (2020)
Kankam, K., Pholasa, N., Cholamjiak, P.: Hybrid forward–backward algorithms using linesearch rule for minimization problem. Thai J. Math. 17(3), 607–625 (2019)
Kankam, K., Pholasa, N., Cholamjiak, P.: On convergence and complexity of the modified forward–backward method involving new linesearches for convex minimization. Math. Meth. Appl. Sci. 42(5), 1352–1362 (2019)
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
salzo, S.: The variable metric forward–backward splitting algorithm under mild differentiability assumptions. SIAM J. Optim. 4, 2153–2181 (2017)
Suantai, S., Noor, M.A., Kankam, K., Cholamjiak, P.: Novel forward–backward algorithms for optimization and applications to compressive sensing and image inpainting. Adv. Differ. Equ-ny. 2021, 265 (2021)
Takahashi, W.: Convex Analysis and Approximation of Fixed Points. Mathematical Analysis Series, vol. 2. Yokohama Publishers, Yokohama, Japan (2000)
Acknowledgements
The work was supported by PHD research startup foundation of Harbin Normal University(No. XKB201804) and the National Natural Sciences Grant(No. 11871182)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Guan, WB., Song, W. The forward–backward splitting method for non-Lipschitz continuous minimization problems in Banach spaces. Optim Lett 16, 2435–2456 (2022). https://doi.org/10.1007/s11590-021-01840-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-021-01840-y