On the Picard-Mann approach for hybridizing the double direction method for solving a system of nonlinear equations.

Subject Areas : Non linear Programming

Abubakar Halilu ^{1 *} , Aliyu kiri ² , Mohammed Waziri ³

1 - Sule Lamido University, Kafin Hausa
2 - Department of Mathematics, Bayero University, Kano
3 - Department of Mathematics, Bayero University, Kano

Received: 2021-12-15 Accepted : 2022-07-06 Published : 2022-03-01

Keywords: Acceleration parameter, Jacobian matrix, Double direction method, Picard-Mann process,

Abstract :

In this article, the improvement of the numerical performance of the iterative scheme presented by Halilu and Waziri in [5] is considered. This is made possible by hybridizing it with Picard-Mann hybrid iterative process. In addition, the step length is calculated using the inexact line search technique. Under the preliminary conditions, the proposed method's global convergence is established. The numerical experiment shown in this paper depicts the efficiency of the proposed method, which improved the results than the double direction method [5], existing in the literature.

References:

Abdullahi, H., Halilu, A. S., & Waziri, M. Y. (2018). A modified conjugate gradient method via a double direction approach for solving large-scale symmetric nonlinear systems. Journal of Numerical Mathematics and Stochastics, 10(1), 32-44.

Dennis Jr, J. E., & Schnabel, R. B. (1983). Numerical methods for unconstrained optimization and nonlinear equations prentice-hall series in computation. Mathematics, Englewood Cliffs, NJ.

Dolan, E. D., & Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2), 201-213.

Halilu A.S. and Waziri M.Y.: Enhanced matrix-free method via double step length approach for solving systems of nonlinear equations. Int J app Math Res. 2017; 6:147–156 .

Halilu, A. S., & Waziri, M. Y. (2017). A transformed double step length method for solving large-scale systems of nonlinear equations. Journal of Numerical Mathematics and Stochastics, 9(1), 20-23.

Halilu, A. S., & Waziri, M. Y. (2018). An improved derivative-free method via double direction approach for solving systems of nonlinear equations. Journal of the Ramanujan Mathematical Society, 33(1), 75-89.

Halilu, A. S., & Waziri, M. Y. (2020). Solving systems of nonlinear equations using improved double direction method. Journal of the Nigerian Mathematical Society, 39(2), 287-301.

Halilu, A. S., Waziri, M. Y., & Musa, Y. B. (2020). Inexact double step length method for solving systems of nonlinear equations. Statistics, Optimization & Information Computing, 8(1), 165-174.

Khan, S. H. (2013). A Picard-Mann hybrid iterative process. Fixed Point Theory and Applications, 2013(1), 1-10.

Li, D., & Fukushima, M. (1999). A globally and superlinearly convergent gauss--Newton-based BFGS method for symmetric nonlinear equations. SIAM Journal on numerical Analysis, 37(1), 152-172.

Petrović, M. J. (2015). An accelerated double step size model in unconstrained optimization. Applied Mathematics and Computation, 250, 309-319.

Petrović, M. J., & Stanimirović, P. S. (2014). Accelerated double direction method for solving unconstrained optimization problems. Mathematical Problems in Engineering, 2014.

Petrovic´, M.J., Stanimirovic´, P.S., Kontrec, N., Mladenovic´, J. Hybrid Modification of accelerated double direction method. Math. Probl. Eng. 2018; Article D 1523267: 8 pages. doi.org/10.1155/2018/1523267.

Yuan, G., & Lu, X. (2008). A new backtracking inexact BFGS method for symmetric nonlinear equations. Computers & Mathematics with Applications, 55(1), 116-129.

Yusuf, M. W., June, L. W., & Hassan, M. A. (2011). Jacobian-free diagonal Newton’s method for solving nonlinear systems with singular Jacobian. Malaysian Journal of Mathematical Sciences, 5(2), 241-255.

Full-Text:



Islamic Azad University Rasht Branch ISSN: 2588-5723        E-ISSN:2008-5427

Optimization Iranian Journal of Optimization Volume 14, Issue 1, 2022, 27-37 Research Paper

 

 

                                        Online version is available on: : www.ijo.rasht.iau.ir

 

