Partial symmetric regularized alternating direction method of multipliers for non-convex split feasibility problems

1.   Introduction

The split feasibility problem (SFP) ^[1] is formulated as

where $C$ and $Q$ are both non-emepty closed convex sets.

The SFP was first introduced by Censor and Elfving ^[1], which was used in modeling various inverse problems arising from signal processing ^[2], medical image reconstruction ^[3], and further studied by many researchers ^[4,5]. Additionally, a variety of iterative algorithms have been employed to tackle the convex SFP ^[6,7,8,9].

When at least one of $C$ and $Q$ in Eq (1.1) is a non-convex set, it is called a non-convex SFP. The application of non-convex SFP is becoming increasingly widespread in various fields. Li and Pong ^[10] proposed the Douglas-Rachford algorithm for this type of problem. Moudafi introduced a semi-alternating algorithm in ^[11] to solve non-convex split equation problems and proved its global convergence under mild conditions. Chen et al. ^[12] developed S-Subgradient projection methods utilizing S-Subdifferential functions. Furthermore, Chen et al. ^[13] proposed an S-Subgradient projection algorithm incorporating an inertial technique for solving non-convex SFP, and proved the weak convergence of the algorithm in these two papers. Additionally, Guo proposed an inexact averaged projection algorithm for non-convex multiple sets SFP ^[14], and established the convergence of the proposed algorithm through the Kurdyka Lojasiewicz inequality.

Currently, there is a limited number of references to discuss this kind of problem. For solving non-convex SFP, Gibali et al. ^[15] presented four different optimization formulations and corresponding iterative algorithms. One of the fomulations is as follows:

where $C$ is a closed convex set and $Q$ is a closed non-convex set. This optimization problem is the sum of two non-negative functions, and when the optimal value of (1.2) is zero, then the achieved optimization solution is the solution of non-convex SFP.

By applying the augument Lagrangian method, Gibali ^[15] processed the proximal alternating directions method (ADMM), linearized proximal ADMM, and weighted proximal ADMM to solve (1.2), which are the continuation of classic ADMM ^[16]. The iterative form of the weighted proximal ADMM (WPADMM) is the following:

As the original problem can be reformuated as a seperable nonconvex optimization problem (1.2), there are many advanced accelerated ADMM-type methods for solving the reformulation, such as ^[17] and ^[18]. Moreover, the last inexact one had been shownto be convergent with linear convergence rate and performed surprisingly efficient than some existing ADMM-type methods. In addition, some primal-dual splitting methods can also be used to solve it, such as ^[19] and ^[20]. However, the proposed methods invovled in the last two references lacks theoretical assurance since they focused on the convex case. And, due to the focus of ^[21] and ^[22] on convex problems, it is necessary to study the convergence of partially symmetric regularized ADMM in non-convex cases.

Furthermore, due to the slow convergence speed of existing ADMM, based on the above analysis and problem (1.2), we use the weighted proximal ADMM algorithm and add updates of Lagrangian multipliers to demonstrate global convergence.

In this article, the models for the functions and non-convex split feasibility problems are different, and the results of ADMM cannot be directly applied. And, we have added updates to the Lagrangian multiplier term to improve the convergence speed of the algorithm.

The structure of the paper is as follows. The basic concepts, definitions, and related results are described in the second part. The third section presents the algorithm and its proof. The fourth part proves the convergence rate of the algorithm. The fifth section provides the corresponding numerical experiment, which verifies the feasibility and effectiveness of the algorithm.

2.   Preliminaries

In this article, $\mathbb{R}^n$ represents an $n$-dimensional Euclidean space, $\mathbb{R}^{m\times n}$ denotes $m \times n$ real matrices, $\mathbb{N}$ denotes the set of natural number, and $\|\text{ }\!\!\cdot\!\!\text{ }\|$ represents the Euclidean norm. For any $x, y \in \mathbb{R}^n$, $\langle x, y \rangle = x^T y$. The G-norm ${{\left\| x \right\|}_{G}} = \sqrt{{{x}^{T}}Gx}$ of $x$, where $G {\underset{\raise0.3em\hbox{ $\smash{ -}$ }}{\succ }}(\succ)0$ is a symmetric positive semidefinite matrix. ${{\lambda }_{\min }}(G)$ and ${{\lambda }_{\max }}(G)$ represent the minimum and maximum eigenvalues of the symmetric matrix $G$, respectively. Then, ${{\lambda }_{\min }}(G){{\left\| y \right\|}^{2}}\le \left\| y \right\|_{G}^{2}\le {{\lambda }_{\max }}(G){{\left\| y \right\|}^{2}}$, $\forall y \in \mathbb{R}^n$.

