Xinyi Zhu, Zidan Wang^*
Key Laboratory of Optimization Theory and Applications, School of Mathematical Sciences, China West Normal University, Nanchong, China.
DOI: 10.4236/jamp.2026.144074   PDF    HTML   XML   35 Downloads   202 Views   Citations

Abstract

We revisit the Backward-Douglas-Rachford algorithm proposed by Pham et al. for solving generalized DC programming problems composed of differentiable, lower semicontinuous, and convex functions. By employing the convergence analysis framework of Themelis et al., based on the lower bound of smooth functions, and under the same standard assumptions and conditions, we recharacterize the range of the step size. Compared with the result of Pham et al., we obtain a larger step size range and simplify its expression. Moreover, under this step size condition, we prove that the sequence generated by the algorithm possesses subsequential convergence.

Keywords

Backward-Douglas-Rachford Splitting Method, DC Programming, Nonconvex Optimization, Step Size Result

Share and Cite:

1. Introduction

We consider the following problem

$\underset{x\in {ℝ}^n}{\text{min}}F\left(x\right):=f\left(x\right)+h\left(x\right)-g\left(x\right),$ (1)

where $f:{ℝ}^n\to ℝ$ is a differentiable function with a Lipschitz continuous gradient, $h:{ℝ}^n\to \left(-\infty ,+\infty \right]$ is a lower semicontinuous function, and $g:{ℝ}^n\to ℝ$ is a continuously convex function. When all functions in (1) are convex, the problem is referred to as a generalized difference-of-convex (DC) programming [1]. In particular, when $f=0$ , problem (1) reduces to the standard DC programming [2].

The classical algorithm for DC programming is the difference-of-convex algorithm [3] and its variants [4]. The alternating direction method of multipliers has also been employed to address DC programming [5]. The Douglas-Rachford splitting method (DRSM) constitutes another powerful approach for DC programming. In particular, Chuang et al. [1] proposed a unified DR splitting framework for solving generalized DC programming problems of the form (1), but its convergence analysis relies on the strict assumption of strong convexity and fails to cover the applicability of the classical DRSM. More recently, Pham et al. [6] introduced a Backward Douglas-Rachford splitting method (BDRSM), which studies problem (1) under weaker assumptions than those imposed in earlier works. The algorithm only requires that $g$ in problem (1) be convex, without assuming its differentiability, and does not require the convexity of $f$ or $h$ , thus having a broader range of applicability.

DRSM was originally proposed by Douglas and Rachford [7] in 1956 to compute numerical solutions of the heat differential equation. After its extension to the monotone operator setting by Lions and Mercier [8], the DRSM has been extensively studied in convex optimization.

In recent years, the application of the DRSM to the following nonconvex optimization problem

$\underset{x}{\text{min}}f\left(x\right)+g\left(x\right),$ (2)

has attracted considerable attention; see, for example [9]-[13]. Here, $f:{ℝ}^n\to ℝ$ is a differentiable function and $g:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ a proper lower semicontinuous function. By introducing the Douglas-Rachford envelope (DRE) function and utilizing the Kurdyka–Łojasiewicz (KL) inequality [14] [15], Li and Pong [9] established the full sequence convergence for the DRSM in a nonconvex setting for (2). Full sequence convergence is achieved as long as the following condition holds

$\gamma <\frac{-\left(2.5l+2L\right)+\sqrt{{\left(2.5l+2L\right)}^2+2L^2}}{2L^2},$

where $L$ is the Lipschitz constant, $l\in ℝ$ is such that $f+\frac{l}{2}{\Vert \cdot \Vert }^2$ is convex. More recently, Themelis et al. [10] conducted a refined and compact analysis of the sufficient descent property of DRSM using lower bounds for smooth functions, extending the range of the relaxation parameter to (0, 2). Within this parameter range, they obtained a broader step size condition $\gamma <\frac{1}{L}$ compared to that of Li and Pong. Meanwhile, they unified the convergence analysis framework for the alternating direction method of multipliers and DRSM. For the generalized DC programming (1), Pham et al. [6] proposed BDRSM. The iteration of BDRSM is as follows

Algorithm 1. Backward-Douglas-Rachford splitting method (BDRSM).

Step 1. Choose initial points $y_0,z_0,w_0\in {ℝ}^n$ and set $n=0$ . Let $\gamma >0,\tau \ge 0$ , and $\nu \in \left(0,2\right)$ . Step 2. Compute $x_{n+1}\in \underset{x\in {ℝ}^n}{\arg \min }\left\{f\left(x\right)+\frac{1}{2\gamma }{\Vert x-y_n\Vert }^2\right\},$ $w_{n+1}=\underset{w\in {ℝ}^n}{\arg \min }\left\{g^{*}\left(w\right)-\langle w,z_n\rangle +\frac{\tau }{2}{\Vert w-w_n\Vert }^2\right\},$ $z_{n+1}\in \underset{z\in {ℝ}^n}{\arg \min }\left\{h\left(z\right)+\frac{1}{2\gamma }{\Vert z-\left(2x_{n+1}-y_n+\gamma w_{n+1}\right)\Vert }^2\right\},$ $y_{n+1}=y_n+\nu \left(z_{n+1}-x_{n+1}\right).$ Step 3. If a termination criterion does not hold, set $n=n+1$ and go to Step 2.

Note that, when $g=0$ , BDRSM reduces to the relaxed DRSM; If we further set $\nu =1$ , it coincides with the classical DRSM. Compared with existing works [1] [16], the convergence analysis in [6] relies on weaker assumptions, it only requires $g$ to be convex. Under mild conditions, Pham et al. [6] established the global convergence of the full sequence of iterates and derived corresponding convergence rate results, when $\gamma$ satisfies the following inequality

$\gamma <\frac{-\nu {\rho }_f+\sqrt{{\nu }^2{\rho }_f^2+8\left(2-\nu \right)L_f^2}}{4L_f^2},$ (3)

where $L_f$ is the gradient Lipschitz constant, ${\rho }_f$ is the weak convexity constant. In view of this, motivated by the work of [9] [10], under the same original assumptions, we utilize the lower bounds of smooth functions to recharacterize the parameter selection range for the iterative step size, and obtain a step size that has a larger range and a more concise expression compared to (3).

The remainder of this paper is structured as follows. In Section 2, we present the necessary preliminaries required throughout this section. In Section 3, through a more refined analysis utilizing lower bounds for smooth functions, we obtain a step size that has a larger range and a more concise expression. Based on this, by constructing a Lyapunov function, we proved the subsequential convergence. In Section 4, the research work and results of this paper are systematically summarized, and possible future research directions are discussed.

Remark 1 (Existence of solutions to subproblems). According to the setup of Pham et al. [6], the three minimization subproblems in the above iteration admit solutions under the following conditions. Since $f$ is $L_f$ -smooth and $\frac{1}{2\gamma }{\Vert x-y_n\Vert }^2$ is strongly convex, the $x$ -subproblem admits a unique solution. Since $g$ is a continuous convex function, its conjugate $g^{*}$ is convex and lower semicontinuous; together with the term $\frac{\tau }{2}{\Vert w-w_n\Vert }^2$ , the $w$ -subproblem is strongly convex and coercive, hence admits a unique solution. For the $z$ -subproblem, $h$ is lower semicontinuous and assumed to be prox-friendly (i.e., its proximal operator can be computed efficiently), so that the subproblem is solvable.

2. Preliminaries

In this section, we introduce the basic concepts and several important lemmas and theorems. First, the meanings of some special symbols commonly used in the text are provided.

Let ${ℝ}_{+}$ denote the set of nonnegative real numbers and ${ℝ}_{++}$ the set of positive real numbers. Let ${ℝ}^n$ denote the $n$ -dimensional Euclidean space, equipped with the inner product $\langle \cdot ,\cdot \rangle$ , and the induced Euclidean norm $\Vert \cdot \Vert$ .