On the Picard-Mann approach for hybridizing the double direction method for solving a system of nonlinear equations

 

Aliyu Ibrahim Kiri1, Mohammed Yusuf Waziri2, and Abubakar Sani Halilu3*

 

1,2 Department of Mathematical Sciences, Bayero University, Kano, Nigeria.

3 Department of Mathematics, Sule Lamido University, Kafin Hausa, Nigeria.

2,3 Numerical Optimization Research Group, Bayero University, Kano, Nigeria.

 

 

Revise Date: 01 March 2022          Abstract

Keywords: Acceleration Parameter Jacobian Matrix  Double Direction Method Picard-Mann Process

Accept Date: 06 July 2022           In this article, the improvement of the numerical performance of the iterative scheme presented by Halilu and Waziri (2018) is considered. This is made possible by hybridizing it with Picard-Mann hybrid iterative process. In addition, the step length is calculated using the inexact line search technique. Under the preliminary conditions, the proposed method’s global convergence is established. The numerical experiment shown in this paper depicts the efficiency of the proposed method, which improved the results than the double direction method (Halilu & Waziri, 2018), existing in the literature.

 

*Correspondence E‐mail: [e-mail]

 

 

INTRODUCTION

   Systems of nonlinear equations usually arise in the areas of human endeavor such as sciences and engineering. Researchers are tasked with developing efficient and robust iterative methods to solve them. Typically, a system of nonlinear equations is represented as

 

Where  is nonlinear map. Throughout this paper, the space  denote the n- dimensional real space, is the Euclidean norm and  Some iterative approaches for solving these problems include derivative-free methods Halilu & Waziri, 2017, 2018, 2020; Abdullahi, Halilu, & Waziri, 2018), and Newton and quasi-Newton methods (Dennis & Schnabel, 1983; Waziri, Leong, & Hassan, 2011; Yuan & Lu, 2008). However, Newton’s method is prominent due to its attractive features, such as easy implementation and rapid convergence. However, the method requires the computation as well as storage of Jacobian matrix at each iteration and generates a sequence of points using the recursive formula:

where  and         is a step length. The Newton’s search direction dk is determined by solving the following linear system of equations,

 

where, is the Jacobian matrix of F at xk. However, in Newton’s method, the derivative F′ is computed at each iteration, which may be unavailable or could not be obtained precisely. In this case, Newton’s method cannot be applied directly. For this reason, quasi-Newton’s methods were developed to replace the Jacobian matrix or its inverse with an approximation which can be updated at each iteration (Yuan & Lu, 2008; Li & Fukushima, 1999), and its search direction is given by

 

where Bk is n × n matrix that approximate the Jacobian of F at xk. Moreover, (1) can be obtained from an unconstrained optimization problem (Fukishima, 1999). Sup-pose f be a merit function defined by

 

Then the problem of nonlinear equations (1) is analogous to the following problem of global optimization

 

Newton and quasi-Newton’s methods require the computation of the Jacobian matrix or its approximation at each iteration, despite the attractive characteristics of these methods. Therefore, they are not ideal for solving large-scale problems because they require massive matrix storage at each iteration which is costly in numerical experiments. Matrix-free methods are proposed to overcome these problems. The double direction method is among the successful matrix-free methods (Petrovic & Stanimirovic, 2014), that generates a sequence of iterates via

 

where xk+1 is the current iterate, xk is the previous iterate, while bk and dk are search directions respectively. The rationale behind double direction method is that, there are two corrections in the scheme (6), if one correction fails during iterative process then the second one will correct the system.

In 2014, Petrovic and Stanimirovic proposed a double direction method for solving

unconstrained optimization problems. In their work, an approximation to Hessian matrix is obtained via acceleration parameter γk > 0, i.e.,

 

where I is an identity matrix. The sequence of iterates is generated using (6).

{xk} Petrovic (2015) further improves the performance of double direction, where the double step length scheme for the unconstrained optimization problem is presented as:

 

