EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 4, 2022, 1908-1916 ISSN 1307-5543 – ejpam.com Published by New York Business Global A New Class of Optimization Methods Based on Coefficient Conjugate Gradient Yoksal A. Laylani1, Basim A. Hassan2,∗, Hisham M. Khudhur2 1 Department of Mathematics, College of Sciences, University of Kirkuk, Kirkuk, Iraq 2 Department of Mathematics, College of Computers Sciences and Mathematics, University of Mosul, Mosul, Iraq Abstract. The coefficient conjugate serves as the foundation for many conjugate gradient meth- ods. The quadratic model is used to derive a novel coefficient conjugate in this study. Its global convergence result might be produced under Wolfe line search circumstances. The conjugate gra- dient method’s performance for unconstrained optimization problems is demonstrated through numerical tests. 2020 Mathematics Subject Classifications: 90C30, 65K05, 49M37 Key Words and Phrases: Optimization, Conjugate Gradient, Numerical results 1. Introduction One of the most important iterative approaches for solving the unconstrained opti- mization issue is the Conjugate Gradient (CG) method, which is as follows: f(x∗) = min x∈Rn f(x). (1) where f : Rn → R is a smooth function, see [7, 11, 12]. The goal function and its gradient are all that is required of the CG techniques in each iteration, see [13]. As a result, this strategy is particularly well suited to solving optimization problems. These approaches use the following iterative formula: xk+1 = xk + αkdk. (2) If f is a quadratic, the one-dimensional minimizer along the ray may be calculated ana- lytically as: αk = − gTk dk dTkQdk (3) ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i4.4575 Email addresses: yuksel@uokirkuk.edu.iq (Y. A. Laylani), basimah@uomosul.edu.iq ( B. A. Hassan), hisham892020@uomosul.edu.iq (H. M. Khudhur) https://www.ejpam.com 1908 © 2022 EJPAM All rights reserved. Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1909 Iterative procedures are required for generic non-linear functions, in [9] has further infor- mation about this. The Wolfe requirements are frequently employed in the convergence analysis and implementation of conjugate gradient techniques to obtain the step length αk satisfying: f(xk + αkdk) ≤ f(xk) + δαkg T k dk (4) dTk g(xk + αkdk) ≥ σdTk gk (5) where 0 < δ < σ < 1. More information is available in [8, 15]. In practice, the conjugate gradient search direction for the next iteration looks like this: dk+1 = −gk+1 + βkdk (6) where βk is a scalar. There are two well-known methods for selecting βk: βFR k = ∥gk+1∥2 ∥gk∥2 , βDY k+1 = ∥gk+1∥2 dTk yk (7) separately by the Fletcher-Reeves (FR) approach [2] and the Dai-Yan (DY) method [1]. It approaches have good convergence properties, but their numerical results aren’t as good as the others [9]. Many variations of this method have been developed throughout the years, and some are extensively utilized in practice. Take, for example, Hideaki and Yasushi [14] and Basim [3]: βHY k = ∥gk+1∥2 2/αk(fk − fk+1) , βB k = ∥gk+1∥2 (fk − fk+1)/αk − gTk dk/2 (8) These algorithms have a very high numerical efficiency. The quadratic model has been established to improve efficiency for unconstrained problems, in order to maximize the ben- efits of the original conjugate gradient approaches. A few novel optimization approaches have been presented in this regard [4–6]. Using a conjugacy condition, we provide a modi- fied conjugate gradient technique in this paper. The sufficient descent property is satisfied by the new search direction, which is independent of the line search and the convex- ity assumption on the objective function. Under the conventional assumptions, the new method has global convergence for generic functions. When dealing with unconstrained optimization issues, numerical experiments show that the new approach is superior. 2. Deriving new Coefficient Conjugate As everyone is aware, the following outcomes are produced when the objective function to be decreased is quadratic and accurate line searches are used: dTk+1Qdk = 0 (9) where Q is Hessian matrix. The conjugacy condition is what it’s called. In [13] has further information. Because the dk+1 = −gk+1 + βkdk for the conjugate gradient technique, the Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1910 following is the result: βk = gTk+1Qsk dTkQsk (10) as a result, a coefficient conjugacy is obtained. We now utilize a quadratic model to derive the new conjugate gradient approach, which can be represented as: fk+1 = fk + sTk gk + 1 2 sTkQ(xk)sk (11) We may calculate the first order derivative: ∇fk+1 = gk +Q(xk)sk (12) Using (12) in (11) we get the following: sTk yk + fk+1 − fk = 1 2 sTkQ(xk)sk (13) We may write the equation (13) by using (3), as follows: dTkQ(xk)sk = 1 2 αk(g T k dk) 2 (sTk yk + (fk+1 − fk)) = ρks T k yk (14) We generate a new formula βk by plugging (14) into (10): βk = gTk+1yk ρks T k yk , ρ1k = 1 2 αk(g T k dk) 2 sTk yk(s T k yk + (fk+1 − fk)) (15) Because f is a quadratic function and exact line search is used, the following is the result: βk = ∥gk+1∥2 ρks T k yk , ρ1k = 1 2 αk(g T k dk) 2 sTk yk(s T k yk + (fk+1 − fk)) (16) Using and exact line search in (13), then (16) reduces to: ρ2k = 1 2 αk(g T k dk) 2 sTk yk(−sTk gk + (fk+1 − fk)) (17) and ρ3k = 1 2 αk(g T k dk) 2 sTk yk(αkg T k gk + (fk+1 − fk)) (18) As a result, our proposal, the so-called BN, becomes clear. The proposed technique is provided with a new algorithm based on the aforementioned. Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1911 2.1. Algorithm Step 1. Givenx1 ∈ Rn. Set k = 1 and d1 = −g1. Step 2. Let the step size αk satisfying the (4) and (5). Step 3. Let xk+1 = xk + αkdk. If ∥gk+1∥ ≤ 10−6, then stop. Step 4. Update βk by the (16), then dk+1 by (6). Step 5. Set k = k + 1 and go to Step2. The descent condition exposes a useful characteristic for the new formula conjugate gradient technique. Additional properties are highly crucial in the convergence proved in this investigation. The preceding material is summarized in the following theorem. Theorem 1. If we use the new way to create {xk} and {dk}, we get: dTk+1gk+1 < 0, and dTk+1gk+1 = βkd T k gk (19) Proof. It goes without saying that if dk = −gk then dT1 g1 < 0. Assume that dTk gk < 0 for any k. From (6) and (17), it is simple to deduce: dTk+1gk+1 = −gTk+1gk+1 + βkd T k gk+1 = −βk [ ρks T k yk ] + βkd T k gk+1 = βk[d T k gk+1 − ρks T k yk] (20) We may deduce the following from equations (15) and (20): dTk+1gk+1 = βkd T k gk (21) It is obvious that dTk gk < 0, thus we get: dTk+1gk+1 < 0 (22) The proof is finished.Other methods, can be proven in the same way. 3. Convergence Analysis We look at how new algorithms are converged. On the objective function, the following assumptions are made. • D = {x|f(x) ≤ f(x0)} is a bounded level set. • In some neighborhood D that contains L0, the gradient is Lipschitz continuous; that is, L exists such that: ∥g(υ)− g(ω)∥ ≤ L ∥υ − ω∥ ∀υ, ω ∈ D (23) For further information, read [1, 10] and Zoutendijk [16] achieved the following significant finding. Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1912 Lemma 1. Allow all assumptions to be true. Consider any iteration algorithm that uses the Wolfe line search to get αk. Then: ∞∑ k=1 (gTk dk) 2 ∥dk∥2 < ∞ (24) Theorem 2. Assume that all of your assumptions are correct. If (19) is satisfied by formula βk, we have: lim k→∞ inf ∥gk∥ = 0 (25) Proof. Assume that (25) isn’t true by induction. (6) is rewritten as dk+1+gk+1 = βkdk, and upon squaring both sides, we obtain: ∥dk+1∥2 + ∥gk+1∥2 + 2dTk+1gk+1 = (βk) 2 ∥dk∥2 (26) Applying (21), yields: ∥dk+1∥2 = (dTk+1gk+1) 2 (dTk gk) 2 ∥dk∥2 − 2dTk+1gk+1 − ∥gk+1∥2 (27) Equation (27) is divided into (dTk+1gk+1) 2, we get: ∥dk+1∥2 (dTk+1gk+1)2 = ∥dk∥2 (dTk gk) 2 − ∥gk+1∥2 (dTk+1gk+1)2 − 2 dTk+1gk+1 (28) The equation becomes, by completing the square: ∥dk+1∥2 (dTk+1gk+1)2 ≤ ∥dk∥2 (dTk gk)2 − ( ∥gk+1∥ (dTk+1gk+1) + 1 ∥gk+1∥2 ) + 1 ∥gk+1∥2 ≤ ∥dk∥2 (dTk gk)2 + 1 ∥gk+1∥2 (29) Hence, ∥dk+1∥2 (dTk+1gk+1)2 ≤ k+1∑ i=1 1 ∥gi∥2 (30) Suppose that there exists c1 > 0 such that ∥gk∥ ≥ c1 for all k ∈ n.Then : ∥dk+1∥2 (dTk+1gk+1)2 < k + 1 c21 (31) Assume and note in Equation (31) that: ∞∑ k=1 (gTk dk) 2 ∥dk∥2 = ∞ (32) Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1913 Based on Lemma 1, we get limk→∞ inf ∥gk∥ = 0 holds. Other methods, can be proven in the same way. 4. Numerical Results The outcomes of mathematical experiments are presented in this section. The FR- Algorithm was contrasted with the innovative conjugate gradient algorithm. Fortran was used to create both algorithms. Section 1. contains the exam questions. We investi- gated numerical experiments for 15 extended unconstrained optimization problems with the number of variables for each test function. We use the inequality as a termination condition. Table 1 contains the findings of the Wolfe condition test, with the following def- initions for each column: The terminology used to describe the issue comprises problem, problem size, dim, number of iterations (NI), and number of function evaluations (NF). Table 1 shows how many challenges these strategies have addressed in terms of iterations and function evaluations. Problem numbers indicant for : 1. is the Trigonometric, 2. is the Extended Rosenbrock, 3. is the Hager, 4. is the Extended Tridiagonal 1, 5. is the Generalized Tridiagonal 2, 6. is the Extended PSC1, 7. is the Extended Tridiagonal 2, 8. is EDENSCH (CUTE), 9. is the STAIRCASE S1, 10. is the DENSCHNA (CUTE), 11. is the DENSCHNC (CUTE), 12. is the Extended White & Holst, 13. is the Extended Block-Diagonal BD2, 14. is the Generalized quartic GQ2, 15. is the Extended Beale. Y. A. Laylani, B. A. Hassan, H. M. Khudhur / Eur. J. Pure Appl. Math, 15 (4) (2022), 1908-1916 1914 Table 1: The numerical results of the FR and New methods FR algorithm BN1 (16) BN2 (17) BN3 (18) P. No. n NI NF NI NF NI NF NI NF 1 100 19 35 18 33 18 33 18 34 1000 38 65 32 57 34 62 38 65 2 100 47 93 40 80 40 82 42 90 1000 78 131 37 78 34 74 39 85 3 100 61 1024 47 665 25 43 28 46 1000 Fail Fail Fail Fail Fail Fail Fail Fail 4 100 32 64 10 21 10 21 13 27 1000 77 129 16 31 16 31 15 31 5 100 37 67 40 63 40 63 44 70 1000 73 115 65 102 67 107 61 98 6 100 15 31 8 17 8 17 8 17 1000 8 17 7 15 7 15 7 15 7 100 40 65 35 56 37 58 36 56 1000 43 68 49 382 39 59 42 65 8 100 69 1202 45 637 38 364 26 48 1000 98 1967 65 1279 43 440 33 257 9 100 671 1066 441 689 480 763 612 982 1000 Fail Fail Fail Fail Fail Fail Fail Fail 10 100 20 33 10 19 10 19 10 19 1000 19 35 9 18 9 18 9 18 11 100 49 80 15 28 14 26 15 26 1000 129 166 13 26 13 26 13 26 12 100 43 88 38 86 33 75 37 79 1000 46 92 34 77 35 76 40 89 13 100 122 156 12 23 12 23 12 23 1000 130 166 12 23 12 23 12 23 14 100 112 147 34 57 37 61 34 58 1000 110 145 38 58 40 60 35 55 15 100 32 52 12 24 12 24 16 32 1000 22 42 12 24 12 24 19 38 Total 2240 7341 1194 4668 1175 2687 1314 2472 The novel procedure saves NI and NF over time when compared to the conventional Fletcher and Reeves (FR) methodology, notably for our set of test problems, as demon- strated in Table 2. Table 1 compares the new methods to the Fletcher and Reeves [2] convex optimization strategy. REFERENCES 1915 Table 2: Ratio of algorithm New cost to HS cost FR algorithm BN1 (16) BN2 (17) BN3 (18) NI 100% 53.30 % 52.45 % 58.66 % NF 100 % 63.58 % 36.60 % 33.67 % 5. Final Thoughts In this study, we provide a novel, globally convergent, functional nonlinear CG method, and fulfills the descent property under certain assumptions, and is based on the strictly convex quadratic function represented by (10) According to computer studies, the unique kinds given in this study are successful. References [1] Yu-Hong Dai and Yaxiang Yuan. A nonlinear conjugate gradient method with a strong global convergence property. SIAM Journal on optimization, 10:177–182, 1999. [2] Reeves Fletcher and Colin M Reeves. Function minimization by conjugate gradients. The computer journal, 7:149–154, 1964. [3] Basim A. Hassan. A new formula for conjugate parameter computation based on the quadratic model. Indonesian Journal of Electrical Engineering and Computer Science, 3:954–961, 2019. [4] Basim A. Hassan, Hussein O Dahawi, and Azzam S Younus. A new kind of parameter conjugate gradient for unconstrained optimization. Indonesian Journal of Electrical Engineering and Computer Science, 17:404, 2020. [5] Basim A. Hassan, Kanikar Muangchoo, Fadhil Alfarag, Abdulkarim Hassan Ibrahim, and Auwal Bala Abubakar. An improved quasi-newton equation on the quasi-newton methods for unconstrained optimizations. Indonesian Journal of Electrical Engineer- ing and Computer Science, 22:389–397, 2020. [6] Basim A. Hassan and RM Sulaiman. A new class of self-scaling for quasi-newton method based on the quadratic model. Indonesian Journal of Electrical Engineering and Computer Science, 21:1830–1836, 2021. [7] Hawraz N Jabbar and Basim A Hassan. Two-versions of descent conjugate gradient methods for large-scale unconstrained optimization. Indonesian Journal of Electrical Engineering and Computer Science, 22:1643, 2021. [8] Xian-zhen Jiang and Jin-bao Jian. A sufficient descent dai–yuan type nonlinear conju- gate gradient method for unconstrained optimization problems. Nonlinear Dynamics, 72:101–112, 2013. REFERENCES 1916 [9] Jorge Nocedal and Stephen J Wright. Numerical optimization, springer series in operations research. Siam J Optimization, 2006. [10] G Ribière and E Polak. Note sur la convergence de directions conjugées. Rev. Fran- caise Informat Recherche Opertionelle, 16:35–43, 1969. [11] Ahmet SAHINER, İdris A Masoud ABDULHAMID, and Shehab A IBRAHEM. A new filled function method with two parameters in a directional search. Journal of Multidisciplinary Modeling and Optimization, 2:34–42, 2019. [12] Ahmet Sahiner and Shehab A Ibrahem. A new global optimization technique by auxiliary function method in a directional search. Optimization Letters, 13:309–323, 2019. [13] Wei Xue, Junhong Ren, Xiao Zheng, Zhi Liu, and Yueyong Liang. A new dy conjugate gradient method and applications to image denoising. IEICE TRANSACTIONS on Information and Systems, 101:2984–2990, 2018. [14] N Yasushi and I Hideaki. Conjugate gradient methods using value of objective func- tion for unconstrained optimization optimization letters. V, 6:941–955, 2011. [15] Gaohang Yu, Jinhong Huang, and Yi Zhou. A descent spectral conjugate gradient method for impulse noise removal. Applied mathematics letters, 23:555–560, 2010. [16] G Zoutendijk. Nonlinear programming, computational methods. Integer and nonlin- ear programming, pages 37–86, 1970.