Consider a function $f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ . The domain of $f$ is defined as $\text{dom}\left(f\right):=\left\{x\in {ℝ}^n:f\left(x\right)<+\infty \right\}$ . The function $f$ is called proper if $\text{dom}\left(f\right)\ne \varnothing$ and it does not take the value $-\infty$ . It is said to be coercive if $f\left(x\right)\to +\infty$ as $\Vert x\Vert \to +\infty$ . The epigraph of $f$ is defined by $\text{epi}\left(f\right):=\left\{\left(x,\rho \right)\in {ℝ}^n\times ℝ:f\left(x\right)\le \rho \right\}$ . The function $f$ is called lower semicontinuous if its epigraph $\text{epi}\left(f\right)$ is a closed set.

Let $f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ be a proper function. Suppose $x\in \text{dom}\left(f\right)$ . The subdifferential of $f$ at $x$ is defined by

$\widehat{\partial }f\left(x\right):=\left\{x^{*}\in {ℝ}^n:\underset{y\to x}{\lim \inf }\frac{f\left(y\right)-f\left(x\right)-\langle x^{*},y-x\rangle }{\Vert y-x\Vert }\ge 0\right\}$

and the limiting subdifferential of $f$ at $x$ is defined by

$\partial f\left(x\right):=\left\{x^{\text{*}}\in {ℝ}^n:\exists x_n\stackrel{f}{\to }x,x_n^{\text{*}}\to x^{\text{*}}\text{with}{x}_n^{\text{*}}\in \widehat{\partial }f\left(x_n\right)\right\},$

where the notation $y\stackrel{f}{\to }x$ means that $y\to x$ with $f\left(y\right)\to f\left(x\right)$ . When $x\notin \text{dom}\left(f\right)$ , both the subdifferential and the limiting subdifferential of $f$ at $x$ are defined to be empty. It follows directly from the definition that the limiting subdifferential satisfies the robustness property

$\partial f\left(x\right)=\left\{x^{\text{*}}\in {ℝ}^n:\exists y_n\stackrel{f}{\to }x,y_n^{\text{*}}\to x^{\text{*}}\text{with}{y}_n^{\text{*}}\in \partial f\left(y_n\right)\right\}.$

The domain of the subdifferential $\partial f$ is defined as

$\text{dom}\partial f:=\left\{x\in {ℝ}^n:\partial f\left(x\right)\ne \varnothing \right\}.$

Let a function $f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ , the Fenchel conjugate of $f$ is denoted by $f^{\text{*}}:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ , is defined as

$f^{\text{*}}\left(v\right)=\underset{x\in {ℝ}^n}{\text{sup}}\left\{\langle v,x\rangle -f\left(x\right)\right\}.$

The following proposition presents key properties of the Fenchel conjugate.

Proposition 1. [6] Let $f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ be a proper function and let $x,v\in {ℝ}^n$ . Then, the following assertions hold:

(i) $f^{\text{*}}$ is a proper lower semicontinuous and convex function, then it holds:

$f\left(x\right)+f^{\text{*}}\left(v\right)\ge \langle x,v\rangle .$

(ii) If $f$ is a lower semicontinuous and convex, then the following statements are equivalent:

$v\in \partial f\left(x\right)\iff f\left(x\right)+f^{\text{*}}\left(v\right)=\langle x,v\rangle \iff x\in \partial f^{\text{*}}\left(v\right).$

Next, we recall the definition of the Kurdyka-Łojasiewicz (KL) property, which will play a central role in our subsequent analysis.

Next, we will introduce the concepts of $L_f$ -smooth.

Definition 1. [17] Let $f:{ℝ}^n\to ℝ$ be a differentiable function, if its gradient $\nabla f$ is $L_f$ -Lipschitz continuous, there exists constant $L_f>0$ ,

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L_f\Vert x-y\Vert \text{for}\text{all}x,y\in {ℝ}^n,$

then the function $f$ is said to be $L_f$ -smooth.

The following descent lemma provides a useful tool for convergence analysis.

Definition 2. [17] Let $f:{ℝ}^n\to ℝ$ be a function. If there exists a constant ${\rho }_f\in \left[-L_f,L_f\right]$ such that

$f+\frac{{\rho }_f}{2}{\Vert x-y\Vert }^2$

is convex, then $f$ is said to be ${\rho }_f$ -hypoconvex convex.

An equivalent characterization of this property for differentiable functions is given below.

Lemma 1. [17] Let $f:{ℝ}^n\to ℝ$ be an $L_f$ -smooth function, where $L_f\ge 0$ , for any $x,y\in {ℝ}^n$ , we have

$\left|f\left(y\right)-f\left(x\right)-\langle \nabla f\left(x\right),y-x\rangle \right|\le \frac{L_f}{2}{\Vert y-x\Vert }^2.$

Theorem 2. [17] A continuously differentiable function $f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ is ${\rho }_f$ -weakly convex if and only if for all $x,y\in {ℝ}^n$ , the following inequality holds:

$f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle -\frac{{\rho }_f}{2}{\Vert x-y\Vert }^2.$

For $L_f$ -smooth and ${\rho }_f$ -weakly convex function, we have the following property.

Theorem 3. [10] Let $f:{ℝ}^n\to ℝ$ be a $L_f$ -smooth and ${\rho }_f$ -weakly convex function. Then, for all $x,y\in {ℝ}^n$ , it holds that