where, αk and βk are two different step lengths. The Numerical results reported in Petrovic (2015) have shown that the proposed method is quite effective compared to the double direction method in Petrovic and Stanimirovic (2014), Because it has the number of iterations and CPU time than the compared method (Petrovic & Stanimirovic, 2014), Moreover, to improve the convergence properties and numerical results of the double direction methods, Petrovi­c’ et al. (2018) hybridized the double direction method for unconstrained optimization problem in (Petrovic & Stanimirovic, 2014), with Picard-Mann hybrid iterative process proposed by Khan in Safeer (2013). The Picard-Mann hybrid iterative process is defined as three relations:

Definition 1. The Picard-Mann hybrid iterative process is defined as three relations:

 

where T: Ω→ Ω is a mapping defined on nonempty convex subset Ω of a normed space E, yk − and xk are sequences determined by the iterations in (9) and (10), and is the sequence of {ηk} positive numbers in (0,1).

In this paper, ηk denotes the correction parameter. Since the research of derivative-free double direction methods for solving systems of nonlinear equations is scarce in the literature, this motivated Halilu and Waziri (2018) to use the scheme in (6) and proposed a derivative-free method via double direction approach for solving system of nonlinear equations. The method is proved to be globally convergent by assuming that the Jacobian of F is bounded and positive definite. Abdullahi et al. [9] further improved the performance of the double direction scheme where they modified the idea in in Halilu and Waziri (2018) based on conjugate gradient approach to solve symmetric nonlinear equations. The method converged globally using the derivative-free line search proposed by Li and Fukushima in (Li & Fukishima, 1999). Recently, Halilu and Waziri (2020) solved the system of nonlinear equations by improving the double direction iteration approach in (6). The global convergence of the method was established under some mild conditions, and the numerical experiments demonstrated in the paper showed that the proposed method is very efficient.

Motivated by the hybridization method presented in Petrovic et al. (2018), This article is aimed at

hybridizing the double direction method in Halilu and Waziri (2018) with the Picard-Mann hybrid iterative process proposed by Khan (2013). The paper is organized as follows. In the next section, we will present the algorithm of the proposed method. Section 3 presents the proposed algorithm’s convergence analysis. Section 4 lists some numerical experiments. The article concluded in section 4.

MAIN RESULT

Let us consider the derivative-free double direction method in in Halilu and Waziri (2018). The method developed a derivative-free method for solving systems of nonlinear equations via

 

where I is an identity matrix and γk > 0 is an acceleration parameter. The method in Halilu and Waziri (2018) produces a sequence of iterates xk such that  where and the direction dk is given as

 

The acceleration parameter is obtained by using first-order Taylor’s expansion as

 

where

Although the method of Halilu and Waziri (2018) has strong convergence properties, its numerical perfor- mance is weak when γk approaches or is equal to 1. For this reason, we are motivated to propose a hybrid method with good numerical results. To define a hybrid form of the method in Petrovic (2014), the mapping T in definition (1) is assumed to be defined by an improved double direction method as  By this assumption and the definition (1) we have

 

From (14) and (15) we obtain the iterative scheme, 

 

where, tk = (ηk + 1) ∈ (1,2) is a correction parameter. we can easily show that, the search direction in (16) is defined as

 

Next, the proposed method algorithm is specified as follows:

 

CONVERGENCE

Analysis We present how the proposed Algorithm 1 (HDDPM) converges globally in this section. To begin, let’s define the level set.

 

Assumption 3.1 However, we state the following assumptions:

1. There exists x∗ n∈R such that F(x∗) = 0.

2. F is continuously differentiable in some neighborhood say Q of x∗ containing Ω.

3. The Jacobian of F is bounded and positive definite on Q. i.e., there exist positive constants H > h > 0 such that

 

and

 

Remark 2. We make the following remark:

Assumption 3.1 implies that there exist constants H > h > 0 such that

 

Since t−1 γk I approximates along sk, the following assumption can be made.

Assumption 3.3 t− 1 γk I is a good approximation to  , i.e.,

 

where, ε∈ (0,1) is a small quantity [4].

Lemma 4. Suppose Assumption 3.3 holds, and let xk be generated by Algorithm 1. Then dk { xk }is a sufficient descent direction for f (xk) at xk i.e.,

 

Proof. From (5), (12), and (25), we have

 

