On the Picard-Mann approach for hybridizing the double direction method for solving a system of nonlinear equations.
Subject Areas : Non linear ProgrammingAbubakar Halilu 1 * , Aliyu kiri 2 , Mohammed Waziri 3
1 - Sule Lamido University, Kafin Hausa
2 - Department of Mathematics, Bayero University, Kano
3 - Department of Mathematics, Bayero University, Kano
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.
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.
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 |
*Correspondence E‐mail: abubakars.halilu@slu.edu.ng |
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, Petrovic’ 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+1I inherits the positive definiteness of γkI. 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, we 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) we 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.
-
A numerical approach for optimal control model of the convex semi-infinite programming
Print Date : 2015-12-01 -
-
Optimization of solution stiff differential equations using MHAM and RSK methods
Print Date : 2019-06-01 -