$\begin{array}{c}f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{1}{2\left(L_f-{\rho }_f\right)}{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2\\ -\frac{{\rho }_f{L}_f}{2\left(L_f-{\rho }_f\right)}{\Vert x-y\Vert }^2,\end{array}$

where ${\rho }_f\in \left[0,L_f\right)$ .

Moreover, the above inequality is also valid if $L_f$ is replaced with any $L\ge L_f$ and ${\rho }_f$ with any $\rho \in \left[{\rho }_f,L\right)$ .

Theorem 4. [17] Let $f:{ℝ}^n\to ℝ$ be a $L_f$ -smooth and convex function. Then, for all $x,y\in {ℝ}^n$ , it holds that

$f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{1}{2L_f}{\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert }^2.$

Remark 2. (Scaling of Smoothness and Hypoconvex Constants). The following scaling properties are crucial for our subsequent analysis.

Smoothness If $f$ is $L_f$ -smooth, then it is also $L$ -smooth for any $L\ge L_f$ . Indeed, for any $x,y$ , the inequality

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L_f\Vert x-y\Vert \le L\Vert x-y\Vert ,$

which satisfies the definition of $L$ -smoothness, hence $f$ is $L$ -smooth.

Hypoconvexity If $f$ is ${\rho }_f$ -weakly convex with ${\rho }_f>0$ . Then it is also $\rho$ -weakly convex for any $\rho \ge {\rho }_f$ , To see this, note that $-\frac{{\rho }_f}{2}{\Vert x-y\Vert }^2\ge -\frac{\rho }{2}{\Vert x-y\Vert }^2$ . Substituting this into the inequality below yields

$\begin{array}{c}f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle -\frac{{\rho }_f}{2}{\Vert x-y\Vert }^2\\ \ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle -\frac{\rho }{2}{\Vert x-y\Vert }^2,\end{array}$

which satisfies the definition of $\rho$ -weakly convexity. Therefore, $f$ is $\rho$ -weakly convex. If $f$ is ${\rho }_f$ -strongly convex with ${\rho }_f<0$ , a similar argument shows it is $\rho$ -strongly convex for any $\rho \le {\rho }_f$ .

In summary, if $f$ is an $L_f$ -smooth and ${\rho }_f$ -hypoconvex function, then it is also $L$ -smooth and $\rho$ -hypoconvex. In the Section 3, we will frequently use these properties. Specifically, we will appropriately inflate the constants $L$ and $\rho$ to meet the specific conditions required for applying certain inequalities or to simplify the derivation of step-size rules.

3. Step Size Result and Convergence Analysis

This section focuses on the Backward-Douglas-Rachford splitting method (BDRSM) proposed by Pham et al. [6], primarily characterizing the range of the iterative step size parameter and analyzing the convergence of subsequences. Inspired by the work of Themelis et al. [10], we utilize the lower bounds of smooth functions to prove the sufficient descent property of the Lyapunov function and conduct a piecewise refined analysis of the descent constant, thereby obtaining a larger step size range. Under this condition, we prove the convergence of the subsequences generated by the algorithm.

Assumption 1. [6]

(i) $f:{ℝ}^n\to ℝ$ is differentiable ${\rho }_f$ -hypoconvex function with an $L_f$ -Lipschitz continuous gradient, where ${\rho }_f\in \left[-L_f,L_f\right]$ .

(ii) $g:{ℝ}^n\to ℝ$ is a continuous and convex function.

(iii) $h:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ is a lower semicontinuous function.

The following lemma will be utilized in the analysis.

Lemma 5. [6] Suppose that $f$ is differentiable with $L_f$ -Lipschitz continuous

gradient. Let ${\left\{\left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ be a sequence generated by Algorithm 1.

Then, for all $n\in {\mathbb{N}}^{\text{*}}$ , the following hold

(i) $y_n=x_{n+1}+\gamma \nabla f\left(x_{n+1}\right)$ .

(ii) $z_n\in \partial g^{\text{*}}\left(w_{n+1}\right)+\tau \left(w_{n+1}-w_n\right)$ .

(iii) $w_{n+1}\in \partial h\left(z_{n+1}\right)-\frac{1}{\gamma }\left(x_{n+1}-z_{n+1}\right)-\frac{1}{\gamma }\left(x_{n+1}-y_n\right)$ .

(iv) $\Vert y_{n+1}-y_n\Vert \le \left(1+\gamma L_f\right)\Vert x_{n+2}-x_{n+1}\Vert$ .

(v) $\Vert z_{n+2}-z_{n+1}\Vert \le \left(\frac{1+\gamma L_f}{\nu }\right)\Vert x_{n+3}-x_{n+2}\Vert +\left(1+\frac{1+\gamma L_f}{\nu }\right)\Vert x_{n+2}-x_{n+1}\Vert$ .

The convergence analysis for the problem (1) is based on the following Lyapunov function [6].

$\begin{array}{c}\Phi \left(x,y,z,w\right):=f\left(x\right)+h\left(z\right)+g^{*}\left(w\right)-\langle w,z\rangle \\ +\frac{1}{2\gamma }{\Vert x-y\Vert }^2-\frac{1}{2\gamma }{\Vert y-z\Vert }^2+\frac{1-\nu }{\gamma }{\Vert x-z\Vert }^2.\end{array}$ (4)

Let $a=x-y,b=x-z$ . Using the identity $2\langle a,b\rangle ={\Vert a\Vert }^2+{\Vert b\Vert }^2-{\Vert a-b\Vert }^2$ , we obtain

$\begin{array}{l}\frac{1}{2\gamma }{\Vert x-y\Vert }^2-\frac{1}{2\gamma }{\Vert y-z\Vert }^2+\frac{1-\nu }{\gamma }{\Vert x-z\Vert }^2-\langle w,z\rangle \\ =\frac{1}{2\gamma }\left({\Vert x-y\Vert }^2-{\Vert y-z\Vert }^2+{\Vert x-z\Vert }^2+{\Vert x-z\Vert }^2\right)\\ -\frac{\nu }{\gamma }{\Vert x-z\Vert }^2+\langle x-z-x,w\rangle \\ =\frac{1}{\gamma }\langle x-z,x-y\rangle +\frac{1}{2\gamma }{\Vert x-z\Vert }^2-\frac{\nu }{\gamma }{\Vert x-z\Vert }^2+\langle x-z,w\rangle -\langle x,w\rangle \\ =\frac{1}{\gamma }\langle x-z,x-y+\gamma w\rangle +\frac{1}{2\gamma }{\Vert x-z\Vert }^2-\frac{\nu }{\gamma }{\Vert x-z\Vert }^2-\langle x,w\rangle \\ =\frac{1}{2\gamma }{\Vert \left(x-z\right)+\left(x-y+\gamma w\right)\Vert }^2-\frac{1}{2\gamma }{\Vert x-y+\gamma w\Vert }^2-\frac{\nu }{\gamma }{\Vert x-z\Vert }^2-\langle x,w\rangle \\ =\frac{1}{2\gamma }{\Vert 2x-y-z+\gamma w\Vert }^2-\frac{1}{2\gamma }{\Vert x-y+\gamma w\Vert }^2-\frac{\nu }{\gamma }{\Vert x-z\Vert }^2-\langle x,w\rangle .\end{array}$

Therefore, (4) can also be written as

$\begin{array}{c}\Phi \left(x,y,z,w\right):=f\left(x\right)+h\left(z\right)+g^{*}\left(w\right)-\langle x,w\rangle \\ +\frac{1}{2\gamma }{\Vert 2x-y-z+\gamma w\Vert }^2-\frac{1}{2\gamma }{\Vert x-y+\gamma w\Vert }^2-\frac{\nu }{\gamma }{\Vert x-z\Vert }^2.\end{array}$ (5)

Next, we revisit the step size condition $\gamma$ established by Pham et al., with the aim of obtaining a step size that has a more concise expression and a larger range, while ensuring that subsequent convergence still holds under this step size condition. We first establish the sufficient descent property.

Theorem 6 (sufficient descent). Suppose that Assumption 1 hold, then stepsize $\gamma$ satisfies

$\gamma <\text{min}\left\{\frac{1}{L_f},\frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}}\right\},$

where, ${\left[{\rho }_f\right]}_{+}=\max \left\{{\rho }_f,0\right\}$ .

Let ${\left\{\left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ be a sequence generated by Algorithm 1. Then the following hold:

For all $n\in {\mathbb{N}}^{\text{*}}$ ,

$\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\ge \frac{\delta }{2}{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2.$

$\frac{\delta }{2}=\frac{2-\nu }{2\nu \gamma }+\{\begin{array}{ll}\text{min}\left\{\frac{-{\rho }_f{L}_f}{2\left(L_f-{\rho }_f\right)},\frac{L_f}{2}-\frac{\gamma L_f^2}{\nu }\right\}\hfill & 0<\nu <2\left(1-\frac{{\rho }_f}{L_f}\right),\hfill \\ -\frac{{\rho }_f}{\nu }\hfill & 2\left(1-\frac{{\rho }_f}{L_f}\right)\le \nu <2.\hfill \end{array}$

Then the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\mathbb{A}}}$ is nonincreasing.

Proof. (i) When $\nu \in \left(0,2\right)$ , we choose $L\ge L_f$ , $\rho \in {ℝ}_{+}$ . By Theorem 3, the following inequality holds

$\begin{array}{l}f\left(x_n\right)-f\left(x_{n+1}\right)\\ \ge \langle \nabla f\left(x_{n+1}\right),x_n-x_{n+1}\rangle +\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2\\ -\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_{n+1}-x_n\Vert }^2.\end{array}$

Combining the above inequality with (4), we obtain

$\begin{array}{l}\Phi \left(x_{n+1},y_n,z_n,w_{n+1}\right)-\Phi \left(x_n,y_n,z_n,w_{n+1}\right)\\ =f\left(x_{n+1}\right)-f\left(x_n\right)+\frac{1}{2\gamma }{\Vert x_{n+1}-y_n\Vert }^2-\frac{1}{2\gamma }{\Vert x_n-y_n\Vert }^2\\ +\frac{1-\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2-\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2\\ \le \langle \nabla f\left(x_{n+1}\right),x_{n+1}-x_n\rangle -\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2\\ +\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2+\frac{1}{2\gamma }{\Vert x_{n+1}-y_n\Vert }^2-\frac{1}{2\gamma }{\Vert x_n-y_n\Vert }^2\\ +\frac{1-\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2-\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2\end{array}$

$\begin{array}{l}=\frac{1}{2\gamma }{\Vert x_{n+1}-x_n\Vert }^2+\frac{1}{\gamma }\langle x_{n+1}-x_n,x_n-y_n\rangle +\langle \nabla f\left(x_{n+1}\right),x_{n+1}-x_n\rangle \\ -\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2+\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2\\ +\frac{1-\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2-\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2\\ =\frac{1}{\gamma }\langle x_{n+1}-x_n,x_{n+1}-y_n\rangle -\frac{1}{2\gamma }{\Vert x_{n+1}-x_n\Vert }^2+\langle \nabla f\left(x_{n+1}\right),x_{n+1}-x_n\rangle \\ -\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2+\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2\\ +\frac{1-\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2-\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2.\end{array}$

From Lemma 5(i), we derive the following equality

$0=\nabla f\left(x_{n+1}\right)+\frac{1}{\gamma }\left(x_{n+1}-y_n\right).$ (6)

Using equality (6), we obtain that

$\begin{array}{l}\Phi \left(x_{n+1},y_n,z_n,w_{n+1}\right)-\Phi \left(x_n,y_n,z_n,w_{n+1}\right)\\ \le -\frac{1}{2\gamma }{\Vert x_{n+1}-x_n\Vert }^2-\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2\\ +\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2+\frac{1-\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2-\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2.\end{array}$ (7)

Now, from the Lyapunov function (4), we have

$\begin{array}{l}\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)-\Phi \left(x_{n+1},y_n,z_{n+1},w_{n+1}\right)\\ =\frac{1}{2\gamma }{\Vert x_{n+1}-y_{n+1}\Vert }^2-\frac{1}{2\gamma }{\Vert y_{n+1}-z_{n+1}\Vert }^2-\frac{1}{2\gamma }{\Vert x_{n+1}-y_n\Vert }^2+\frac{1}{2\gamma }{\Vert y_n-z_{n+1}\Vert }^2.\end{array}$

It is well known that

$\begin{array}{l}\langle a-b,c-d\rangle \\ =\langle a,c\rangle -\langle a,d\rangle -\langle b,c\rangle +\langle b,d\rangle \\ =\frac{1}{2}\left({\Vert a\Vert }^2+{\Vert c\Vert }^2-{\Vert a-c\Vert }^2\right)-\frac{1}{2}\left({\Vert a\Vert }^2+{\Vert d\Vert }^2-{\Vert a-d\Vert }^2\right)\\ -\frac{1}{2}\left({\Vert b\Vert }^2+{\Vert c\Vert }^2-{\Vert b-c\Vert }^2\right)+\frac{1}{2}\left({\Vert b\Vert }^2+{\Vert d\Vert }^2-{\Vert b-d\Vert }^2\right)\\ =\frac{1}{2}{\Vert a-d\Vert }^2-\frac{1}{2}{\Vert a-c\Vert }^2-\frac{1}{2}{\Vert b-d\Vert }^2+\frac{1}{2}{\Vert b-c\Vert }^2,\end{array}$

let $a=x_{n+1},b=z_{n+1},c=y_n,d=y_{n+1}$ , then we have

$\begin{array}{l}\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)-\Phi \left(x_{n+1},y_n,z_{n+1},w_{n+1}\right)\\ =\frac{1}{\gamma }\langle x_{n+1}-z_{n+1},y_n-y_{n+1}\rangle \\ =\frac{\nu }{\gamma }{\Vert x_{n+1}-z_{n+1}\Vert }^2,\end{array}$ (8)

where the second equality is got from the updating step of $y_{n+1}$ in Algorithm 1. Next, from the definition of $w_{n+1}$ in Algorithm 1, we know that

$\begin{array}{l}{g}^{\text{*}}\left(w_{n+1}\right)-\langle w_{n+1},z_n\rangle +\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2\\ \le g^{\text{*}}\left(w_n\right)-\langle w_n,z_n\rangle +\frac{\tau }{2}{\Vert w_n-w_n\Vert }^2.\end{array}$

Rearranging the above inequality, we get

$g^{\text{*}}\left(w_{n+1}\right)-g^{\text{*}}\left(w_n\right)+\langle w_n-w_{n+1},z_n\rangle \le -\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2.$

It means that

$\begin{array}{l}\Phi \left(x_n,y_n,z_n,w_{n+1}\right)-\Phi \left(x_n,y_n,z_n,w_n\right)\\ =g^{*}\left(w_{n+1}\right)-g^{*}\left(w_n\right)-\langle w_{n+1},z_n\rangle +\langle w_n,z_n\rangle \\ \le -\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2.\end{array}$ (9)

Subsequently, we construct the relationship of Φ regarding to $z_n$ and $z_{n+1}$ from (5), that is

$\begin{array}{l}\Phi \left(x_{n+1},y_n,z_{n+1},w_{n+1}\right)-\Phi \left(x_{n+1},y_n,z_n,w_{n+1}\right)\\ =h\left(z_{n+1}\right)+\frac{1}{2\gamma }{\Vert 2x_{n+1}-y_n+\gamma w_{n+1}-z_{n+1}\Vert }^2-\frac{\nu }{\gamma }{\Vert x_{n+1}-z_{n+1}\Vert }^2\\ -h\left(z_n\right)-\frac{1}{2\gamma }{\Vert 2x_{n+1}-y_n+\gamma w_{n+1}-z_n\Vert }^2+\frac{\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2.\end{array}$

However, by the definition of $z_{n+1}$ in Algorithm 1, it yields that

$\begin{array}{l}\Phi \left(x_{n+1},y_n,z_{n+1},w_{n+1}\right)-\Phi \left(x_{n+1},y_n,z_n,w_{n+1}\right)\\ \le -\frac{\nu }{\gamma }{\Vert x_{n+1}-z_{n+1}\Vert }^2+\frac{\nu }{\gamma }{\Vert x_{n+1}-z_n\Vert }^2.\end{array}$ (10)

Combining (7), (8), (9) and (10), we obtain

$\begin{array}{l}\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)-\Phi \left(x_n,y_n,z_n,w_n\right)\\ \le -\frac{1}{2\gamma }{\Vert x_{n+1}-x_n\Vert }^2-\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2\\ +\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2+\frac{1}{\gamma }{\Vert x_{n+1}-z_n\Vert }^2\\ -\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2-\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2\\ =\frac{1}{2\gamma }{\Vert x_{n+1}-x_n\Vert }^2-\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2\\ +\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2+\frac{2}{\gamma }\langle x_{n+1}-x_n,x_n-z_n\rangle \\ +\frac{\nu }{\gamma }{\Vert x_n-z_n\Vert }^2-\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2.\end{array}$ (11)

From the iteration of $y_{n+1}$ in Algorithm 1 and Lemma 5(i), it is not hard to know that

$\nu \left(x_n-z_n\right)=y_{n-1}-y_n=x_n-x_{n+1}+\gamma \left(\nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\right).$

Now, we can rewrite $\frac{\nu }{\gamma }{\Vert x_n-z_n\Vert }^2$ as follows

$\begin{array}{c}\frac{\nu }{\gamma }{\Vert x_n-z_n\Vert }^2=\frac{1}{\gamma \nu }\cdot {\nu }^2{\Vert x_n-z_n\Vert }^2\\ =\frac{1}{\gamma \nu }{\Vert \left(x_n-x_{n+1}\right)+\gamma \left(\nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\right)\Vert }^2\\ =\frac{1}{\gamma \nu }{\Vert x_{n+1}-x_n\Vert }^2+\frac{\gamma }{\nu }{\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2\\ +\frac{2}{\nu }\langle x_{n+1}-x_n,\nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\rangle .\end{array}$ (12)

Additionally, we aslo obtain

$\begin{array}{l}\frac{2}{\gamma }\langle x_{n+1}-x_n,x_n-z_n\rangle \\ =\frac{2}{\gamma }\langle x_{n+1}-x_n,\frac{1}{\nu }\left(x_n-x_{n+1}\right)+\frac{\gamma }{\nu }\left(\nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\right)\rangle \\ =-\frac{2}{\nu \gamma }{\Vert x_{n+1}-x_n\Vert }^2+\frac{2}{\nu }\langle x_{n+1}-x_n,\nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\rangle .\end{array}$ (13)

Substituting (12) and (13) into (11), we have

$\begin{array}{l}\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)-\Phi \left(x_n,y_n,z_n,w_n\right)\\ \le -\frac{1}{2\left(L-\rho \right)}{\Vert \nabla f\left(x_n\right)-\nabla f\left(x_{n+1}\right)\Vert }^2+\frac{\rho L}{2\left(L-\rho \right)}{\Vert x_n-x_{n+1}\Vert }^2\\ -\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2+\left(\frac{1}{2\gamma }-\frac{1}{\nu \gamma }\right){\Vert x_{n+1}-x_n\Vert }^2\\ +\frac{\gamma }{\nu }{\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2\end{array}$ (14)

$\begin{array}{l}\le \left(\frac{1}{2\gamma }-\frac{1}{\nu \gamma }+\frac{\rho L}{2\left(L-\rho \right)}\right){\Vert x_{n+1}-x_n\Vert }^2\\ +\left(\frac{\gamma }{\nu }-\frac{1}{2\left(L-\rho \right)}\right){\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2-\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2,\end{array}$ (15)

If we multiply both sides of inequality (14) by $\frac{1}{L}$ , we obtain

$\begin{array}{l}\frac{1}{L}\left(\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\right)\\ \ge \left(-\frac{1}{2\gamma L}+\frac{1}{\nu \gamma L}-\frac{\rho }{2\left(L-\rho \right)}\right){\Vert x_{n+1}-x_n\Vert }^2\\ -\left(\frac{\gamma }{\nu L}-\frac{1}{2L\left(L-\rho \right)}\right){\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2+\frac{\tau }{2L}{\Vert w_{n+1}-w_n\Vert }^2,\end{array}$ (16)

where $\rho \in \left[0,L\right)$ . Since $f(\cdot )$ is $L_f$ -smooth, we have $\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert \le L_f\Vert x_{n+1}-x_n\Vert$ , (16) can be expressed as follows

$\begin{array}{l}\frac{1}{L}\left(\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\right)\\ \ge \frac{\delta }{2L}{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2L}{\Vert w_{n+1}-w_n\Vert }^2,\end{array}$

where $\delta$ is chosen as

$\frac{\delta }{2L}=\{\begin{array}{ll}-\frac{1}{2\gamma L}+\frac{1}{\nu \gamma L}-\frac{\frac{\rho }{L}}{2\left(1-\frac{\rho }{L}\right)}\hfill & \frac{\gamma }{\nu L}-\frac{1}{2L\left(L-\rho \right)}<0,\hfill \\ -\frac{1}{2\gamma L}+\frac{1}{\nu \gamma L}-\frac{\frac{\rho }{L}}{2\left(1-\frac{\rho }{L}\right)}-\left(\frac{\gamma }{\nu L}-\frac{1}{2L\left(L-\rho \right)}\right)L_f^2\hfill & \text{otherwise}.\hfill \end{array}$ (17)

Now we want to select a suitable $L$ to ensure that the constant $\delta$ is strictly positive. Therefore, we further consider two possibilities based on the size of $\nu$ :

Case 1: If $0<\nu <2\left(1-\frac{\rho }{L_f}\right)$ .

The condition is equivalent to $\frac{\nu L_f}{2\left(L_f-\rho \right)}<1$ , then $\rho <\frac{\left(2-\nu \right)L_f}{2}<L_f$ . Since the parameter $L$ in Theorem 3 can be any number satisfying $L\ge L_f$ . To keep the analysis as simple as possible and avoid unnecessarily conservative bounds, we take $L=L_f$ . Then (17) becomes

$\frac{\delta }{2L_f}=\frac{2-\nu }{2\nu \gamma L_f}+\{\begin{array}{ll}-\frac{\frac{\rho }{L_f}}{2\left(1-\frac{\rho }{L_f}\right)}\hfill & \gamma L_f<\frac{\nu L_f}{2\left(L_f-\rho \right)}\hfill \\ \frac{1}{2}-\frac{\gamma L_f}{\nu }\hfill & \text{otherwise}.\hfill \end{array}$

In this case, we will verify that for any $\gamma$ satisfying $\gamma <\frac{1}{L_f}$ , the constant $\delta$ is strictly positive.

a) If $0<\gamma L_f<\frac{\nu L_f}{2\left(L_f-\rho \right)}<1$ ,

$\begin{array}{c}\frac{\delta }{2L_f}=\frac{2-\nu }{2\nu \gamma L_f}-\frac{\frac{\rho }{L_f}}{2\left(1-\frac{\rho }{L_f}\right)}>\frac{2-\nu }{2\nu }-\frac{\frac{\rho }{L_f}}{2\left(1-\frac{\rho }{L_f}\right)}\\ >\frac{2-\nu }{2\nu }-\frac{\frac{\rho }{L_f}}{\nu }>\frac{1-\frac{\rho }{L_f}}{\nu }-\frac{1}{2}=\frac{2\left(1-\frac{\rho }{L_f}\right)-\nu }{2\nu }>0.\end{array}$

b) If $\frac{\nu L_f}{2\left(L_f-\rho \right)}\le \gamma L_f<1$ ,

$\frac{\delta }{2L_f}=\frac{2-\nu }{2\nu \gamma L_f}+\frac{1}{2}-\frac{\gamma L_f}{\nu }>\frac{2-\nu }{2\nu }-\frac{1}{\nu }+\frac{1}{2}=0.$

According to the analysis of (a) and (b), it implies that whenever $\gamma <\frac{1}{L_f}$ , $\delta$ is strictly positive, therefore, we also obtain $\frac{\delta }{2L}>0$ .

Case 2: If $2\left(1-\frac{\rho }{L_f}\right)\le \nu <2$ .

This inequality requires $\rho$ must satisfy $\rho >0$ , otherwise $\nu$ will an empty. To obtain a simple and unified expression for the step-size condition, we set $\rho ={\rho }_f$ . The original condition is equivalent to $\frac{1}{L_f}\ge \frac{2-\nu }{2{\rho }_f}$ . Since $L\ge L_f$ , we can set $\frac{1}{L}=\frac{2-\nu }{2{\rho }_f}\le \frac{1}{L_f}$ , substituting $\frac{1}{L}=\frac{2-\nu }{2{\rho }_f}$ into (17) and simplifying yields

$\frac{\delta }{2}=\frac{2-\nu }{2\nu \gamma }+\{\begin{array}{ll}-\frac{{\rho }_f}{\nu }\hfill & \gamma <\frac{2-\nu }{2{\rho }_f}\hfill \\ -\frac{{\rho }_f}{\nu }-\left(\frac{\gamma }{\nu }-\frac{2-\nu }{2{\rho }_f\nu }\right)\cdot L_f^2\hfill & \text{otherwise}.\hfill \end{array}$

When $\gamma <\frac{2-\nu }{2{\rho }_f}=\frac{1}{L}$ , it is easy to verify that

$\frac{\delta }{2L}=\frac{2-\nu }{2\nu \gamma L}-\frac{{\rho }_f}{\nu L}>\frac{2-\nu }{2\nu }-\frac{{\rho }_f}{\nu L}=\frac{2-\nu }{2\nu }-\frac{{\rho }_f}{\nu }\cdot \frac{2-\nu }{2{\rho }_f}=0,$

we also obtain that $\delta$ is strictly positive for $\gamma <\frac{2-\nu }{2{\rho }_f}$ . But if $\gamma \ge \frac{2-\nu }{2{\rho }_f}$ , we can only obtain

$\frac{\delta }{2}=\frac{2-\nu }{2\nu \gamma }-\frac{{\rho }_f}{\nu }+\left(-\frac{\gamma }{\nu }+\frac{2-\nu }{2{\rho }_f\nu }\right)\cdot L_f^2<\frac{2-\nu }{2\nu }\cdot \frac{2{\rho }_f}{2-\nu }-\frac{{\rho }_f}{\nu }=0.$

Consequently, we obtain that

$\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\ge \frac{\delta }{2}{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2,$

where $\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2>0$ and $\delta$ is strictly positive with $\gamma <\text{min}\left\{\frac{1}{L_f},\frac{2-\nu }{2{\rho }_f}\right\}$ . This shows that the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\mathbb{A}}}$ is nonincreasing.

(ii) When $\nu \in \left(0,2\right)$ , $\rho <0$ . The focus in the following will be on the strongly convex case. Utilizing Theorems 4, we have

$f\left(x_n\right)-f\left(x_{n+1}\right)\ge \langle \nabla f\left(x_{n+1}\right),x_n-x_{n+1}\rangle +\frac{1}{2L_f}{\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2.$

Similar constructed to (i), we derive the following inequality

$\begin{array}{l}\frac{1}{L_f}\left(\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\right)\\ \ge \left(-\frac{1}{2\gamma L_f}+\frac{1}{\nu \gamma L_f}\right){\Vert x_{n+1}-x_n\Vert }^2\\ -\left(\frac{\gamma }{\nu L_f}-\frac{1}{2L_f^2}\right){\Vert \nabla f\left(x_{n+1}\right)-\nabla f\left(x_n\right)\Vert }^2+\frac{\tau }{2L_f}{\Vert w_{n+1}-w_n\Vert }^2.\end{array}$

$\delta$ can be expressed as

$\frac{\delta }{2L_f}=\{\begin{array}{ll}-\frac{1}{2\gamma L_f}+\frac{1}{\nu \gamma L_f}\hfill & \frac{\gamma }{\nu L_f}-\frac{1}{2L_f^2}<0,\hfill \\ -\frac{1}{2\gamma L_f}+\frac{1}{\nu \gamma L_f}-\left(\frac{\gamma }{\nu L_f}-\frac{1}{2L_f^2}\right)L_f^2\hfill & \text{otherwise}.\hfill \end{array}$

since $\nu \in \left(0,2\right)$ , we can verify that for any $\gamma$ satisfying $\gamma <\frac{1}{L_f}$ , the constant $\delta$ is strictly positive.

a) If $0<\gamma L_f<\frac{\nu }{2}<1$ ,

$\frac{\delta }{2L_f}=\frac{2-\nu }{2\nu \gamma L_f}>\frac{2-\nu }{2\nu }>0.$

b) If $\frac{\nu }{2}\le \gamma L_f<1$ ,

$\frac{\delta }{2L_f}=\frac{2-\nu }{2\nu \gamma L_f}+\frac{1}{2}-\frac{\gamma L_f}{\nu }>\frac{2-\nu }{2\nu }-\frac{1}{\nu }+\frac{1}{2}=0.$

Therefore, when $\gamma <\frac{1}{L_f}$ , it ensures that $\delta >0$ .

In summary, let ${\left[{\rho }_f\right]}_{+}=\max \left\{{\rho }_f,0\right\}$ , the range of $\gamma$ can be expressed as $\gamma <\text{min}\left\{\frac{1}{L_f},\frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}}\right\}$ , then sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\mathbb{A}}}$ is nonincreasing.

□

Theorem 7 (Subsequence convergence). Suppose that Assumption 1 hold, and let ${\left\{\left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ be a sequence generated by Algorithm 1 with stepsize $\gamma$ as in Theorem 6. The following hold

Suppose that $F$ is coercive. Then the sequence ${\left\{\left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is bounded, when $n\to +\infty$ , we have $\Vert x_{n+1}-x_n\Vert \to 0$ , $\Vert y_{n+1}-y_n\Vert \to 0$ , $\Vert z_{n+1}-z_n\Vert \to 0$ , $\Vert z_{n+1}-x_{n+1}\Vert \to 0$ , and $\Vert w_{n+1}-w_n\Vert \to 0$ . For any cluster point $\left(x^{\text{*}},y^{\text{*}},z^{\text{*}},w^{\text{*}}\right)$ , we have $x^{\text{*}}=z^{\text{*}}$ ,

$0\in \nabla f\left(z^{\text{*}}\right)+\partial h\left(z^{\text{*}}\right)-\partial g\left(z^{\text{*}}\right),$

and

$\underset{n\to +\infty }{\lim }\Phi \left(x_n,y_n,z_n,w_n\right)=\Phi \left(x^{*},y^{*},z^{*},w^{*}\right)=\underset{n\to +\infty }{\lim }F\left(z_n\right)=F\left(z^{*}\right).$

Proof. First, we show that the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\mathbb{A}}}$ is bounded.

Since $f$ is $L_f$ -smooth function, the descent lemma yields the following inequalities

$f\left(z_n\right)+\langle \nabla f\left(x_n\right),x_n-z_n\rangle -\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2\le f\left(x_n\right),$

$f\left(z_n\right)+\langle \nabla f\left(x_n\right),x_n-z_n\rangle +\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2\ge f\left(x_n\right),$

Combining the above two inequalities, we have

$\begin{array}{l}f\left(z_n\right)+\langle \nabla f\left(x_n\right),x_n-z_n\rangle -\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2\\ \le f\left(x_n\right)\le f\left(z_n\right)+\langle \nabla f\left(x_n\right),x_n-z_n\rangle +\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2.\end{array}$ (18)

According to Lemma 5(i) and $y_{n+1}=y_n+\nu \left(z_{n+1}-x_{n+1}\right)$ , we know that

$\gamma \nabla f\left(x_n\right)=y_{n-1}-x_n=y_n-\nu \left(z_n-x_n\right)-x_n=\left(y_n-z_n\right)-\left(1-\nu \right)\left(x_n-z_n\right),$

which implies that

$\nabla f\left(x_n\right)=\frac{1}{\gamma }\left(y_n-z_n\right)-\frac{1-\nu }{\gamma }\left(x_n-z_n\right).$ (19)

Now, we estimate the term $\langle \nabla f\left(x_n\right),x_n-z_n\rangle$ in (18) with (19), we derive that

$\begin{array}{c}\langle \nabla f\left(x_n\right),x_n-z_n\rangle =\langle \frac{1}{\gamma }\left(y_n-z_n\right)-\frac{1}{\gamma }\left(1-\nu \right)\left(x_n-z_n\right),x_n-z_n\rangle \\ =\frac{1}{\gamma }\langle y_n-z_n,x_n-z_n\rangle -\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2\\ =\frac{1}{2\gamma }{\Vert y_n-z_n\Vert }^2+\frac{1}{2\gamma }{\Vert x_n-z_n\Vert }^2-\frac{1}{2\gamma }{\Vert x_n-y_n\Vert }^2\\ -\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2.\end{array}$ (20)

Since $g^{\text{*}}$ is the Fenchel conjugate of $g$ , by Proposition 1,

$g^{\text{*}}\left(w_n\right)-\langle w_n,z_n\rangle \ge -g\left(z_n\right).$ (21)

Combining (18) with (20) and (21), we get

$\begin{array}{c}\Phi \left(x_n,y_n,z_n,w_n\right)=f\left(x_n\right)+h\left(z_n\right)+g^{*}\left(w_n\right)-\langle w_n,z_n\rangle +\frac{1}{2\gamma }{\Vert x_n-y_n\Vert }^2\\ -\frac{1}{2\gamma }{\Vert y_n-z_n\Vert }^2+\frac{1-\nu }{\gamma }{\Vert x_n-z_n\Vert }^2\\ =f\left(x_n\right)+h\left(z_n\right)+g^{*}\left(w_n\right)-\langle w_n,z_n\rangle \\ +\langle \nabla f\left(x_n\right),z_n-x_n\rangle +\frac{1}{2\gamma }{\Vert x_n-z_n\Vert }^2\\ \ge f\left(z_n\right)+h\left(z_n\right)-g\left(z_n\right)+\langle \nabla f\left(x_n\right),z_n-x_n\rangle \\ +\frac{1}{2\gamma }{\Vert x_n-z_n\Vert }^2+\langle \nabla f\left(x_n\right),x_n-z_n\rangle -\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2\\ =f\left(z_n\right)+h\left(z_n\right)-g\left(z_n\right)+\left(\frac{1}{2\gamma }-\frac{L_f}{2}\right){\Vert x_n-z_n\Vert }^2\\ =F\left(z_n\right)+\left(\frac{1}{2\gamma }-\frac{L_f}{2}\right){\Vert x_n-z_n\Vert }^2.\end{array}$ (22)

From Lemma 5(ii), we have

$z_{n-1}\in \partial g^{\text{*}}\left(w_n\right)+\tau \left(w_n-w_{n-1}\right).$

And because of Proposition 1(ii),

$g^{\text{*}}\left(w_n\right)+g\left(z_{n-1}-\tau \left(w_n-w_{n-1}\right)\right)=\langle w_n,z_{n-1}-\tau \left(w_n-w_{n-1}\right)\rangle ,$

subtracting $\langle w_n,z_n\rangle$ from both sides of the equation, then rearrange it

$\begin{array}{c}{g}^{\text{*}}\left(w_n\right)-\langle w_n,z_n\rangle =\langle w_n,z_{n-1}-\tau \left(w_n-w_{n-1}\right)\rangle \\ -g\left(z_{n-1}-\tau \left(w_n-w_{n-1}\right)\right)-\langle w_n,z_n\rangle ,\\ =\langle w_n,z_{n-1}-z_n-\tau \left(w_n-w_{n-1}\right)\rangle \\ -g\left(z_{n-1}-\tau \left(w_n-w_{n-1}\right)\right).\end{array}$ (23)

Then, by the convexity of $g$ , taking $t_n\in \partial g\left(z_n\right)$ yields

$g\left(z_{n-1}-\tau \left(w_n-w_{n-1}\right)\right)\ge g\left(z_n\right)+\langle t_n,z_{n-1}-\tau \left(w_n-w_{n-1}\right)-z_n\rangle ,$

that is, $-g\left(z_{n-1}-\tau \left(w_n-w_{n-1}\right)\right)\le -g\left(z_n\right)+\langle t_n,z_n-z_{n-1}+\tau \left(w_n-w_{n-1}\right)\rangle$ .

Combining (23), we obtain

$g^{\text{*}}\left(w_n\right)-\langle w_n,z_n\rangle \le -g\left(z_n\right)+\langle t_n-w_n,z_n-z_{n-1}+\tau \left(w_n-w_{n-1}\right)\rangle ,$ (24)

Then, combining (18) with (20) and (24), they become

$\begin{array}{c}\Phi \left(x_n,y_n,z_n,w_n\right)\le f\left(z_n\right)+\langle \nabla f\left(x_n\right),x_n-z_n\rangle +\frac{L_f}{2}{\Vert x_n-z_n\Vert }^2\\ +h\left(z_n\right)-g\left(z_n\right)+\langle t_n-w_n,z_n-z_{n-1}+\tau \left(w_n-w_{n-1}\right)\rangle \\ +\langle \nabla f\left(x_n\right),z_n-x_n\rangle +\frac{1}{2\gamma }{\Vert x_n-z_n\Vert }^2\\ =F\left(z_n\right)+\langle t_n-w_n,z_n-z_{n-1}+\tau \left(w_n-w_{n-1}\right)\rangle \\ +\left(\frac{1}{2\gamma }+\frac{L_f}{2}\right){\Vert x_n-z_n\Vert }^2.\end{array}$ (25)

Since $\gamma <\text{min}\left\{\frac{1}{L_f},\frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}}\right\}$ , the size of $\gamma$ is always less than $\frac{1}{L_f}$ , $\frac{1}{2\gamma }-\frac{L_f}{2}>0$ is always holds. Since $F$ is a proper lower semicontinuous coercive function, it is bounded below [18], according to (22) that the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ is bounded below. From (i) above, ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ is nonincreasing. It means that it is convergent.

From Theorem 6, the following inequality holds

$\Phi \left(x_n,y_n,z_n,w_n\right)-\Phi \left(x_{n+1},y_{n+1},z_{n+1},w_{n+1}\right)\ge \frac{\delta }{2}{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2}{\Vert w_{n+1}-w_n\Vert }^2,$

Summing the above inequality from $n=1$ to $N$ and using the telescoping property, we obtain

$\begin{array}{l}\frac{\delta }{2}{\displaystyle \sum }_{n=1}^N{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2}{\displaystyle \sum }_{n=1}^N{\Vert w_{n+1}-w_n\Vert }^2\\ \le \Phi \left(x_1,y_1,z_1,w_1\right)-\Phi \left(x_{N+1},y_{N+1},z_{N+1},w_{N+1}\right),\end{array}$

Taking $N\to +\infty$ , we obtain

$\begin{array}{l}\frac{\delta }{2}{\displaystyle \sum }_{n=1}^{+\infty }{\Vert x_{n+1}-x_n\Vert }^2+\frac{\tau }{2}{\displaystyle \sum }_{n=1}^{+\infty }{\Vert w_{n+1}-w_n\Vert }^2\\ \le \Phi \left(x_1,y_1,z_1,w_1\right)-\underset{n\to +\infty }{\lim }\Phi \left(x_n,y_n,z_n,w_n\right)<+\infty .\end{array}$

From the above inequality, it shows that

${\displaystyle \sum }_{n=1}^{+\infty }{\Vert x_{n+1}-x_n\Vert }^2<+\infty ,{\displaystyle \sum }_{n=1}^{+\infty }{\Vert w_{n+1}-w_n\Vert }^2<+\infty ,$

which implies $\Vert x_{n+1}-x_n\Vert \to 0$ , $\Vert w_{n+1}-w_n\Vert \to 0$ . According to Lemma 5(iv) and (v), $\Vert y_{n+1}-y_n\Vert \to 0$ , $\Vert z_{n+1}-z_n\Vert \to 0$ .

Since the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ is nonincreasing, and according to (22), we can deduce that $F$ has an upper bound. Furthermore, since $F$ is bounded below, we can further conclude that ${\left\{F\left(z_n\right)\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ and ${\left\{\Vert x_n-z_n\Vert \right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is bounded. Moreover, recall that $F$ is coercive, we can derive that ${\left\{z_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is bounded, then ${\left\{x_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is also bounded. By Lemma 4(i), ${\left\{y_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is bounded. According to Lemma 4(ii) and Proposition 1(ii), we obtain

$w_{n+1}\in \partial g\left(z_n-\tau \left(w_{n+1}-w_n\right)\right).$

Since $t_n\in \partial g\left(z_n\right)$ , ${\left\{z_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ is bounded and $\Vert w_{n+1}-w_n\Vert \to 0$ as $n\to +\infty$ , it follows that the sequence ${\left\{w_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ and ${\left\{t_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ are bounded.

Let $\left(x^{\text{*}},y^{\text{*}},z^{\text{*}},w^{\text{*}}\right)$ be a cluster point of the sequence ${\left\{\left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ .

Since ${\left\{\Phi \left(x_n,y_n,z_n,w_n\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ is bounded, there exists a subsequence ${\left\{\left(x_{k_n},y_{k_n},z_{k_n},w_{k_n}\right)\right\}}_{n\in {\mathbb{N}}^{\mathbb{A}}}$ converges to $\left(x^{\text{*}},y^{\text{*}},z^{\text{*}},w^{\text{*}}\right)$ . It is known that as $n\to +\infty$ ,

$x_{n+1}-x_n\to 0,y_{n+1}-y_n\to 0,z_{n+1}-z_n\to 0\text{and}{w}_{n+1}-w_n\to 0.$

From the iteration of $y_{n+1}$ in Algorithm 1, we have $x_{n+1}-z_{n+1}=-\frac{1}{\nu }\left(y_{n+1}-y_n\right)$ , hence $x_{n+1}-z_{n+1}\to 0$ as $n\to +\infty$ , we obtain $x^{\text{*}}=z^{\text{*}}$ , then

$\underset{n\to +\infty }{\text{lim}}\left(x_{k_{n-1}},y_{k_{n-1}},z_{k_{n-1}}\right)=\underset{n\to +\infty }{\text{lim}}\left(x_{k_{n-2}},y_{k_{n-2}},z_{k_{n-2}}\right)=\left(x^{\text{*}},y^{\text{*}},z^{\text{*}}\right),$ (26)

if $\tau >0$ ,

$\underset{n\to +\infty }{\text{lim}}{w}_{k_{n-1}}=\underset{n\to +\infty }{\text{lim}}{w}_{k_{n-2}}=w^{\text{*}}.$ (27)

From the iteration of $z_{n+1}$ , we have

$\begin{array}{l}h\left(z_{k_n}\right)+\frac{1}{2\gamma }{\Vert z_{k_n}-\left(2x_{k_n}-y_{k_{n-1}}+\gamma w_{k_n}\right)\Vert }^2\\ \le h\left(z^{\text{*}}\right)+\frac{1}{2\gamma }{\Vert z^{\text{*}}-\left(2x_{k_n}-y_{k_{n-1}}+\gamma w_{k_n}\right)\Vert }^2.\end{array}$

Similar for $w_{n+1}$ , we have

$\begin{array}{l}{g}^{\text{*}}\left(w_{k_n}\right)-\langle w_{k_n},z_{k_{n-1}}\rangle +\frac{\tau }{2}{\Vert w_{k_n}-w_{k_{n-1}}\Vert }^2\\ \le g^{\text{*}}\left(w^{\text{*}}\right)-\langle w^{\text{*}},z_{k_{n-1}}\rangle +\frac{\tau }{2}{\Vert w^{\text{*}}-w_{k_{n-1}}\Vert }^2.\end{array}$

Using (26) and (27), taking the limit yields

$\underset{n\to +\infty }{\lim \sup }h\left(z_{k_n}\right)\le h\left(z^{*}\right),\underset{n\to +\infty }{\lim \sup }{g}^{*}\left(w_{k_n}\right)\le g^{*}\left(w^{*}\right).$

Additionally, since $h$ and $g^{\text{*}}$ are lower semicontinuous, we know that $\lim {\inf }_{n\to +\infty }h\left(z_{k_n}\right)\ge h\left(z^{*}\right)$ and $\lim {\inf }_{n\to +\infty }{g}^{*}\left(w_{k_n}\right)\ge g^{*}\left(w^{*}\right)$ . Consequently,

$\underset{n\to +\infty }{\text{lim}}h\left(z_{k_n}\right)=h\left(z^{\text{*}}\right),\underset{n\to +\infty }{\text{lim}}{g}^{\text{*}}\left(w_{k_n}\right)=g^{\text{*}}\left(w^{\text{*}}\right).$

Recall that Lemma 5(i) and (iii), we have

$w_{k_n}\in \nabla f\left(x_{k_n}\right)-\frac{1}{\gamma }\left(x_{k_n}-z_{k_n}\right)+\partial h\left(z_{k_n}\right).$

Since $x^{\text{*}}=z^{\text{*}}$ , by taking the limit, we have the following result

$w^{\text{*}}\in \nabla f\left(z^{\text{*}}\right)+\partial h\left(z^{\text{*}}\right).$ (28)

Similarly, from Lemma 5(ii), it follows that

$z_n\in \partial g^{\text{*}}\left(w_{n+1}\right)+\tau \left(w_{n+1}-w_n\right)$ (29)

Taking the limit on both sides of (28), it yields $z^{\text{*}}\in \partial g^{\text{*}}\left(w^{\text{*}}\right)$ . Using Proposition 1, it is not difficult to see that

$g^{\text{*}}\left(w^{\text{*}}\right)-\langle w^{\text{*}},z^{\text{*}}\rangle =-g\left(z^{\text{*}}\right)\text{and}{w}^{\text{*}}\in \partial g\left(z^{\text{*}}\right)$ (30)

Therefore, combining (28) and (30) leads to

$0\in \nabla f\left(z^{\text{*}}\right)+\partial h\left(z^{\text{*}}\right)-\partial g\left(z^{\text{*}}\right).$

Then, according to (4), we have

$\begin{array}{c}\Phi \left(x_{k_n},y_{k_n},z_{k_n},w_{k_n}\right)=f\left(x_{k_n}\right)+h\left(z_{k_n}\right)+g^{*}\left(w_{k_n}\right)-\langle w_{k_n},z_{k_n}\rangle \\ +\frac{1}{2\gamma }{\Vert x_{k_n}-y_{k_n}\Vert }^2-\frac{1}{2\gamma }{\Vert y_{k_n}-z_{k_n}\Vert }^2+\frac{1-\nu }{\gamma }{\Vert x_{k_n}-z_{k_n}\Vert }^2.\end{array}$

Taking limit on both sides of the above equality and using the continuity of $f$ , we deduce that

$\begin{array}{c}\underset{n\to +\infty }{\lim }\Phi \left(x_{k_n},y_{k_n},z_{k_n},w_{k_n}\right)=f\left(z^{*}\right)+h\left(z^{*}\right)+g^{*}\left(w^{*}\right)-\langle w^{*},z^{*}\rangle \\ =\Phi \left(x^{*},y^{*},z^{*},w^{*}\right).\end{array}$ (31)

According to (30) and the convergence of the sequence ${\left\{\Phi \left(x_n,y_n,z_n,w_z\right)\right\}}_{n\in {\mathbb{N}}^{*}}$ , we know

$\begin{array}{c}\underset{n\to +\infty }{\lim }\Phi \left(x_n,y_n,z_n,w_n\right)=f\left(x^{*}\right)+h\left(z^{*}\right)+g^{*}\left(w^{*}\right)-\langle w^{*},z^{*}\rangle \\ =f\left(z^{*}\right)+h\left(z^{*}\right)-g\left(z^{*}\right)\\ =F\left(z^{*}\right).\end{array}$

From (22), (25), together with the boundedness of the sequences ${\left\{w_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ and ${\left\{t_n\right\}}_{n\in {\mathbb{N}}^{\text{*}}}$ , and the fact that $z_{n+1}-z_n\to 0$ , $w_{n+1}-w_n\to 0$ , and $x_{n+1}-z_{n+1}\to 0$ as $n\to 0$ , we have ${\lim }_{n\to +\infty }F\left(z_n\right)={\lim }_{n\to +\infty }\Phi \left(x_n,y_n,z_n,w_n\right)$ , thus the theorem is proved. □

Remark 3. Compared with the result of Pham et al.

$\gamma <\frac{-\nu {\rho }_f+\sqrt{{\nu }^2{\rho }_f^2+8\left(2-\nu \right)L_f^2}}{4L_f^2},$

the expression for $\gamma$ that we derived, namely

$\gamma <\text{min}\left\{\frac{1}{L_f},\frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}}\right\},$

is considerably simpler and more intuitive in form. This formulation clearly reveals the independent roles of the two key constants, $\frac{1}{L_f}$ reflects the restriction imposed by the smoothness of $f$ , while $\frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}}$ captures the limitation due to its hypoconvexity. The final step size must satisfy both constraints simultaneously. Moreover, one can intuitively see how changes in $L_f$ or ${\rho }_f$ affect the allowable step size range.

We now show that the step size range we obtain is always not smaller than that of Pham et al. First, if we require

$\frac{-\nu {\rho }_f+\sqrt{{\nu }^2{\rho }_f^2+8\left(2-\nu \right)L_f^2}}{4L_f^2}\le \frac{1}{L_f},$

then it follows that ${\rho }_f\ge -L_f$ . Second, if we require

$\frac{-\nu {\rho }_f+\sqrt{{\nu }^2{\rho }_f^2+8\left(2-\nu \right)L_f^2}}{4L_f^2}\le \frac{2-\nu }{2{\left[{\rho }_f\right]}_{+}},$

then it follows that ${\rho }_f^2\le L_f^2$ , i.e., ${\rho }_f\in \left[-L_f,L_f\right]$ , which is exactly consistent with the assumption.

Thus, the new admissible set contains the old one. Notably, when $\nu =1$ , ${\rho }_f=L_f$ , the range of $\gamma$ is the same as that of Pham et al.

4. Conclusion

We revisit the Backward-Douglas-Rachford algorithm proposed by Pham et al. for solving generalized DC programming problems. While retaining the original assumptions, we adopt the analysis framework of Themelis et al. to derive a step size condition for BDRSM that has a larger range and a more concise expression. This step size range is always not smaller than that obtained by Pham et al., and the two are equivalent in special cases. Moreover, under this step size range, we establish the subsequential convergence of the iterative sequence generated by BDRSM.