To prove the partially symmetric regularized alternating direction multiplier algorithm for non-convex split feasibility problems, two functions play a crucial role which are the indicator function and the distance function. Mathematically speaking, given a non-empty closed set $Q$ in the $n$-dimensional Euclidean space $\mathbb{R}^n$, the indicator function is defined as

When $Q$ is a closed non-convex set, the indicator function is proper, lower semi-continuous. The definition of proper function can be seen in reference ^[23].

The distance function of the set $C$, represented by $d_C:{{\mathbb{R}}^{n}}\to \mathbb{R}$, is given by

In this article, we also write $d_C(x)$ as $d(x, C)$.

When $C$ is a closed convex set, the square of the distance function is smooth. Specifically, if $C = \emptyset$, then $d_C(x) = +\infty$. Let $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$. Define

Given a non-empty closed subset $C$ of Euclidean space, the orthogonal projection on set $C$ is the operator $P_C (x):\mathbb{R}^n \rightarrow C$, defined as

Definition 1. ^[24] If the function $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ satisfies $g({{y}_{0}})\le \underset{{}}{\mathop{\lim }}\, {{\inf }_{y\to {{y}_{0}}}}g(y)$ at $y_0$, then function $g$ is said to be lower semi-continuous at $y_0$. If $g$ is lower semi-continuous at every point, then $g$ is called a lower semi-continuous function.

Definition 2. ^[24] Let the function $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ be proper lower semi-continuous.

(1) The $Fr\acute{e}chet$ subdifferential of $g$ at $y\in \text{dom}\ g$ is defined as

(2) The limit subdifferential of $g$ at $y \in \text{dom}\ g$ is defined as

By definition, the closure of $\partial g$ can be obtained, which means that $\{(y^k, u^k)\}$ is a sequence in $\mathbb{R}^n \times \mathbb{R}^n$ that satisfies the condition, for any $k\in N$,

$\text{and}$ if $(y^k, u^k)$ converges to $(y, u)$ $\text{and}$ $g(y^k)$ converges to $g(y)$, then $(y^k, u^k)\in \text{Graph}\; \partial g$.

Based on the first-order optimality condition of nonsmooth functions, the critical point set of $g$ is defined as

Remrk 1. According to the definition of subdifferentials, we can obtain the following properties (see reference ^[24]):

(1) $\forall y \in \mathbb{R}^n, \hat{\partial }g(y)\subseteq \partial g(y)$ and $\hat{\partial }g(y)$ is a closed convex set, $\partial g(y)$ is a closed set.

(2) If $y_{k} ^{*} \subseteq \hat{\partial }g(y)$ and $\mathop {\lim }\limits_{k \to \infty } \, ({{y}_{k}}, y_{k}^{*}) = (y, {{y}^{*}})$, then $y^{*} \in \partial g(y)$, i.e., $\partial g(y)$ is closed.

(3) If $y \in \mathbb{R}^n$ is the minimum point of $g$, then $0 \in \partial g(y)$; if $0 \in \partial g(y)$, then $y$ is the critical point of the function $g$.

(4) If $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ is proper lower semi-continuous and $f:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ is continuously differentiable, then for any $y \in \text{dom}\ g$, we have $\partial (f(x)+g(y)) = \nabla f(x)+\partial g(y)$.

Definition 3. ^[25] (Kurdyka-Lojasiewicz property) The function $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ is a proper lower semi-continuous function, and $g$ is said to have KL property in $y^* \in \text{dom}\ \partial g$ if there exists $\eta \in (0, +\infty]$, a certain neighborhood $U$ of $y^*$, and a continuous concave function $\varphi:[0, \eta)\rightarrow \mathbb{R}^+$, such that

(1) $\varphi (0) = 0$;

(2) $\varphi$ is continuously differentiable on $(0, \eta)$ and $\varphi$ is also continuous at 0;