b y Chauchy-Schwarz we have,

 

Since ϵ ϵ(0,1), taking c = 1− ϵ, this lemma is true.

We can conclude from Lemma 3.4 that the norm function f (xk) is a descent along k,which means that  is true.

Lemma 5. Suppose that Assumption 3.1 holds and let {xk} be generated by Algorithm 1. Then {xk} ⊂ Ω.

Proof. From Lemma 3.4, we have ∥Fk+1∥ ≤ ∥Fk∥. Furthermore, for all k,

∥Fk+1∥ ≤ ∥Fk∥ ≤ ∥Fk−1∥ ≤ ... ≤ ∥F0∥.

This means that {xk} ⊂ Ω. 

Lemma 6. Suppose Assumption 3.1 holds and {xk} be generated by Algorithm 1. Then there exists a constant m > 0 such that for all k,

 

Proof. By mean-value theorem and (22),

 

Using  is always generated by the update formula (??). herefore,≥∥∥γk+1­I inherits the positive definiteness of γk­I. From Lemma 3 and (??), the following inequality holds.

 

Lemma 7. Suppose that Assumption 3.1 holds and {xk} is generated by Algorithm 1. Then we have

 

and

 

Proof. From (18) for all k > 0

 

By summing the above inequality, we have

From the level set and the fact that  satisfies (19), then the series

This implies (31). Using the same logic as above, but this time with  on the left, w­e obtain (32).

Lemma 8. Suppose Assumption 3.1 holds and let {xk} be generated by Algorithm 1. Then there exists a constant M > 0 such that for all k > 0, Proof. From (12) and (13) w­e have

 

Proof From (12) and (13) we have

 

Takingwe have (35).

Theorem 9. Suppose that Assumption 3.1 holds and {xk} be generated by Algorithm 1. Assume further for all k > 0,

 

where λ is some positive constant. Then

 

Proof. From Lemma 8 we have (35). Also, from (31) and the boundedness of {∥ dk ∥}, we have

 

from (37) and (39) we have

 

Also, from (12) we have,

 

Since

 

 

Then,

 

Therefore, from (42) we have,

 

As a result,

 

Hence,

 

The proof is completed.

NUMERICAL EXPERIMENTS

In this section, we test the efficiency and robustness of our proposed method (HDDPM) using the following existing methods in the literature:

• An improved derivative-free method via double direction approach for solving

systems of nonlinear equations (IDFDD) (Halilu and Waziri, 2018).

The computer codes utilized were written in Matlab 9.4.0 (R2018a) and run on a personal computer equipped with a 1.80 GHz CPU processor and 8 GB RAM. The two algorithms were implemented with the same line search (18) in the experiments, and the following parameters are set: ω1 = ω2 = 10− 4, r = 0.2, and ηk = 1/ (k + 1)­2, as they are taken in [5]. We, however, set t = 1.2 in our algorithm. The program execution is stopped if the total number of iterations exceeds 1000 or 5 ∥ Fk ∥10-5≤. To show the extensive numerical experiments of HDDPM and DFDD methods, we have tried these methods on the previous three Benchmark test problems with different initial points and dimensions (n values) between 1000 and 100,000.

 

 

Table 1: Initial points

 

 

 

 

 

Table 2: Numerical results of Problem 1

 

Table 3: Numerical results of Problem 2

 

 

 

 

Table 4: Numerical results of Problem 3

 

 

 

Tables (2-4) above reported the numerical results of the two methods, where ’ITER’ and ’TIME’ stand for the number of iterations and the CPU time (in seconds), respectively, while  is the norm of the residual at the stopping point. From the Tables, HDDPM and IDFDD methods attempt to solve the problem (1), but it is clear that the HDDPM method outperforms the IDFDD method. In particular, the HDDPM method considerably outperforms the IDFDD for almost all the tested problems, as it has the least iteration and CPU time than the IDFDD method. Due to the contribution of the computation of correction parameter at each iteration. Thus, the proposed method successfully solves the large-scale system of nonlinear equations.

 

 

 

 

 

Fig. 1. Performance profile with respect to the number of iterations

 

