This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction and Background Results
The topic of our research is solving the unconstrained nonlinear optimization problem
Some well-known formulas for defining
The family of CG methods for nonlinear optimization has reached great popularity lately, thanks to the various benefits and advantages it possesses. The most important property is based on computationally efficient iterations arising from a simple CG rule. This property initiates the high efficiency of CG methods with respect to analogous methods for nonlinear optimization. Moreover, global convergence is ensured under suitable conditions. Finally, the application of various CG methods in solving image restoration problems has become an important research topic [10, 11].
Since the parameter
In order to complete the presentation, we will restate the main principles proposed so far for computing
Dai and Kou [15] suggested the conjugate gradient coefficient
The results given in [15] confirm that the DK iterations outperform many existing CG methods. Following the development of DL methods, Babaie-Kafaki and Ghanbari [16] defined two new ways to calculate the value of the parameter
Andrei in [17] proposed the new rule for calculating
Lotfi and Hosseini in [18] proposed the following rule for determining the parameter
On the basis of the above overview of the main CG methods and motivated by the strong theoretical properties and computational efficiency of modified Dai-Liao CG methods proposed by many researchers, we suggest a new way of calculating the value of the parameter
The global organization of sections is described as follows. Introduction, motivation, and a brief overview of the preliminary results are given in Section 1. A new rule for calculating the variable parameter
2. A Modified Dai-Liao Method and Its Convergence
Popularity in defining new rules for calculating
To successfully define
By putting
Further, with certain modifications and substitutions in the equation defining
It is easy to verify that
Accordingly,
Considering
Before the main algorithm, it is necessary to define the backtracking line search as one of the most popular and practical methods for computing the step length
Algorithm 1:
The backtracking line search.
Require: Nonlinear objective function
1:
2: While
3: Return
Algorithm 2 describes a computational framework for the EDL method.
It is necessary to examine the properties of the EDL method and prove its convergence.
Assumption 1.
(1) The level set
(2) The goal function
Assumption 1 initiates the existence of positive constants
The conditions from Assumption 1 are assumed. In view of the uniform convexity of
Algorithm 2:
Effective Dai-Liao (EDL) CG method.
Require: An initial point
1: Assign
2: If
STOP;
else go to Step 3.
3: Calculate
4: Compute
5: Calculate
6: Compute
7: Calculate
8: Compute
9: Let
It follows from (21) and (22) that
By (19) and (23), one concludes
The inequality (25) initiates
Taking into account
Lemma 2.
[22, 23]. Let Assumption 1 be accomplished and the points
Lemma 3.
Consider the proposed Dai-Liao CG method, including (3), (4), and (18). If the search procedure guarantees (27), for all
Proof.
The inequality (29) will be verified by induction. In the initial situation
Using (17) in common with (27) and
Now from (30), (31), and
In view of
The global convergence of the proposed EDL method is confirmed by Theorem 4.
Theorem 4.
Let Assumption 1 be true and
Proof.
Suppose the opposite, i.e., (34) is not true. This implies the existence of a constant
Squaring both sides of (4) implies
Taking into account (18), we can get
Now from (31) and (32), it follows that
Now, an application of (18) initiates
Using
Next, dividing both sides of (40) by
The inequalities in (41) imply
Therefore,
3. Numerical Experiments
The implementation of the EDL method is based on Algorithm 2. This section is intended to analyze and compare the numerical results obtained by the EDL method and four variants of the MHSDL class methods (6). These variants are defined by
The codes used in the testing experiments for the above methods are written in MATLAB R2017a and executed on the Intel Core i3 2.0 GHz workstation with the Windows 10 operating system. Three important criteria are analyzed in each individual test case: number of iterations (NI), number of function evaluations (NFE), and processor time (CPU).
The numerical experiment is performed using 28 test functions presented in [24], where much of the problems are taken over from the CUTEr collection [25]. All methods used in the testing of an arbitrary objective function start from the same initialization
The uniform terminating criteria for each of the five considered algorithms (EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6) are
Summary numerical results for EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods, executed on 28 test functions, are arranged in Tables 1–3. Tables 1–3 show the numerical outcomes corresponding to all three criteria (NI, NFE, and CPU) for the EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods.
Table 1
Summary results of EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods with respect to NI.
Test function | MHSDL3 | MHSDL4 | MHSDL5 | EDL | MHSDL6 |
Extended penalty | 1466 | 2243 | 2231 | 1259 | 1371 |
Perturbed quadratic | 1203710 | 754291 | 746557 | 305622 | 423037 |
Raydan 1 | 159055 | 110587 | 106586 | 55477 | 75154 |
Raydan 2 | 1636 | 441 | 441 | 70 | 209 |
Diagonal 1 | 116788 | 78844 | 73512 | 30978 | 20332 |
Diagonal 2 | 176983 | 270434 | 271595 | 515000 | 271295 |
Diagonal 3 | 150328 | 98647 | 104417 | 47155 | 37711 |
Hager | 8666 | 5219 | 5157 | 3234 | 3625 |
Generalized tridiagonal 1 | 1862 | 1471 | 1485 | 639 | 877 |
Extended TET | 1357 | 5954 | 5915 | 4030 | 2664 |
Diagonal 4 | 30693 | 19589 | 19332 | 8040 | 12012 |
Diagonal 5 | 1721 | 25120 | 25120 | 60 | 216 |
Extended Himmelblau | 1777 | 8023 | 7946 | 1376 | 3682 |
Perturbed quadratic diagonal | 2940970 | 2115659 | 2027128 | 1136414 | 1352704 |
Quadratic QF1 | 1270802 | 799192 | 786032 | 309509 | 325415 |
Extended quadratic penalty QP1 | 770 | 594 | 575 | 560 | 543 |
Extended quadratic penalty QP2 | 399671 | 240530 | 245254 | 96620 | 137799 |
Extended quadratic exponential EP1 | 462 | 606 | 606 | 513 | 526 |
Extended tridiagonal 2 | 3119 | 2176 | 2177 | 1132 | 1455 |
ARWHEAD (CUTE) | 88824 | 69868 | 67413 | 40713 | 48669 |
ENGVAL1 (CUTE) | 2323 | 1407 | 1415 | 552 | 820 |
INDEF (CUTE) | 20 | 31 | 1080 | 23 | 36240 |
QUARTC (CUTE) | 173913 | 262291 | 262291 | 524299 | 262181 |
Diagonal 6 | 1824 | 508 | 508 | 70 | 227 |
Generalized quartic | 1208 | 1403 | 2846 | 1265 | 1154 |
Diagonal 7 | 3217 | 655 | 655 | 653 | 580 |
Diagonal 8 | 511 | 698 | 698 | 686 | 596 |
Full Hessian FH3 | 1456 | 5353 | 5350 | 2523 | 3176 |
Table 2
Summary results of EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods with respect to NFE.
Test function | MHSDL3 | MHSDL4 | MHSDL5 | EDL | MHSDL6 |
Extended penalty | 54876 | 73764 | 73429 | 46820 | 49791 |
Perturbed quadratic | 56691737 | 34287604 | 33885701 | 13168688 | 18486375 |
Raydan 1 | 5066739 | 3364983 | 3236335 | 1551846 | 2170553 |
Raydan 2 | 6554 | 1162 | 1162 | 159 | 428 |
Diagonal 1 | 5004640 | 3256274 | 3022015 | 1200086 | 744278 |
Diagonal 2 | 353976 | 540878 | 543200 | 1030010 | 542600 |
Diagonal 3 | 6339146 | 3998904 | 4229565 | 1798032 | 1400076 |
Hager | 192474 | 107413 | 106534 | 59187 | 69735 |
Generalized tridiagonal 1 | 37429 | 27860 | 28138 | 10760 | 15177 |
Extended TET | 19546 | 77422 | 76925 | 40340 | 29334 |
Diagonal 4 | 713120 | 425023 | 418666 | 155027 | 242443 |
Diagonal 5 | 6874 | 50460 | 50460 | 140 | 442 |
Extended Himmelblau | 45972 | 192362 | 190524 | 26104 | 80854 |
Perturbed quadratic diagonal | 135901222 | 94177165 | 90238441 | 48147512 | 57702654 |
Quadratic QF1 | 55972697 | 33836473 | 33243711 | 12316721 | 12853424 |
Extended quadratic penalty QP1 | 17016 | 12882 | 12565 | 11116 | 10544 |
Extended quadratic penalty QP2 | 13015888 | 7454686 | 7584960 | 2743358 | 4030601 |
Extended quadratic exponential EP1 | 14914 | 18463 | 18463 | 14132 | 15133 |
Extended tridiagonal 2 | 36450 | 22564 | 22379 | 9687 | 12920 |
ARWHEAD (CUTE) | 4296028 | 3305257 | 3182138 | 1846606 | 2230650 |
ENGVAL1 (CUTE) | 40462 | 22432 | 22898 | 8209 | 12858 |
INDEF (CUTE) | 1808 | 2182 | 5995 | 2060 | 104962 |
QUARTC (CUTE) | 347926 | 524662 | 524662 | 1048648 | 524422 |
Diagonal 6 | 7394 | 1416 | 1408 | 159 | 468 |
Generalized quartic | 14364 | 21842 | 48770 | 16695 | 14103 |
Diagonal 7 | 6454 | 6838 | 6838 | 3891 | 4521 |
Diagonal 8 | 6098 | 6938 | 6938 | 4161 | 5494 |
Full Hessian FH3 | 60792 | 212799 | 212701 | 89890 | 114962 |
Table 3
Summary results of EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods with respect to CPU time (sec).
Test function | MHSDL3 | MHSDL4 | MHSDL5 | EDL | MHSDL6 |
Extended penalty | 29.75 | 34.11 | 31.42 | 18.30 | 24.27 |
Perturbed quadratic | 40532.66 | 24358.20 | 24947.84 | 8335.80 | 13225.80 |
Raydan 1 | 3054.67 | 1904.48 | 1692.06 | 690.91 | 1184.86 |
Raydan 2 | 6.77 | 1.58 | 1.66 | 0.31 | 0.77 |
Diagonal 1 | 7834.03 | 5106.41 | 4592.28 | 1476.89 | 486.09 |
Diagonal 2 | 885.13 | 1428.05 | 1447.02 | 2352.11 | 1513.50 |
Diagonal 3 | 13614.27 | 8416.77 | 9064.30 | 3132.02 | 1916.30 |
Hager | 586.63 | 325.75 | 333.41 | 142.06 | 198.13 |
Generalized tridiagonal 1 | 66.14 | 35.59 | 34.42 | 15.19 | 21.63 |
Extended TET | 20.50 | 78.34 | 82.94 | 41.23 | 31.45 |
Diagonal 4 | 134.53 | 77.86 | 87.88 | 30.41 | 55.34 |
Diagonal 5 | 18.06 | 134.73 | 121.09 | 0.56 | 1.84 |
Extended Himmelblau | 11.13 | 44.47 | 44.36 | 6.19 | 18.30 |
Perturbed quadratic diagonal | 91655.55 | 58226.16 | 60920.06 | 32179.38 | 36383.83 |
Quadratic QF1 | 62610.50 | 31552.48 | 28679.91 | 8832.11 | 8465.34 |
Extended quadratic penalty QP1 | 7.56 | 7.25 | 6.98 | 4.98 | 4.94 |
Extended quadratic penalty QP2 | 3814.16 | 2128.86 | 2288.55 | 671.52 | 1204.72 |
Extended quadratic exponential EP1 | 9.11 | 10.23 | 8.55 | 8.00 | 8.02 |
Extended tridiagonal 2 | 11.13 | 8.83 | 6.95 | 4.08 | 5.25 |
ARWHEAD (CUTE) | 2709.42 | 2336.92 | 2369.28 | 1266.80 | 1689.80 |
ENGVAL1 (CUTE) | 19.47 | 11.33 | 11.81 | 4.03 | 6.70 |
INDEF (CUTE) | 2.44 | 2.89 | 10.70 | 1.92 | 774.34 |
QUARTC (CUTE) | 3106.56 | 4818.58 | 4808.70 | 7138.72 | 4735.39 |
Diagonal 6 | 6.75 | 1.92 | 2.03 | 0.38 | 1.34 |
Generalized quartic | 7.16 | 11.53 | 21.05 | 7.53 | 9.78 |
Diagonal 7 | 5.98 | 8.20 | 8.28 | 4.56 | 6.25 |
Diagonal 8 | 6.17 | 8.20 | 8.08 | 4.72 | 7.69 |
Full Hessian FH3 | 30.08 | 66.45 | 79.48 | 35.77 | 43.42 |
We utilized the performance profile given in [26] to compare numerical results for three criteria (NI, NFE, and CPU) generated by five methods (EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6). The upper curve of the selected performance profile corresponds to the method that shows the best performance.
Figures 1–3 plot the performance profiles for the numerical values included in Tables 1–3, respectively. Figure 1 presents the performance profiles of the NI criterion generated by the EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods. In this figure, it is noticeable that EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods solved all tested functions, wherein the EDL method shows the best performances in 57.14% of test functions compared with MHSDL3 (25.00%), MHSDL4 (0.00%), MHSDL5 (0.00%), and MHSDL6 (17.86%). From Figure 1, it is observable that the graph of the EDL method comes first to the top, which means that the EDL outperforms other considered methods with respect to the NI.
[figure omitted; refer to PDF]
Figure 2 presents the performance profiles of the NFE of the EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods. It is observable that EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 generated solutions to all tested cases, and the EDL method is the best in 67.86% of the functions compared with MHSDL3 (17.86%), MHSDL4 (0.00%), MHSDL5 (0.00%), and MHSDL6 (14.28%). From Figure 2, it is observed that the EDL graph first comes to the top, which confirms that the EDL is the winner with respect to the NFE.
Figure 3 contains graphs of the performance profiles corresponding to the CPU time of the EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 methods. It is obvious that EDL, MHSDL3, MHSDL4, MHSDL5, and MHSDL6 solved all tested functions. Further analysis gives that the EDL method is the winner in 67.86% of the test cases compared with MHSDL3 (17.86%), MHSDL4 (0.00%), MHSDL5 (0.00%), and MHSDL6 (14.28%). Figure 3 demonstrates that the graph of the EDL method first comes to level 1, which indicates its superiority with respect to the CPU time.
From the previous analysis of the results shown in Tables 1–3 and Figures 1–3, it can be concluded that the EDL method produces superlative results in terms of all three basic metrics: NI, NFE, and CPU.
4. Conclusion
A novel rule which determines the value
We are convinced that the obtained results will be a motivation for further research in defining new values of the parameter
Acknowledgments
The research was supported by the National Natural Science Foundation of China (Grant Nos. 11971142, 11871202, 61673169, 11701176, 11626101, and 11601485).
[1] Y. -H. Dai, L. -Z. Liao, "New conjugacy conditions and related nonlinear conjugate gradient methods," Applied Mathematics and Optimization, vol. 43 no. 1, pp. 87-101, DOI: 10.1007/s002450010019, 2001.
[2] Y. Cheng, Q. Mou, X. Pan, S. Yao, "A sufficient descent conjugate gradient method and its global convergence," Optimization Methods and Software, vol. 31 no. 3, pp. 577-590, DOI: 10.1080/10556788.2015.1124431, 2016.
[3] I. E. Livieris, P. Pintelas, "A descent Dai-Liao conjugate gradient method based on a modified secant equation and its global convergence," ISRN Computational Mathematics, vol. 2012,DOI: 10.5402/2012/435495, 2012.
[4] M. R. Peyghami, H. Ahmadzadeh, A. Fazli, "A new class of efficient and globally convergent conjugate gradient methods in the Dai-Liao family," Optimization Methods and Software, vol. 30 no. 4, pp. 843-863, DOI: 10.1080/10556788.2014.1001511, 2015.
[5] H. Yabe, M. Takano, "Global convergence properties of nonlinear conjugate gradient methods with modified secant condition," Computational Optimization and Applications, vol. 28 no. 2, pp. 203-225, DOI: 10.1023/B:COAP.0000026885.81997.88, 2004.
[6] S. Yao, B. Qin, "A hybrid of DL and WYL nonlinear conjugate gradient methods," Abstract and Applied Analysis, vol. 2014,DOI: 10.1155/2014/279891, 2014.
[7] S. Yao, X. Lu, Z. Wei, "A conjugate gradient method with global convergence for large-scale unconstrained optimization problems," Journal of Applied Mathematics, vol. 2013,DOI: 10.1155/2013/730454, 2013.
[8] Y. Zheng, B. Zheng, "Two new Dai-Liao-type conjugate gradient methods for unconstrained optimization problems," Journal of Optimization Theory and Applications, vol. 175 no. 2, pp. 502-509, DOI: 10.1007/s10957-017-1140-1, 2017.
[9] W. Zhou, L. Zhang, "A nonlinear conjugate gradient method based on the MBFGS secant condition," Optimization Methods and Software, vol. 21 no. 5, pp. 707-714, DOI: 10.1080/10556780500137041, 2006.
[10] W. Hu, J. Wu, G. Yuan, "Some modified Hestenes-Stiefel conjugate gradient algorithms with application in image restoration," Applied Numerical Mathematics, vol. 158, pp. 360-376, DOI: 10.1016/j.apnum.2020.08.009, 2020.
[11] G. Yuan, T. Li, W. Hu, "A conjugate gradient algorithm for large-scale nonlinear equations and image restoration problems," Applied Numerical Mathematics, vol. 147, pp. 129-141, DOI: 10.1016/j.apnum.2019.08.022, 2020.
[12] N. Andrei, "Open problems in nonlinear conjugate gradient algorithms for unconstrained optimization," Bulletin of the Malaysian Mathematical Sciences Society, vol. 34 no. 2, pp. 319-330, 2011.
[13] W. W. Hager, H. Zhang, "A new conjugate gradient method with guaranteed descent and an efficient line search," SIAM Journal on Optimization, vol. 16 no. 1, pp. 170-192, DOI: 10.1137/030601880, 2005.
[14] W. W. Hager, H. Zhang, "Algorithm 851," ACM Transactions on Mathematical Software, vol. 32 no. 1, pp. 113-137, DOI: 10.1145/1132973.1132979, 2006.
[15] Y. -H. Dai, C. -X. Kou, "A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search," SIAM Journal on Optimization, vol. 23 no. 1, pp. 296-320, DOI: 10.1137/100813026, 2013.
[16] S. Babaie-Kafaki, R. Ghanbari, "The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices," European Journal of Operational Research, vol. 234 no. 3, pp. 625-630, DOI: 10.1016/j.ejor.2013.11.012, 2014.
[17] N. Andrei, "A Dai-Liao conjugate gradient algorithm with clustering of eigenvalues," Numerical Algorithms, vol. 77 no. 4, pp. 1273-1282, DOI: 10.1007/s11075-017-0362-5, 2018.
[18] M. Lotfi, S. M. Hosseini, "An efficient Dai-Liao type conjugate gradient method by reformulating the CG parameter in the search direction equation," Journal of Computational and Applied Mathematics, vol. 371, article 112708,DOI: 10.1016/j.cam.2019.112708, 2020.
[19] X. Li, Q. Ruan, "A modified PRP conjugate gradient algorithm with trust region for optimization problems," Numerical Functional Analysis and Optimization, vol. 32 no. 5, pp. 496-506, DOI: 10.1080/01630563.2011.554948, 2011.
[20] N. Andrei, "An acceleration of gradient descent algorithm with backtracking for unconstrained optimization," Numerical Algorithms, vol. 42 no. 1, pp. 63-73, DOI: 10.1007/s11075-006-9023-9, 2006.
[21] P. S. Stanimirovic, M. B. Miladinovic, "Accelerated gradient descent methods with line search," Numerical Algorithms, vol. 54 no. 4, pp. 503-520, DOI: 10.1007/s11075-009-9350-8, 2010.
[22] W. Cheng, "A two-term PRP-based descent method," Numerical Functional Analysis and Optimization, vol. 28 no. 11–12, pp. 1217-1230, DOI: 10.1080/01630560701749524, 2007.
[23] G. Zoutendijk, "Nonlinear programming, computational methods," Integer and Nonlinear Programming, North-Holland, pp. 37-86, 1970.
[24] N. Andrei, "An unconstrained optimization test functions collection," Advanced Modeling and Optimization, vol. 10 no. 1, pp. 147-161, 2008.
[25] I. Bongartz, A. R. Conn, N. Gould, P. L. Toint, "CUTE: constrained and unconstrained testing environments," ACM Transactions on Mathematical Software, vol. 21 no. 1, pp. 123-160, DOI: 10.1145/200979.201043, 1995.
[26] E. D. Dolan, J. J. Moré, "Benchmarking optimization software with performance profiles," Mathematical Programming, vol. 91 no. 2, pp. 201-213, DOI: 10.1007/s101070100263, 2002.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Copyright © 2021 Branislav Ivanov et al. This is an open access article distributed under the Creative Commons Attribution License (the “License”), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License. https://creativecommons.org/licenses/by/4.0/
Abstract
A new rule for calculating the parameter
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Details




1 Technical Faculty in Bor, University of Belgrade, Vojske Jugoslavije 12, 19210 Bor, Serbia
2 Faculty of Sciences and Mathematics, University of Niš, Višegradska 33, 18000 Niš, Serbia
3 University of Tetovo, St. Ilinden, n.n., Tetovo, North Macedonia
4 Department of Basic Sciences, University of Engineering and Technology Peshawar, Pakistan
5 Department of Mathematics, Huzhou University, Huzhou 313000, China