# New Inexact Parallel Splitting Algorithm for a Class of Separable Convex Programming

Authors: Xiaobiao Chen; Meiyu Zhang; Gaoshe Lian; Lichen Chai
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In this paper, a new inexact parallel splitting algorithm based on the shrinkage algorithm is proposed. We bring in inexact terms, and new iteration points are obtained by the parallel splitting method. A new descent direction and a proper step length are derived. Under reasonable assumptions, the convergence of the algorithm is demonstrated. Some matrix correction problem experiments show that the algorithm is efficient and easy to implement.


---

## Body

## 1. Introduction

This paper considers a class of minimization problems in the following form:(1)minF1x+F2zs.t.x−z=0x∈X,z∈Z,where F1x, F2x are convex functions defined on Rn. Projection solution on X and Z is not tricky.In practical applications, there exist quite a few structured optimizations arising from the fields such as electronic engineering and computer science, including matrix processing [1], traffic network analysis [2], least squares semi-definite programming problem [3, 4], image restoration problem [5], and so on.Use the following function to represent the Lagrangian function of (1):(2)Lx,y,λ=F1x+F2z−λTx−z.Gabay and Mercier first introduced alternating direction method (ADM) in [6], which is an efficient method to solve (2). For a given iterate zk,λk, a new iterate x˜k,z˜k,λ˜k can be generated by ADM via the scheme(3)x˜k=argminF1x−λkTx−zk|x∈X,z˜k=argminF2z−λkTx˜k−z|z∈Z,λ˜k=λk−βx˜k−z˜k.Recently, the ADMM has found many efficient applications, especially in machine learning, image processing [7–9], and matrix correction problem. Also, ADMM has been deeply investigated in previous work (see, e.g., [10–16]).However, the ADMM may fail when it comes to difficult subproblems in practical issues. To avoid such situations, various methods have been studied, such as linearization (see, e.g., [17, 18]), adding asymptotic terms (see, e.g., [15, 16]) and inexact solutions (see, e.g., [19–21]). Eckstein and Bertsekas first introduced an inexact technique used to solve the ADM algorithm in [12], which has been widely used and popularized (for details, refer to the bibliography [17–30]). On the flip side, the parameter β has a great influence on the convergence speed of the algorithm and the experimental effect. He et al. [21] introduced a method of adjusting the parameter to improve the convergence speed of the ADM. Also, this method was widely used. Recently, Chen et al. [22] proposed a new IPCM, which does not need to know the mathematical expression of the mapping; however, this algorithm has strict restrictions on parameters; based on IPCM in [22] and IPADM in [23], we get an improved inexact parallel splitting method for the model of (2), and our algorithm relaxes the constraints on parameters and is computationally simple.


## 2. Preliminaries

First, we review some preliminary knowledge that can help readers better understand the analysis that follows.Letfx represent the subgradient of F1x and hz represent the subgradient of F2z, respectively. As described in the literature [17], the optimal solution of the function Lx,z,λ is equivalent to finding υ∗=x∗,z∗,λ∗T which makes the following formula:(4)x−x∗,z−z∗,λ−λ∗fx∗−λ∗hz∗+λ∗x∗−z∗≥0,hold.For the convenience of analysis, we let(5)υ=x,z,λT∈Ω,Tυ≔fx−λhz+λx−z.Then, formula (4) is rewritten in the following compact form:(6)υ−υ∗TTυ∗≥0,∀υ∈S,where(7)S=X×Z×Rn.Throughout, we make some reasonable assumptions to guarantee that the algorithm works properly:(a)
fx and hz are monotone and Lipschitz continuous.(b)
Projection onX and Z is not difficult to solve.


## 3. New Inexact Parallel Splitting Method (NIPSM)

For the convenience of later analysis, we denote(8)υk=xk,zk,λkT,υ˜k=x˜k,z˜k,λ˜kT,M=βI000βI0001βI.Now we present implementation steps of the algorithm NIPSM.Step 0. Let ε>0, υ0=x0,z0,λ0, ν∈0,1, γ∈1,2.Step 1. Generate an iterative sequence by the following method.Solvex˜k via(9)x−x˜kTfxk−λk−βxk−zk+βx˜k−xk≥0,where(10)fxk−fx˜k≤2−22vβxk−x˜k.Solvez˜k via(11)z−z˜kThzk+λk−βxk−zk+βz˜k−zk≥0,where(12)hzk−hz˜k≤2−22vβzk−z˜k.Updateλ˜k via(13)λ˜k=λk−βx˜k−z˜k.Step 2. The contraction step:FormΙ:(14)υΙk+1=υk−αkl1υk,υ˜k,where(15)l1υk,υ˜k=Mυk−υ˜k+fx˜k−fxkhz˜k−hzk0,formΠ:(16)υΠ=PSυk−αkl2υk,υ˜k,where(17)l2υk,υ˜k=Tυ˜k+βxk−x˜k−zk−z˜kzk−z˜k−xk−x˜k0,where(18)αk=γψ1υk,υ˜kl1υk,υ˜k2,(19)ψ1υk,υ˜k=υk−υ˜kTl1υk,υ˜k+λk−λ˜kTxk−x˜k−zk−z˜k.Remark 1.
β that satisfies the conditions can be obtained because of the Lipschitz continuous property of fx and hz.Remark 2.
αk is a proper step length of correction step of the algorithm, and we will prove that later on.


## 4. Convergence Analysis of the Proposed NIPSM

