# A Modified Scaled Spectral-Conjugate Gradient-Based Algorithm for Solving Monotone Operator Equations

Authors: Auwal Bala Abubakar; Kanikar Muangchoo; Abdulkarim Hassan Ibrahim; Sunday Emmanuel Fadugba; Kazeem Olalekan Aremu; Lateef Olakunle Jolaoso
Journal: Journal of Mathematics
 (2021)

---

## Abstract

This paper proposes a modified scaled spectral-conjugate-based algorithm for finding solutions to monotone operator equations. The algorithm is a modification of the work of Li and Zheng in the sense that the uniformly monotone assumption on the operator is relaxed to just monotone. Furthermore, unlike the work of Li and Zheng, the search directions of the proposed algorithm are shown to be descent and bounded independent of the monotonicity assumption. Moreover, the global convergence is established under some appropriate assumptions. Finally, numerical examples on some test problems are provided to show the efficiency of the proposed algorithm compared to that of Li and Zheng.


---

## Body

## 1. Introduction

We desire in this work to propose an algorithm to solve the problem:(1)Fx=0,x∈C,where F:Rn⟶Rn is monotone and Lipschitz continuous and C⊆Rn is nonempty, closed, and convex.Solving problems of form (1) are becoming interesting in recent years due to its appearance in many areas of science, engineering, and economy, for example, in forecasting of financial market [1], constrained neural networks [2], economic and chemical equilibrium problems [3, 4], signal and image processing [5, 6], phase retrieval [7, 8], power flow equations [9], nonnegative matrix factorisation [10, 11], and many more.Some notable methods for finding solution to (1) are: Newton’s method, quasi-Newton method, Gauss–Newton method, Levenberg–Marquardt method, and their variants [12–15]. These methods are prominent due to their fast convergence property. However, their convergence is local, and they require computing and storing of the Jacobian matrix at each iteration. In addition, there is a need to solve a linear equation at each iteration. These and other reasons make them unattractive especially for large-scale problems. To avoid the above drawbacks, methods that are globally convergent and also do not require computing and storing of the Jacobian matrix were introduced. Examples of such methods are the spectral (SG) and conjugate (CG) gradient methods. However, SG and CG methods for solving (1) are usually combined with the projection method proposed in [16]. For instance, Zhang and Zhou [17] extended the work of Birgin and Martinéz [18] for unconstrained optimization problems by combining it with the projection method and proposed a spectral gradient projection-based algorithm for solving (1). Dai et al. [19] extend the modified Perry’s CG method [20] for solving unconstrained optimization problem to solve (1) by combining it with the projection method. Liu and Li [21] incorporated the Dai-Yuan (DY) [22] CG method with the projection method and proposed a spectral Dai-Yuan (SDY) projection method for solving nonlinear monotone equations. The method was shown to be globally convergent under appropriate assumptions. Furthermore, to popularize and boost the efficiency of the DY CG method, Liu and Feng [23] proposed a spectral DY-type CG projection method (PDY), where the spectral parameter is derived such that the direction is descent. It is worth mentioning that all the methods mentioned above require the operator in (1) to be monotone. Recently, Li and Zheng [24] proposed scaled three-term derivative-free methods for solving (1). The method is an extension of the method proposed by Bojari and Eslahchi [25]. However, to establish the convergence of the method, Li and Zheng assume that the operator is uniformly monotone which is a stronger condition. Some other related ideas on spectral gradient-type and spectral conjugate gradient-type methods for finding solution to (1) were studied in [26–41] and references therein.In this work, motivated by the strong condition imposed on the operator by Li and Zheng [24], we seek to relax the condition on the operator from uniformly monotone to monotone. This is achieved by modifying the two search directions defined by Li and Zheng. In addition, the global convergence is established under the assumption that the operator is monotone and Lipschitz continuous. Numerical examples to support the theoretical results are also given.Notations: unless or otherwise stated, the symbol⋅ stands for Euclidean norm on Rn. Fxk is abbreviated to Fk. Furthermore, PC⋅ is the projection mapping from Rn onto C given by PCx=argminx−y:x∈Rn,y∈C, for a nonempty closed and convex set C⊆Rn.


## 2. Motivation and Algorithm