Fig. 2: Performance profile with respect to the CPU time (in second)

 

 

Using the performance profile of Dolan and More (Dolan & More, 2009), we generate Figures 1 and

to show the performance and efficiency of each of the three methods. That is, for each method, we plot the fraction P(τ) of the problems for which the method is within a factor τ of the best time. Figures 1 and 2 show that the curves corresponding to the HDDPM method stay above the other curve representing the IDFDD method. This indicates that the proposed method outperforms the compared method in terms of fewer iterations and CPU time (in second), and hence, it is the most efficient. Finally, it is clear from both Figures that our method effectively solves the large-scale nonlinear system of equations.

CONCLUSION

Hybridization of double direction method for solving system of nonlinear equations via Picard-Mann hybrid iterative process in Safeer (2013) is presented in this work. This was achieved by modifying the method in in Halilu and Waziri (2018) using the correction parameter. The proposed method is an entirely derivative-free iterative method, which is why it is more efficient in solving large-scale problems. Numerical comparisons have been made using a set of large-scale test problems. In addition, Table (2-4) and Fig. (1-2) have shown that the proposed method is very efficient because it has the least iteration and CPU time compared to the IDFDD method. In future research, the idea proposed in this scheme will be applied to solve the monotone nonlinear equations with application in compressive sensing.

REFERENCES

Abdullahi, H., Halilu, A. S., & Waziri, M. Y. (2018). A modified conjugate gradient method via a double direction approach for solving large-scale symmetric nonlinear systems. Journal of Numerical Mathematics and Stochastics, 10(1), 32–44.

Dennis, J. E., & Schnabel, R. B. (1983). Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall.

Dolan, E., & Moré, J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91, 201–213.

Halilu, A. S., & Waziri, M. Y. (2017). Enhanced matrix-free method via double step length approach for solving systems of nonlinear equations. International Journal of Applied Mathematical Research, 6, 147–156.

Halilu, A. S., & Waziri, M. Y. (2020). Inexact double step length method for solving systems of nonlinear equations. Statistics, Optimization & Information Computing, 8, 165–174.

Halilu, A. S., & Waziri, M. Y. (2020). Solving systems of nonlinear equations using improved double direction method. Journal of the Nigerian Mathematical Society, 32(2), 287–301.

Halilu, A. S., & Waziri, M. Y. (2017). A transformed double step length method for solving large-scale systems of nonlinear equations. Journal of Numerical Mathematics and Stochastics, 9, 20–32.

Halilu, A. S., & Waziri, M. Y. (2018). An improved derivative-free method via double direction approach for solving systems of nonlinear equations. Journal of the Ramanujan Mathematical Society, 33, 75–89.

Li, D., & Fukushima, M. (1999). A global and superlinear convergent Gauss-Newton based BFGS method for symmetric nonlinear equation. SIAM Journal on Numerical Analysis, 37, 152–172.

Petrović, M. J. (2015). An accelerated double step size model in unconstrained optimization. Applied Mathematics and Computation, 250, 309–319.

Petrović, M. J., Stanimirović, P. S., Kontrec, N., & Mladenović, J. (2018). Hybrid modification of accelerated double direction method. Mathematical Problems in Engineering, 2018, Article ID 1523267, 8 pages. https://doi.org/10.1155/2018/1523267

Petrovic, M. J., & Stanimirovic, P. S. (2014). Accelerated double direction method for solving unconstrained optimization problems. Mathematical Problems in Engineering, 2014, Article ID 1–8.

Safeer, H. K. (2013). A Picard-Mann hybrid iterative process. Fixed Point Theory and Applications, 2013, 69, 1–10.

Waziri, M. Y., Leong, W. J., & Hassan, M. A. (2011). Jacobian-free diagonal Newton’s method for solving nonlinear systems with singular Jacobian. Malaysian Journal of Mathematical Sciences, 5, 241–255.

Yuan, G., & Lu, X. (2008). A new backtracking inexact BFGS method for symmetric nonlinear equations. Computers & Mathematics with Applications, 55, 116–129. 

 

Iranian Journal of Optimization, 14(1), 27-37, March 2022 ,2023  2022  2022   22

 27

 

---