Lemma 1.
For a given pointυk=xk,zk,λk and υ∗∈S∗, let υ˜k=x˜k,z˜k,λ˜k generated by NIPSM satisfy(20)υ−υ˜k,l2υ,υ˜k≥υ−υ˜k,l1υ,υ˜k,∀υ∈S.Proof.
Combining (9)–(13) Lemma 1 can be obtained immediately. Here, we do not give a detailed proof, and one can refer to the proof in reference [22].Lemma 2.
For a given pointυk=xk,zk,λk, ψ1υk,υ˜k defined as (19) satisfies(21)ψ1υk,υ˜k≥2−221−νυk−υ˜kM2.Proof.
It follows from Cauchy–Schwarz inequality, and we know that(22)υk−υ˜kTfx˜k−fxkhz˜k−hzk0≥−2−22vβxk−x˜k2+zk−z˜k2,λk−λ˜kTxk−x˜k≥−122βxk−x˜k2+12βλk−λ˜k2,λ˜k−λkTzk−z˜k≥−122βzk−z˜k2+12βλk−λ˜k2.
From the definition ofψ1υk,υ˜k in (19) and the above formula, the conclusion is clearly established.Lemma 3.
For a given pointυk=xk,zk,λk and υ∗∈S∗, the sequences υ˜k generated by (9)–(13) satisfy(23)υk−υ∗Tl1υk,υ˜k≥ψ1υk,υ˜k.Proof.
Byx∗−z∗=0 and υ∗∈S∗, we have(24)υk−υ∗,βxk−x˜k−zk−z˜kzk−z˜k−xk−x˜k0=λk−λ˜kTxk−x˜k−zk−z˜k.
Then,(25)υk−υ∗Tl1υk,υ˜k=υk−υ˜kTl1υk,υ˜k+υ˜k−υ∗Tl1υk,υ˜k≥υk−υ˜kTl1υk,υ˜k+υ˜k−υ∗Tl2υk,υ˜k≥ψ1υk,υ˜k.
The second inequality is obtained because the mappingTυ is monotone on S.
It follows from Lemma3, and we know that −l1υk,υ˜k is a descent direction of 1/2υk−υ∗2,υ∗∈S. Next we will show how to choose an optimal step size.
From (15), one can obtain that(26)l1υk,υ˜k2≤2Mυk−υ˜k2+2fx˜k−fxk2+2hz˜k−hzk2≤2ƛ2υk−υ˜k2+3−22ν2β2xk−x˜k2+zk−z˜k2≤2ƛ2υk−υ˜k2+3−22ν2ƛ2υk−υ˜k2≤2+3−22ν2ƛ2υk−υ˜k2,where ƛ represents the eigenvalues of matrix M and we know that ƛ>0.
For the convenience of analysis, we denoteC=2+3−22ν2. It follows that(27)l1υk,υ˜k2≤Cƛ2υk−υ˜k.
It follows from Lemma2 that(28)αk≥2−21−ν2Cƛ.
In order to explain why we chooseαk as defined in (18), we let(29)υk+1α=υk−αl1υk,υ˜k,ϑα=υk−υ∗2−υk+1α−υ∗2.Lemma 4.
Letυ∗=x∗,z∗,λ∗ be an arbitrary point in S∗. We have(30)ϑα≥qα=2αψ1υk,υ˜k−2α2Cƛ2υk−υ˜k2.Proof.
(31)ϑα=υk−υ∗2−υk+1α−υ∗2=2αυk−υ∗,l1υk,υ˜k−α2l1υk,υ˜k2≥2αψ1υk,υ˜k−α2Cƛ2υk−υ˜k2=qα.
Lemma4 shows that we should choose (18). In order to speed up iteration of the algorithm, in the actual calculation, we generally take a relaxation factor γ∈1,2.Theorem 1.
The sequenceυk is generated by NIPSM and υ∗∈S∗. Then, the following conclusion holds:(32)υk+1−υ∗2≤υk−υ∗2−γ2−γ1−ν23−22Cυk−υ˜k2.Then,(33)limk⟶∞υk−υ˜k=0,and algorithm converges to υ∞, which is a solution of (1).Proof.
By the previous lemma, we know that(34)υk−υ∗2−υk+1−υ∗2≥2αψ1υk,υ˜k−α2l1υk,υ˜k2=γ2−γαψ1υk,υ˜k≥γ2−γ1−ν23−22Cυk−υ˜k2.
Therefore, assertion (22) is proved, and we have(35)γ2−γ1−ν23−22Climk=0υk−υ˜k2≤υ0−υ∗2.
Theorem1 states that the algorithm will terminate in finite step and converge to a solution of model (1).


## 5. Numerical Results

Consider the matrix correction problem:(36)min12X−DF2s.t.X∈Q+n∩QB,where(37)Q+n=A∈Rn×n|AT=A,A≥0,QB=A∈Rn×n|AL≤A≤AV,where AL and AV are two given n×n symmetric matrices.Obviously, problem (36) can be rewritten in the following form:(38)min12X−D2+12Z−D2s.t.X−Z=0X∈Qn+,Z∈QB.We chooseβ=1.2,γ=1.6,Y0=0,λ0=0, and tol≔10−5, and n denotes matrix dimensions. Table 1 lists the results of the number of iterations and the CPU time of both the inexact projection and contraction method in literature [22] (IPCM) and the proposed method (NIPSM).Table 1
Iteration number and CPU time comparison of IPCM and NIPSM.
nIPCMNIPSMNoCPUNoCPU100660.37380.27200842.34471.72300925.93544.0550011726.996318.32800141142.717381.45


## 6. Conclusion

In this paper, we propose an inexact parallel splitting algorithm with two separable operators. Numerical results show that our proposed method is efficient, and the larger the scale, the more obvious the advantage. Of course, we can also apply the parameter adjustment technique in reference [21] to the algorithm of this paper. How to extend this algorithm to convex optimization problems with more than two separable operators will be our next research direction.



---

*Source: 8054688-2022-02-23.xml*