In this section, we will begin by recalling a three-term spectral-conjugate gradient method for solving (1). Given an initial point x0, the method generates a sequence xk via the following formula:(2)xk+1=xk+αkdk,k=0,1,2,…,where xk+1 and xk are the current and previous points, respectively. αk is the stepsize obtained via a line search and dK is the search direction defined as(3)d0≔−F0,dk≔−θkFk+βkdk−1+γkyk−1,k≥1,where θk, βk, and γk are parameters and yk−1=Fk−Fk−1.Based on the three-term direction above, we will propose a modified scaled three-term derivative-free algorithms for solving (1). The algorithms are a modification of the two algorithms proposed by Li and Zheng [24]. The aim of the modification is to relax the uniformly monotone assumption on the operator. The search directions defined in [24] were shown to be bounded under the uniformly monotone assumption. Our main interest is to modify the search directions defined in [24] and prove their boundedness without requiring the uniformly monotone assumption. The directions in [24] are defined as follows:STDF1:(4)dk≔−μ1Fk+1dk−1Tyk−1μ1FkTyk−1−ck−1yk−12dk−1+2−μ1ck−1yk−1.STDF2:(5)dk≔−μ1Fk+1dk−1Tyk−1μ1FkTyk−1−c¯k−1yk−12−μ2FkTsk−1dk−1+2−μ1c¯k−1yk−1,where(6)ck−1=FkTdk−1dk−1Tyk−1,c¯k−1=FkTdk−1dk−1Tyk−1,yk−1=Fk−Fzk−1,sk−1=zk−1−xk−1,zk−1=xk−1+αk−1dk−1,1<μ1≤2,μ2≥0.To obtain a lower bound for the termdk−1Tyk−1, Li and Zheng used the uniformly monotone assumption. So, in order to relax this condition, we replace the term dk−1Tyk−1 in the directions defined by (4) and (5) with dk−1Twk−1. In addition, we replace ck−1 and c¯ in (4) and (5) with c˜k−1, sk−1 in (5) with dk−1. Hence, we define the new directions as follows:PSTDF1:(7)dk≔−μ1Fk+1dk−1Twk−1μ1FkTyk−1−c˜k−1yk−12dk−1+2−μ1c˜k−1yk−1.PSTDF2:(8)dk≔−μ1Fk+1dk−1Twk−1μ1FkTyk−1−c˜k−1yk−12−μ2FkTdk−1dk−1+2−μ1c˜k−1yk−1.where(9)c˜k−1=FkTdk−1dk−1Twk−1,yk−1=Fk−Fk−1,wk−1=yk−1+ℓk−1dk−1,ℓk−1=1+max0,−dk−1Tyk−1dk−12.Remark 1.
(10)dk−1Twk−1≥dk−1Tyk−1+dk−12−dk−1Tyk−1=dk−12.
From (10), a lower bound for the term dk−1Twk−1 is obtained without any assumption on the operator F.
LetSolC,F be the solution set of (1) and assume that the following holds.Assumption 1.
The constraint setC is nonempty, closed, and convex.Assumption 2.
The operatorF is monotone, that is, ∀x1,x2∈Rn:(11)Fx1−Fx2T,x1−x2≥0.Assumption 3.
The operatorF is L-Lipschitz continuous on ℝn, that is, ∀x1,x2∈Rn, L>0,(12)Fy1−Fy2≤Lx1−x2.
In the following algorithm, we generate approximate solutions to problem (1) under Assumptions 1–3 Algorithm 1.Algorithm 1.
PSTDF.Input. Choose an initial guess x0∈C, ϑ>0, 0<ρ<1, 1<μ1≤2, μ2≥0, t>0, tol>0 and k≔0.Step 1. If Fk≤tol, terminate. Else move to Step 2.Step 2. Compute dk using (7) or (8).Step 3. Compute(13)zk=xk+αkdk,αk=ϑρi, for i=0,1,…, where i is the least nonnegative integer satisfying(14)−FzkTdk≥tαkdk2.Step 4. If zk∈C and Fzk≤tol, then stop. Else, compute(15)xk+1≔PCxk−ηkFzk,where(16)ηk≔FzkTxk−zkFzk2.Step 5. Let k=k+1 and repeat from Step 1.


## 3. Theoretical Results