(3) $\forall s \in (0, \eta), \varphi^{'}(s) > 0$;

(4) $\forall y \in U \cap [g(y^*) < g < g(y^*)+\eta]$, all KL inequalities hold, that is

Lemma 1. ^[26] (Consistent KL property) Let $\phi_n$ be the set of functions which satisfies the KL property. Assuming $\Omega$ is a compact set, and the function $g:{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ is a proper lower semi-continuous function. If the function $g$ is a constant on $\Omega$ and satisfies the KL property at every point in $\Omega$, then there exist $\varepsilon > 0, \eta > 0, \varphi \in \phi_n$ such that for any $\overline{y} \in \Omega$ and all $y$ belonging to the intersection

the following inequality holds true:

In some practical applications, many functions satisfy the KL property, such as semi-algebraic functions, real analytic functions, subanalytic functions, and strongly convex functions, etc., as seen in reference ^[27].

Lemma 2. ^[28] If $\psi :{{\mathbb{R}}^{n}}\to \mathbb{R}\cup \{+\infty \}$ is a continuous differentiable function and $\nabla \psi$ is Lipschitz continuous, then there exists a Lipschitz constant $L_\psi > 0$, such that for any $x, y \in \mathbb{R}^n$, there is

Definition 4. (Semi-algebraic sets and functions) (1) A subset $S$ of $\mathbb{R}^n$ is a real semi-algebraic set, if there exists a finite number of real polynomial functions $g_{ij}, h_{ij}:\mathbb{R}^n \rightarrow \mathbb{R}$ such that

(2) A function $f:\mathbb{R}^{n} \rightarrow (-\infty, +\infty]$ is called semi-algebraic if its graph

is a semi-algebraic subset of $\mathbb{R}^{n+1}$.

3.   Non-convex split feasibility problems

In this section, we study the solving method for problem (1.2), where $C$ is a non-empty closed convex set of $\mathbb{R}^n$ and $Q$ is a non-empty closed non-convex set of $\mathbb{R}^m$. According to the structure of $C$, the following conclusions hold.

(1) The function $d^{2} _C(\text{ }\!\!\cdot\!\!\text{ })$ is continuously differentiable.

(2) The gradient of $d^{2} _C(\text{ }\!\!\cdot\!\!\text{ })$ is Lipschitz continuous, i.e., there is a constant $L$ such that $\left\| \nabla d^{2}_C(y)-\nabla d^{2}_C(x) \right\|\le L \left\| y-x \right\|$.

Now, we give the algorthim.

Algorithm 1. Partial symmetric regularized alternating direction method of multipliers for non-convex split feasibility problems (PSRADMM)

Given three initial points $x^0, y^0$, and $\lambda^0$, $G\in {{\mathbb{R}}^{n\times n}}$ is a symmetric positive definite matrix. $\beta$, $\gamma$, and $s$ are constants. Iteratively update the sequence $\{{{\omega }^{k}} = ({{x}^{k}}, {{y}^{k}}, {{\lambda }^{k}})\}$ as follows:

Based on the optimality conditions for each subproblem in Algorithm 1, we have

Assumption 1. Some assumptions and conditions regarding Algorithm 1 are provided below.

(1) $\gamma+s > 0$ and $\gamma (1-2s) +s -6(1-s)^2 > 0$.

(2) $\beta > {{\beta }_{0}} = \frac{(\gamma+s) +\sqrt{{{(\gamma+s)}^{2}}+24[\gamma(1-2s)+s-6(1-s)^2]}}{2[\gamma(1-2s)+s-6(1-s)^2]}$.

(3) $\delta = \min \{{{\delta }_{1}}, {{\delta }_{2}}\}$, where

(4) $C, Q$ are both semi-algebraic sets.

Remark 2. The solution set of this inequality system (1) in Assupmtion 1 is represented as $(\gamma, s) \in D = D_1 \cup D_2$, where

and

It can be seen that $(\gamma, s)$ has a wide range of choices. Specifically, when $s \in (\frac{3}{4}, 1)$ occurs, $(\gamma = s, s)\in D_2$, which means that the parameters $\gamma$ and $s$ of PSRADMM can take the same value in this interval.

The augmented Lagrangian function for problem (1.2) is

where ${{\omega }} = ({{x}}, {{y}}, {{\lambda }})$, $\lambda \in \mathbb{R}^m$ is a Lagrangian multiplier, and $\beta > 0$ is a penalty parameter.

Without loss of generality, we assume that $\{{{\omega }^{k}} = ({{x}^{k}}, {{y}^{k}}, {{\lambda }^{k}})\}$ produced by Algorithm 1 is bounded. The reason to do this will be explained in Lemma 7.

Lemma 3. The $\{{{\omega }^{*}} = ({{x}^{*}}, {{y}^{*}}, {{\lambda }^{*}})\}$ is the critical point of the augmented Lagrangian function $L_\beta (x, y, \lambda)$ for problem (1.2), i.e., $0 \in \partial L_\beta (\omega ^*)$, if and only if

Proof. Due to the simplicity of the proof, it is omitted here. □

Similar to the approach in reference ^[29], Lemma 4 below indicates that the sequence $\{ {L_{\beta}}({\omega}^{k}) \}$ monotonically decreases. For ease of analysis, let $z = (x, y)$ and $z^k = (x^k, y^k)$.

Lemma 4. If Assumption 1 holds, then

Proof. First, based on the iterative formulas (3.2a), (3.2d), and (3.2b), one has

and

On the other hand, based on the definition of the augmented Lagrangian function, Eq (3.2c), the Lipschitz continuity of $\nabla d^{2} _C$, and Lemma 2, then

And, because ${y}^{k+1}$ is the solution of (3.1a), then

Therefore, adding inequalities (3.4), (3.5), (3.6), and (3.7), we have

Also, according to (3.1b) and (3.1d), we have

On the other hand, from (3.2c) and (3.2d), it can be concluded that

Combining the Lipschitz continuity of $\nabla d^{2}_{C}(x)$, we obtain

Furthermore, using the Cauchy inequality for (3.12), we have

Combining Eqs (3.9), (3.10), and inequality (3.13), one has

Substituting inequality (3.14) into inequality (3.8), we have

Therefore,

□

Lemma 5. If Assumption 1 holds and the iteration sequence $\{{{\omega }^{k}} = ({{x}^{k}}, {{y}^{k}}, {{\lambda }^{k}})\}$ generated by Algorithm 1 is bounded, then

Proof. Due to $\{{{\omega }^{k}}\}$ being bounded, $\{{{{\omega }}^{k}}\}$ has at least one aggregation point $\omega ^*$. Hence, there exists a subsequence $\{ {\omega}^{k_j} \}$ such that $\mathop {\lim }\limits_{{k_j} \to + \infty } {{\omega }}^{{{k}_{j}}} = \omega ^{*}$. Because $\delta_Q(\text{ }\!\!\cdot\!\!\text{ })$ is a lower semi-continuous function and $d^{2} _C\, (\text{ }\!\!\cdot\!\!\text{ })$ is continuous differentiable, then ${L_{\beta}}\, (\text{ }\!\!\cdot\!\!\text{ })$ is lower semi-continuous. So ${L_{\beta}}\, ({{\omega }^{*}})\le \mathop {\lim }\limits_{{k_j} \to + \infty } \, \inf {L_{\beta}}\, ({{{\omega }}^{{{k}_{j}}}})$, i.e., $\{{L_{\beta}}\, ({{{\omega }}^{{{k}_{j}}}})\}$ has a lower bound.

According to Lemma 4, ${{L_{\beta}}({{{\omega}}^{{k_j}}})}$ monotonically decreases and then ${{L_{\beta}}({{{\omega}}^{{k_j}}})}$ converges. Therefore, by summing up (3.3) from $k = 0$ to $n$, we can obtain that

According to inequality (3.11), there are $\sum\limits_{k = 0}^{\infty}{{{\left\|{{\lambda}^{k+1}}-{{\lambda }^{k}} \right\|}^{2}}} < +\infty$, so $\sum\limits_{k = 0}^{\infty }{{{\left\| {{\omega }^{k+1}}-{{\omega }^{k}} \right\|}^{2}}} < +\infty$. □

Let $\Omega$ be the set of aggregation points of $\{{{\omega }^{k}}\}$ and based on the results of Lemma 5. We can establish the global convergence of Algorithm 1.

Theorem 1. (Global convergence) If Assumption 1 holds and $\{{{\omega }^{k}}\}$ is bounded, then the following conclusions hold.

(1) $\Omega$ is a non-empty compact set and

(2) $\{{L_\beta}({{{\omega }}^{k}})\}$ is convergent, and for all ${{{\omega }}^{*}}\in {\Omega }$,

(3) $\Omega \subseteq \text{crit}{{L}_{\beta }}.$

Proof. (1) The conclusion can be drawn from the boundedness of $\{{{\omega }^{k}}\}$ and the definition of $\Omega$.

(2) Let ${{{\omega }}^{*}}\in {\Omega }$. Therefore, there exists a subsequence $\{{{{\omega }}^{{{k}_{j}}}}\}$ of $\{{{{\omega }}^{k}}\}$ which converges to ${{{\omega }}^{*}}$.

Also, according to the lower semi-continuity of ${L_{\beta}}\, (\text{ }\!\!\cdot\!\!\text{ })$, i.e., ${L_{\beta}}({{{\omega }}^{*}})\le \mathop {\lim }\limits_{{k_j} \to + \infty } \ \inf {L_{\beta}}({{{\omega }}^{{{k}_{j}}+1}})$, then $\mathop {\lim }\limits_{{k_j} \to + \infty } \, {L_{\beta}}({{{\omega }}^{{{k}_{j}}+1}}) = {L_{\beta}}({{{\omega }}^{*}})$ and Lemma 4 states that $\{{L_{\beta}}({{{\omega }}^{*}})\}$ monotonically decreases. Therefore,

(3) Let ${{\omega}^{*}} = ({{x}^{*}}, {{y}^{*}}, {{\lambda}^{*}})\in \Omega$. Therefore, there exists a subsequence $\{{{\omega }^{{{k}_{j}}}}\}$ of $\{{{\omega }^{k}}\}$ that converges to ${{\omega }^{*}}$.

According to Lemma 5, $\mathop {\lim }\limits_{{k_j} \to + \infty } \, {{\omega}^{{{k}_{j}+1}}} = {{\omega}^{*}}$. And, by (3.1b), $\{\lambda^{{k_j}+\frac{1}{2}}\}$ is covergent. Assume that $\mathop {\lim }\limits_{{k_j} \to + \infty } \, {{\lambda }^{{{k}_{j}}+\frac{1}{2}}} = {{\lambda }^{**}}$. Let $k = {{k}_{j}}$ in (3.1b) and (3.1d), and take the limit. Then, we have

which, combined with $(\gamma +s)\beta > 0$, it can be seen that $A{{x}^{*}}-{{y}^{*}} = 0, {{\lambda }^{**}} = {{\lambda }^{*}}$.

As a result, ${{x}^{*}}$ and ${{y}^{*}}$ are the feasible points for problem (1.1). According to the following inequality (3.1a), we can obtain

Because $\mathop {\lim }\limits_{{k_j} \to + \infty } \, {{\omega }^{{{k}_{j}}}} = \mathop {\lim }\limits_{{k_j} \to + \infty } \, {{\omega }^{{{k}_{j}}+1}} = {{\omega }^{*}}$, we have $\mathop {\lim }\limits_{{k_j} \to + \infty } \, \delta_Q({{y}^{{{k}_{j}}+1}})\le \delta_Q({{y}^{*}})$. Also, due to the lower semi-continuity of $\delta_Q(y)$, one has $\mathop {\lim }\limits_{{k_j} \to + \infty } \, \delta_Q({{y}^{{{k}_{j}}+1}}) = \delta_Q({{y}^{*}})$. Furthermore, combining the closeness of $\partial \delta_Q$ and the continuity of $\nabla d^{2} _C$, and letting $k = {{k}_{j}}\to +\infty$ in (3.1), we have

Therefore, according to Lemma 3, ${{\omega }^{*}}\in \text{crit}{{L}_{\beta }}$. Hence, $\Omega \subseteq \text{crit}{{L}_{\beta }}$. □

Lemma 6. If Assumption 1 holds, then there exists a constant $\tau > 0$, and, for all $k\geq2$,

Proof. Through the definition of ${L_{\beta}}\, (\text{ }\!\!\cdot\!\!\text{ })$, it can be obtained that

Let ${{\varepsilon }^{k+1}} = (\varepsilon _{1}^{k+1}, \varepsilon _{2}^{k+1}, \varepsilon _{3}^{k+1})\in \partial {L_{\beta}}({{{\omega }}^{k+1}})$. Combining (3.2) and (3.15), one has

As a result, $\varepsilon _{1}^{k+1} \in {{\partial }_{x}}{L_{\beta}}({{{\omega }}^{k+1}})$, $\varepsilon _{2}^{k+1} \in {{\partial }_{y}}{L_{\beta}}({{{\omega }}^{k+1}})$, $\varepsilon _{3}^{k+1} \in {{\partial}_{\lambda}}{L_{\beta}}({{{\omega }}^{k+1}})$, and ${{\varepsilon }^{k+1}}\in \partial {L_{\beta}}({{{\omega }}^{k+1}})$.

Hence, for all $k \geq1$, there exists ${{\tau }_{0}} > 0$ such that

According to the result of inequality (3.12), there exists a constant $\tau_1 > 0$ such that

Combining (3.16) and (3.17), it can be concluded that there exists a constant $\tau_1 > 0$, and, for all $k\geq2$,

□

Now, we study the strong convergence of the Algorithm 1 by using Lemma 4, Lemma 6, and the relevant conclusions in Theorem 1.

Theorem 2. (Strong convergence) Assume that $\{{{\omega}_k}\}$ is bounded and ${L_\beta}\, (\text{ }\!\!\cdot\!\!\text{ })$ satisfies the KL property on ${\Omega}$. Then,

(1)$\lim\limits_{k\rightarrow \infty}\|\omega^{k+1}-\omega^k\| = 0.$

(2) $\{\omega_k\}$ converges to the critical point of ${L_\beta}\, (\text{ }\!\!\cdot\!\!\text{ })$.

Proof. (1) Theorem 1(2) means that $\mathop {\lim }\limits_{k \to + \infty } \, {L_{\beta}}({{{\omega} }^{k}}) = {L_{\beta}}({{{\omega }}^{*}})$ for each ${ {{\omega }^{*}}}\in{ \Omega }$. Now we divide into two cases for further analysis.

Case 1. There exists an integer $k_0$ such that ${L_{\beta}}({{{\omega }}^{k_0}}) = {L_{\beta}}({{{\omega} }^{*}})$. By Lemma 4, for all $k\geq k_0$, we have

As a result, ${{x}^{k+1}} = {{x}^{k}}, {{y}^{k+1}} = {{y}^{k}}$. Also, from inequality (3.15), for all $k\ge {{k}_{0}+2}$, we have ${{\lambda }^{k+1}} = {{\lambda }^{k}}$ and ${{\omega }^{k+1}} = {{\omega }^{k}}$.

Case 2. Assume for all $k \ge 1$, ${L_{\beta}}({{{\omega} }^{k}}) > {L_{\beta}}({{{\omega} }^{*}})$. Due to $d({{{\omega} }^{k}}, \Omega)\to 0$, for any given $\varepsilon > 0$, there exists $k_1 > 0$, for $k > k_1$, such that $d({{{\omega} }^{k}}, \Omega) < \varepsilon$. And, for any given $\eta > 0$, there exists $k_2 > 0$, for $k > \widetilde{k} = \max \{{{k}_{1}}, {{k}_{2}}\}$, such that ${L_{\beta}}({{{\omega} }^{k}}) < {L_{\beta}}({{{\omega} }^{*}})+\eta$.

Therefore,

Because $\{{{\omega }^{k}}\}$ is bounded, according to Theorem 1, it is known that ${\Omega}$ is a non-empty compact set, and ${L_{\beta}}\, (\text{ }\!\!\cdot\!\!\text{ })$ is a constant on ${\Omega}$. Therefore, using Lemma 1, for all $k > \widetilde{k}$,

Because ${{\phi }^{'}}({L_{\beta}}({{{\omega }}^{k}})-{L_{\beta}}({{{\omega }}^{*}})) > 0$, therefore

Due to the convexity of the function $\phi$, it can be concluded that

Therefore,

Combining inequalities (3.18) and (3.19) with Lemma 6, one has

Note ${{\Delta }_{p, q}} = \phi ({L_{\beta}}({{{\omega }}^{p}})-{L_{\beta}}({{{\omega }}^{*}}))-\phi ({L_{\beta}}({{{\omega }}^{q}})-{L_{\beta}}({{{\omega }}^{*}}))$.

For simplicity, let ${{\wedge }_{k}} = \left\| {{x}^{k}}-{{x}^{k-1}} \right\|+\left\| {{y}^{k}}-{{y}^{k-1}} \right\|$, and combining Lemma 4 and inequality (3.20), for all $k > \widetilde{k}$, it can be derived that

According to inequality (3.21), it can be concluded that

Furthermore, we have

For inequality (3.22), summing up from $\widetilde{k}+1$ to $m$, it can be concluded that

Note that ${{\phi }^{'}}({L}({{{\omega }}^{m+1}})-{L}({{{\omega }}^{*}}))\ge 0$. According to the above inequality and by using the Cauchy inequality, at the same time letting $m\to +\infty$, we have

Therefore, $\sum\limits_{k = 0}^{\infty }{\left\| {{x}^{k+1}}-{{x}^{k}} \right\|} < +\infty$ and $\sum\limits_{k = 0}^{\infty }{\left\| {{y}^{k+1}}-{{y}^{k}} \right\|} < +\infty$. By (3.17), it can be concluded that

Additionally, we have noticed that

Hence, $\sum\limits_{k = 0}^{\infty }{\left\| {{\omega }^{k+1}}-{{\omega }^{k}} \right\|} < +\infty.$ In other words,

(2) From (1) we know that $\{{{\omega }^{k}}\}$ is a Cauchy sequence, and therefore it converges, and then from Theorem 1 (3), we know that $\{{{\omega }^{k}}\}$ converges to the critical point of the sequence ${L}_\beta\, (\text{ }\!\!\cdot\!\!\text{ })$ as a whole. □

Next, we wonder if the assumption about the boundedness of $\{{{\omega}_k}\}$ is reasonable, which will be ensured by the following lemma.

Lemma 7. Suppose that Assumption 1 and the following conditions (1)–(3) hold.

(1) $A$ is a row full rank matrix.

(2) The relaxation factor $s\in (\frac{3-\sqrt{3}}{2}, \frac{3+\sqrt{3}}{2})$.

(3) The function ${\bar{f}}(x^{k}) = d^{2} _C(x^{k}) - \frac{\|\nabla d^{2} _C(x^k)\|^{2}}{2\beta(2s-1)\|A\|^2}$ has a lower bound and is coercive, i.e.,

Then, the sequence $\{{{\omega}_k}\}$ generated by Algorithm 1 is bounded.

Proof. According to ${L_{\beta} (\omega ^k)}$ being monotonically decreasing, ${L_{\beta} (\omega ^k)}\leq {L_{\beta} (\omega ^0)}$, which, combined with (3.11), we have

where $(A^{T})^+$ represents the Morre-Penrose inverse of $A^{T}$.

Therefore, one has

It is not difficult to deduce that $A{x}^{k}-{y}^{k}-\frac{{({A}^{T})}^{+}\nabla d^{2} _C({x}^{k})}{(2s-1)\beta }$ is bounded, so $\nabla d^{2} _C (x^k)$ is bounded. Furthermore, combining (3.11), we can know that ${\left\{ \lambda ^{k} \right\}}$ is bounded. Therefore, the boundedness of ${\left\{ \omega ^{k} \right\}}$ has been proven. □

4.   Convergence rate analysis

In this section, we further discuss the convergence rate of PSRADMM under the premise of strong convergence. The main results are as follows.

Theorem 3. Assume that ${\left\{ \omega ^{k} \right\}}$ is a sequence generated by PSRADMM and converges to ${\left\{ \omega ^{*} \right\}}$. Let $L_{\beta} (\cdot)$ satisfy the KL property at $\omega ^{*}$ and the correlation function $\varphi (t) = c{{t}^{1-\theta }}, \theta \in [0, 1), c > 0$. Then, the following conclusions hold.

(1) If $\theta = 0$, then sequence ${\left\{ \omega ^{k} \right\}}$ converges after finite iterations, i.e., there exists $k$ such that $\omega ^{k} = \omega ^{*}$.

(2) If $\theta \in (0, \frac{1}{2}]$, then there exists $\tau \in [0, 1)$, such that $\parallel\omega^{k} -\omega^{*} \parallel \le O(\tau^k)$, i.e., PSRADMM is linearly convergent.

(3) If $\theta \in (\frac{1}{2}, 1)$, then $\parallel\omega^{k} -\omega^{*} \parallel \le O(k^{\frac{1-\theta}{1-2\theta}})$, i.e., PSRADMM is sublinearly convergent.

Proof. For the case that $\theta = 0$, we have $\varphi(t) = ct$, hence $\varphi'(t) = c$. If $\omega ^{k}\neq \omega ^{*}$ for all $k$, then for a sufficiently large $k$, it is known by the KL property, and $cd(0, \partial L_{\beta} (\omega ^{k})) \geq 1$, which contradicts (3.16).

Assume $\theta > 0$, and combine (3.22).

Note that as ${L}_\beta\, (\text{ }\!\!\cdot\!\!\text{ })$ satisfies the KL property at $\omega ^{*}$, one has

and because $\varphi (t) = c{{t}^{1-\theta }}$, the above inequality is equivalent to

Also, due to (3.16), we have

and, combined with (4.2) and (4.3), there exists $\gamma > 0$ such that

By (4.1), it can be concluded that

Based on inequality (4.4), further proof will be completed using the relevant conclusions of Attouch and Bolte ^[26].

(1) If $\theta \in [0, \frac{1}{2})$, then, according to ^[26], there exist $c_{1} > 0$ and $\tau \in [0, 1)$ such that

(2) If $\theta \in (\frac{1}{2}, 1)$, then, according to ^[26], there exists $c_{2} > 0$ such that

Furthermore, from the Eq (3.11), Lemma 3, and the $L$ -Lipshitz continuity of $\nabla d^{2} _{C}$, it can be inferred that

Finally, according to (4.4)–(4.6), it can be concluded that conclusions (1)–(3) have been verified. □

5.   Numerical examples

In this section, we validated the feasibility and effectiveness of the PSRADMM compared to the WPADMM (1.3) by comparing the number of iterations and running time. The entire code is implemented in MATLAB R2018b. All numerical calculations were performed on the Lenovo Xiaoxin Air 13IWL, with a CPU clock of 1.6GHz and a memory of 8.00GB.

When $C$ is a non-convex closed set and $Q$ is a closed convex set, the above algorithm still holds true. For details, please see reference ^[29]. We consider a class of important problems that are often applied in practical fields such as image reconstruction and signal processing, that is, compressed sensing problems, which involves recovering a sparse signal $x$ from a linear system $Ax = b$. Transform the problem into a non-convex SFP, that is, find a vector $x \in \mathbb{R}^n$ which satisfies

where $C = \{x \in \mathbb{R}^n:\|x\|_0 \le 1\}$ (here, $\|x\|_0$ represents the number of non-zero elements in vector $x$), $b\in \mathbb{R}^m$, and the set $Q = \{b\}$. Therefore, this section starts from the perspective of solving non-convex SFP and solves the decompression sensing problem. We transform problem (1.2) into the following optimization problem, and take $G = u I - \beta A^T A$:

Using WPADMM to solve (5.1), we have

Using PSRADMM to solve (5.1), we have

In numerical experiments, $A$ is a randomly generated $m \times n$ matrix. The initial point $x^0$ belongs to rand$(n, 1)$, and the initial point $\lambda ^0$ is taken as the zero vector. In addition, the selection of correlation coefficients in WPADMM and PSRADMM is consistent, which are $\beta = 12, s = r = \frac{10}{12}$. When $\|\omega^{k+1}-\omega^k\| < \varepsilon$, the program terminates. In this section, we set $\varepsilon = 10^{-5}$.

We solve problem (5.1) using WPADMM and PSRADMM, and selected six different dimensions of A for testing. Table 1 provides a comprehensive overview of the primary test outcomes pertaining to both algorithms, encompassing vital metrics such as iteration number and runtime. Figures 1 and 2 show the main numerical test results of the two algorithms, where iter ($k$) and Time/s represent the number of iterations and CPU calculation time in seconds, respectively.

Upon thorough examination of Figures 1 and 2, we can see that the PSRADMM consistently outperforms the WPADMM in terms of both runtime efficiency and convergence behavior, as reflected by the iteration number. This observation suggests that the PSRADMM exhibits enhanced computational efficiency and convergence speed compared to the WPADMM.

Inspired by Godwin et al. ^[8], we apply the algorithm to image processing for deblurring. First, we blur the original image using a Gaussian blur kernel with a size of 15*15 and a standard deviation with a size of 2 to obtain the blurred image (See Figures 3–6).

We can see from the Figures 3–6 that PSRADMM has a better deblurring effect than WPADMM. However, we still need to evaluate the effectiveness of deblurring based on two indicators: peak signal-to-noise ratio (PSNR$: = 10log_{10} \frac{255^2}{\sqrt{MSE}}$) and structural similarity index (SSIM).

From Table 2, we can see that the PSNR of PSRADMM is better than that of WPADMM restored images. Measure 1: A higher PSNR value indicates that the difference between the processed image and the original image is small, usually indicating higher image quality. The PSNR value of PSRADMM is higher. Measure 2: An SSIM value close to 1 indicates a higher similarity in brightness, contrast, and structure between the processed image and the original image, usually indicating better image quality. The SSIM value of the PSRADMM algorithm is closer to 1.

Finally, we validate the feasibility and effectiveness of the algorithm through image enhancement. Figures 7 and 8 show the images displayed using image enhancement techniques using the WPADMM and PSRADMM algorithms, respectively.

From Table 3, we can see that the image enhancement effect of PSRADMM is better than that of the WPADMM by comparing PSNR and SSIM.

6.   Conclusions

In this article, we propose a partially symmetric regularized alternating direction multiplier method to solve non-convex split feasibility problems. A conclusion on global convergence is drawn. When the augmented Lagrangian function satisfies the KL property, the algorithm has strong convergence. In addition, this article provides the convergence rate of the algorithm. Finally, in the compressed sensing problem, numerical experiments have shown that our proposed algorithm outperforms existing weighted proximal symmetric regularized alternating direction multiplier methods for solving non-convex SFP. And, we applied the PSRADMM to image processing with good experimental results.

Author contributions

Yue Zhao: Methodology; Meixia Li: Supervision; Xiaowei Pan: Software, Visualization; Jingjing Tan: Writing–original draft, Writing–review & editing. All authors have read and approved the final manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This project is supported by Natural Science Foundation of China (Grant No.12071351, 11571120) and Shandong Provincial Natural Science Foundation (Grant No.ZR2020MA027, ZR2022MA034).

Conflict of interest

The authors have no competing interests to declare that are relevant to the content of this article.