In this section, we will establish the convergence analysis of the proposed algorithm. However, we require the following important lemmas. The following lemma shows that the proposed directions are descent.Lemma 1.
The search directions defined by (7) and (8) satisfy the sufficient descent condition.Proof.
Multiplying both sides of (7) by FkT, we have(17)FKTdk=−μ1Fk2+1dk−1Twk−1μ1FkTyk−1−ck−1yk−12FKTdk−1+2−μ1ck−1FKTyk−1=−μ1Fk2+μ1FKTdk−1FkTyk−1dk−1Twk−1−yk−12FKTdk−12dk−1Twk−12+2FKTdk−1FKTyk−1dk−1Twk−1−μ1FKTdk−1FKTyk−1dk−1Twk−1=−μ1Fk2−yk−12FKTdk−12dk−1Twk−12+2FKTdk−1FKTyk−1dk−1Twk−1=−μ1−1Fk2−Fk−FKTdk−1dk−1Twk−1yk−12≤−μ1−1Fk2.
Also, multiplying both sides of (8) by FkT, we have(18)FkTdk=−μ1Fk2+1dk−1Twk−1μ1FkTyk−1−ck−1yk−12−μ2FkTdk−1FkTdk−1+2−μ1ck−1FKTyk−1,=−μ1Fk2+μ1FKTdk−1FkTyk−1dk−1Twk−1−yk−12FKTdk−12dk−1Twk−12−μ2FkTdk−12dk−1Twk−1+2FKTdk−1FKTyk−1dk−1Twk−1−μ1FKTdk−1FKTyk−1dk−1Twk−1=−μ1Fk2−yk−12FKTdk−12dk−1Twk−12+2FKTdk−1FKTyk−1dk−1Twk−1−μ2FKTdk−12dk−1Twk−1=−μ1−1Fk2−Fk−FKTdk−1dk−1Twk−1yk−12−μ2FKTdk−12dk−1Twk−1≤−μ1−1Fk2.
Hence, for allk, the directions defined by (7) and (8) satisfy(19)FKTdk≤−μ1−1Fk2.
The lemma below shows that the linesearch (14) is well-defined and the stepsize is bounded away from zero.Lemma 2 (see [5]).
Suppose Assumptions1–3 are satisfied. If dk, zk, and xk are sequences defined by (7), (13), and (15), respectively, then(i)
For allk, there is αk=ϑρi satisfying (14) for some i∈ℕ∪0 and ∀k≥0.(ii)
αk obtained via (14) satisfies(20)αk>maxϑ,ρFk2L+tdk2.Lemma 3 (see [5]).
Suppose Assumptions1–3 are fulfilled, then the sequences zk and xk defined by (13) and (15) are bounded. Furthermore,(21)limk⟶∞xk−zk=limk⟶∞αkdk=0.Lemma 4 (see [5]).
From Lemma3, we have(22)xk+1−x¯2≤xk−x¯2.Remark 2.
Sincexk is bounded from Lemma 3 and F is continuous from Assumption 3, Fk is also bounded. That is, there exists c1,c2>0 such that, for all k,(23)xk≤c1,Fk≤c2.
All are now set to establish the convergence of the proposed algorithm.Theorem 1.
Suppose Assumptions1 and 2 are satisfied. If xk is a sequence defined by (15), then(24)liminfk⟶∞Fk=0.
Furthermore, the sequencexk converges to a solution of problem (1).Proof.
Suppose thatliminfk⟶∞Fk≠0, then there is a positive constant ν>0 such that, for all k≥0,(25)Fk≥ν.
By (17), (18), and the Cauchy–Schwartz inequality, we have that, for all k≥0,(26)dk≥μ1−1Fk≥μ1−1ν.
To complete the proof of the theorem, we need to show that the search directiondk defined by (7) and (8) are bounded.
Fork=0, we have(27)d0=F0≤c2.
Now fork≥1, using (7), (10), (12), and (26), we have(28)dk≤μ1Fk+dk−1dk−1Twk−1μ1Fkyk−1+Fkdk−1dk−1Twk−1yk−12+2Fkdk−1yk−1dk−1Twk−1+μ1Fkdk−1yk−1dk−1Twk−1≤μ1Fk+2μ1+1Lxk−xk−1dk−1+Lxk−xk−1dk−12Fk≤mu1Fk+2μ1+1Lxk+xk−1dk−1+Lxk+xk−1dk−12Fk≤μ1c2+2μ1+1L2c1μ1−1ν+L2c1μ1−1ν2c2≤μ1c2+4c1Lμ1+1μ1−1ν+4c12L2μ1−12ν2c2.
Similarly, from (8),(29)dk≤μ1+μ2Fk+2μ1+1Lxk−xk−1dk−1+Lxk−xk−1dk−12Fk,≤μ1+μ2c2+4c1Lμ1+1μ1−1ν+4c12L2μ1−12ν2c2.
LettingM1=μ1c2+4c1Lμ1+1/μ1−1ν+4c12L2/μ1−12ν2c2 and M2=μ1+μ2c2+4c1Lμ1+1/μ1−1ν+4c12L2/μ1−12ν2c2, then for all k,(30)dk≤M2,since M2>M1.
Multiplying (20) by dk, we get(31)αkdk≥maxϑdk,ρFk2L+tdk≥maxtμ1−1ν,μμ1−12ν2L+tM>0.
This contradicts (21) and hence liminfk⟶∞Fk=0.
BecauseF is a continuous function and (24) holds, then the sequence xk has some accumulation point say x¯ for which Fx¯=0, that is, x¯ is a solution of (1). From (22), it holds that xk−x¯ converges, and since x¯ is an accumulation point of xk, xk converges to x¯.


## 4. Numerical Examples on Monotone Operator Equations

This segment of the paper would demonstrate the computational efficiency of the PSTDF algorithm relative to STDF algorithm [24]. For PSTDF algorithm, we have PSTDF1 which corresponds to the direction defined by (7) and PSTDF2 corresponding to the one defined by (8). Similarly, for the STDF algorithm, we have STDF1 and STDF2 corresponding to (4) and (5), respectively. The parameters chosen for the implementation of the PSTDF algorithm are ϑ=1,μ1=1.9,μ2=0.8,ρ=0.8, and t=10−4. The parameters for STDF algorithm are chosen as reported in [24]. The metrics considered are the number of iteration (NOI), number of function evaluations (NFE), and the CPU time (TIME). We used eight test problems with dimension n=1000, 5000, 10,000, 50,000, and 100,000 and five initial points x1=0.1,0.1,…,0.1T,x2=0.2,0.2,…,0.2T,x3=0.5,0.5,…,0.5T,x4=1.5,1.5,…,1.5T,x5=2,2,…,2T. The algorithms were coded in MATLAB R2019a and run on a PC with Intel (R) Core (TM) i3-7100U processor with 8 GB RAM and CPU 2.40 GHz. The iteration process is stopped whenever Fxk≤10−5. Failure is declared if this condition is not satisfied after 1000 iterations.Table1 consists of the test problems considered, where the function F is Fx=f1x,f2x,…,fnxT and x=x1,x2,…,xnT.Table 1
List of test problems with references.
S/NProblem and reference1Modified exponential function 2 [42]2Logarithmic function [42]3Nonsmooth function [43]4Strictly convex function I [42]5Tridiagonal exponential function [44]6Nonsmooth function [45]7Problem 4 in [46]8Problem 9 in [32]The result of the experiments in Tabular form can be found in the linkhttps://documentcloud.adobe.com/link/review?uri=urn:aaid:scds:US:77a9a900-2156-4344-a9d9-b42e3a3dc8e5. It can be observed from the results that the algorithms successfully solved all the problems considered without a single failure. However, to better illustrate the performance of each algorithm, we employ the Dolan and Moré [47] performance profiles and plot Figures 1–3. Figures 1–3 represent the performance of the algorithms based on NOI, NFE, and TIME, respectively. In terms of NOI (Figure 1), the best performing algorithm is PSTDF2 with 70% success, followed by PSTDF1 with 51% success. STDF1 and STDF2 record less than 10% success each. Based on NFE (Figure 2), the best performing algorithm is PSTDF1 with around 42% success, followed by PSTDF2 with almost 40% success. STDF1 and STDF2 record 20% and around 15% success, respectively. Lastly, in terms of TIME (Figure 3), PSTDF2 performs better with around 50% success, followed by PSTDF1 with more than 30% success. STDF1 and STDF2 record around 20% and 5% success, respectively. Overall, we can conclude that PSTDF1 and PSTDF2 outperform STDF1 and STDF2 based on the metrics considered.Figure 1
Performance profiles for the number of iterations (NOI).Figure 2
Performance profiles for the number of function evaluations (NFE).Figure 3
Performance profiles for the CPU time (in seconds).


## 5. Conclusions

In this paper, a modified scaled algorithm based on the spectral-conjugate gradient method for solving nonlinear monotone operator equations was proposed. The algorithm replaces the stronger assumption of uniformly monotone on the operator in the work of Li and Zheng (2020) with just monotone, which is weaker. Interestingly, the search directions were shown to be descent independent of line search and also without monotonicity assumption (unlike in the work of Li and Zheng). Furthermore, the convergence results were established under monotonicity and Lipschitz continuity assumptions on the operator. Numerical experiments on some benchmark problems were conducted to illustrate the good performance of the proposed algorithm.



---

*Source: 5549878-2021-04-26.xml*