SQU Journal for Science, 2022, 90-99 DOI: 10.53539/squjs.vol27iss2pp90-99 Sultan Qaboos University 90 Solving unconstrained optimization problems by a new conjugate gradient method with sufficient descent property Farzad Rahpeymaii 1* , Majid Rostami 2 1 Department of Mathematics‎, Technical and Vocational University (TVU), Tehran, Ira‏n, 2 Department of Mathematics‎, Technical and Vocational University (TVU), Tehran, Ira‏n, *Email: rahpeyma_83@yahoo.com. ABSTRACT: ‎There have been some conjugate gradient methods with strong convergence but numerical instability and conversely‎. Improving these methods is an interesting idea to produce new methods with both strong convergence and‎ ‎‏‏ ‎numerical stability‎. ‎In this paper‎, ‎a new hybrid conjugate gradient method is introduced based on the Fletcher‎ ‎formula (CD) with strong convergence and the Liu and Storey formula (LS) with good numerical results‎.‎ ‎New directions satisfy the sufficient descent property‎, ‎independent of line search‎.‎‎Under some mild assumptions‎, ‎the global convergence of new hybrid method is proved‎.‎‎Numerical results on unconstrained CUTEst test problems show that the new algorithm is‎‎very robust and efficient‎. Keywords: Conjugate gradient methods; Unconstrained optimization; Global convergence; Sufficient descent property;‎‎Numerical results. يهلکافخاصية اإلنحدارا مترافقةال ميولمن خالل طریقة ال ةغيرالمقيّد لمسائ تحسينحل و پيمایی، مجيد رستمی هفرزاد را إلنتاج‏‏‏فكرة‏مثیرة‏.‏تحسین‏هذه‏الطرقكسیا،‏لکن‏غیر‏مستقّرة‏وغیرثابتة‏عددیا‏و‏عةقوب‏توافقتهناك‏بعض‏من‏طرق‏اإلنحدار‏المزدوج،‏التی‏‏:لخصمال (‏CDة‏فلجر‏)طرق‏جدیدة‏بالتقارب‏العددی‏القوی‏و‏الثابت.‏فی‏هذه‏المقالة،‏قد‏عّرفت‏و‏قدّمت‏طریقة‏اإلنحدار‏المزدوج‏المرّکب‏الجدید‏علی‏أساس‏صیغ ‏المستقلة‏عن‏البحث‏بنتائج‏رقمیة‏جیدة.‏تحت‏الشروط‏القیاسیة‏(‏LSاستوری‏)بالتقارب‏القوی‏و‏صیغة‏لیو‏و ‏الجهات‏الجدیدة وبالنتائج‏العددیة‏الجیدة. تدّل‏علی‏أّن‏الخوارزمیة‏‏ CUTEstاختبار‏القضایا‏والمسائل‏غیر‏المقیدة‏على‏النتائج‏‏العددیة‏‏.الخطي،‏تم‏اثبات‏التقارب‏الجماعي‏للطریقة‏المركبة‏الجدیدة ‏الجدیدة،‏قویّة‏جدّا.‏ ‏ النتائج‏العددیة.‏-التقارب‏الجماعی،‏شرط‏التقلیل‏الکافی‏-التحسین‏غیر‏المقیّد‏-اإلنحدار‏المزدوجطرق‏‏:الكلمات المفتاحية 1. Introduction ‎onsider the unconstrained optimization problem‎ 𝑓(𝑥), 𝑥∈ℝ𝑛 𝑚𝑖𝑛 )1) ‎where 𝑓: ℝ𝑛 → ℝ is a smooth nonlinear function whose‎‎gradient at 𝑥 is available 𝑔 ≔ 𝑔(𝑥) = ∇𝑓(𝑥). ‎There are many iterative methods to solve‎‎‎unconstrained optimization problem including the Newton methods‎, ‎the quasi-Newton‎ ‎methods, trust-region methods [21]. 1.1 Conjugate gradient method ‎The conjugate gradient (CG) methods are famous iterative methods for solving large-scale unconstrained‎ ‎optimization problems whose iterative scheme is‎ C SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS 91 𝑥𝑘+1 ≔ 𝑥𝑘 + 𝛼𝑘 𝑑𝑘 , 𝑥0 ∈ ℝ 𝑛 . (2) Here 𝑥0 ∈ ℝ 𝑛 is an initial point‎, ‎𝛼 > 0 is a step size‎, ‎which is obtained by an exact or inexact line search methods‎‎and 𝑑𝑘 is a search direction computed by‎ 𝑑𝑘 = { −𝑔𝑘 , 𝑘 = 0, −𝑔𝑘 + 𝛽𝑘 𝑔𝑘−1, 𝑘 ≥ 1, (3) ‎in which 𝛽𝑘 is a scalar‎, ‎called the CG parameter and 𝑔𝑘 ≔ 𝑔(𝑥𝑘 )‎.‎ ‎Different choices for CG parameter are available‎, ‎some of which are as follows‎ 𝛽𝑘 𝐹𝑅 ≔ ‖𝑔𝑘‖ 2 ‖𝑔𝑘−1‖ 2 , Fletcher & Reeves (FR) [8] (4) 𝛽𝑘 𝐻𝑆 ≔ 𝑔𝑘 𝑇𝑦𝑘−1 𝑑𝑘−1 𝑇 𝑦𝑘−1 , Hestenes & Stiefel (HS) [15] (5) 𝛽𝑘 𝐶𝐷 ≔ − ‖𝑔𝑘‖ 2 𝑔𝑘−1 𝑇 𝑑𝑘−1 , Fletcher (CD) [7] (6) 𝛽𝑘 𝑃𝑅𝑃 ≔ 𝑔𝑘 𝑇𝑦𝑘−1 ‖𝑔𝑘−1‖ 2 , Polak & Ribire − Polyak (PRP) [23,24] (7) 𝛽𝑘 𝐷𝑌 ≔ ‖𝑔𝑘‖ 2 𝑑𝑘−1 𝑇 𝑦𝑘−1 , Dai & Yuan (DY) [4] (8) 𝛽𝑘 𝐿𝑆 ≔ − 𝑔𝑘 𝑇𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 , Liu & Storey (LS) [20] (9) 𝛽𝑘 𝐻𝑍 ≔ (𝑦𝑘−1 − 2𝑑𝑘−1 ‖𝑦𝑘−1‖ 2 𝑑𝑘−1 𝑇 𝑦𝑘−1 ) 𝑇 𝑔𝑘 𝑑𝑘−1 𝑇 𝑦𝑘−1 , Hager & Zhang (HZ) [13] (10) ‎in which ‖ . ‖ is the Euclidean norm and 𝑦𝑘−1 ≔ 𝑔𝑘 − 𝑔𝑘−1‎. ‎These methods require‎ ‎low memory. ‎In order to guarantee the global convergence of CG methods‎, ‎the search direction 𝑑𝑘 must satisfy‎‎‎the sufficient descent condition [1] 𝑔𝑘 𝑇 𝑑𝑘 ≤ −𝑐‖𝑔𝑘 ‖ 2, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑘 ≥ 0, (11) ‎in which 𝑐 is a positive constant‎. ‎In CG methods to solve (1) ‎, ‎after determining the descent‎‎‎search direction satisfying 𝑔𝑘 𝑇 𝑑𝑘 ≤ 0 for all 𝑘 ≥ 0‎, the step size 𝛼𝑘 needs to be found‎, ‎which‎‎‎can be computed by inexact line search‎‎‎such as Armijo‎, ‎Goldstein and Wolfe conditions‎. ‎For a given constant 𝜌 ∈ (0,1)‎, the Armijo line search is‎ 𝑓(𝑥𝑘 + 𝛼𝑘 𝑑𝑘 ) − 𝑓(𝑥𝑘 ) ≤ 𝜌𝛼𝑘 𝑔𝑘 𝑇 𝑑𝑘 . (12) ‎The Armijo condition (12) along with 𝑔𝑘+1 𝑇 𝑑𝑘 ≥ 𝜎𝑔𝑘 𝑇 𝑑𝑘 , 0 < 𝜌 < 𝜎 < 1, (13) ‎is called the Wolfe line search [21].‎‎In addition‎, ‎in a strong Wolfe line search‎, ‎(13) is changed as‎ |𝑔𝑘+1 𝑇 𝑑𝑘 | ≤ −𝜎𝑔𝑘 𝑇 𝑑𝑘 . (14) 1.2 Applications of CG method Conjugate gradient methods play an important rol‏e in solving large-scale unconstrained optimization problems‎ ‎which‎ arise in economics, engineering, sciences and so on. Currently, the ‎u‎nconstrained‎ ‎optimization problem‏s in impulse noise removal and image restoration have been solved by CG method‏s [2,17]. 1.3 Contribution ‎Although LS has a good performance in practice‎, ‎it is generally not a strong convergence‎.‎‎On the other hand‎, ‎in CD with strong convergence the numerical results are not efficient.‎‎The purpose of this paper is to overcome these drawbacks‎. ‎We improve and combine LS and CD‎‎‎to obtain a new method with a good performance in practice and strong convergence properties‎.‎ ‎The new method always produces a sufficient descent direction which the global‎‎ ‎convergence of it is established under some suitable assumptions‎.‎ ‎Also‎, ‎we give some preliminary numerical experiments to illustrate the efficiency of new method‎. ‎In Section 2‎, ‎we describe our proposed‎‎‎method and give its algorithm‎. ‎The sufficient descent condition of new direction and‎‎‎the global convergence of the new algorithm are established in Section 3‎.‎‎In Section 4‎, ‎we report some numerical results to show the efficiency of new method‎.‎‎Finally‎, ‎we give our conclusion in Section 5‎. RAHPEYMAII F. ROSTAMI M. 92 2. Motivation and proposed algorithm ‎In this section‎, ‎we describe the new method to solve unconstrained optimization problem (1).‎‎The LS proposed by Liu and Story [02] ‎. ‎The global convergence of‎‎‎LS with Grippo & Lucidi line search is established in [11] ‎. ‎This method has good numerical‎‎ ‎results but its global convergence properties are not strong‎. ‎Many researchers have proposed several modifications‎‎‎of LS‎, ‎see ‎[19,26,27]. Fletcher in [7] proposed CD‎‎for a general objective function with strong convergence properties‎, ‎but in numerical performance is weak‎. ‎We improve and combine CD‎‎‎and LS to obtain a new method with both the strong convergence and the good numerical results‎.‎‎Based on LS and CD parameters‎, ‎we obtain‎ 𝛽𝑘 1 ≔ − 𝑔𝑘 𝑇𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 𝑎𝑛𝑑 𝛽𝑘 2 ≔ − ‖𝑦𝑘−1‖ 2 𝑔𝑘−1 𝑇 𝑑𝑘−1 . (15) ‎Here‎, 𝛽𝑘 1: = 𝛽𝑘 𝐿𝑆 and in the numerator of 𝛽𝑘 2 term ‖𝑦𝑘−1‖ 2 has replaced ‖𝑔𝑘 ‖ 2 in parameter ‎𝛽𝑘 𝐶𝐷 . Therefore‎, ‎the new conjugate gradient parameter is obtained by‎ 𝛽𝑘 𝑛𝑒𝑤 : = 𝑡𝑘 𝛽𝑘 2 − 𝛽𝑘 1, (16) with 𝑡𝑘 ≔ 2 𝑔𝑘 𝑇𝑑𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 . (17) The ‎parameters ‎𝛽𝑘 1, 𝛽𝑘 2‎ and 𝑡𝑘 guarantee‏ the sufficient descent property ‎and‎ the global convergence. Furthermore, these parameters improve numerical results of new method in compared to CD and LS methods‏. Now, ‎by substituting (15) and (17) in (11) ‎, ‎we get‎ 𝛽𝑘 𝑛𝑒𝑤 : = −2 𝑔𝑘 𝑇𝑑𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 ‖𝑦𝑘−1‖ 2 𝑔𝑘−1 𝑇 𝑑𝑘−1 + 𝑔𝑘 𝑇𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 . (18) ‎Finally‎, ‎the new search direction 𝑑𝑘 is computed by‎ 𝑑𝑘 = { −𝑔𝑘 , 𝑘 = 0, −𝑔𝑘 + 𝛽𝑘 𝑛𝑒𝑤 𝑑𝑘−1, 𝑘 ≥ 1. (19) ‎Algorithm 1 solves the smooth unconstrained optimization problem (1).‎‎It takes the initial point 𝑥0 ∈ ℝ 𝑛 as input and uses the following parameters‎:‎𝜀 > 0 (minimum threshold for the stopping test)‎, 𝜅 ∈ (0,1) and 0 < 𝜌 < 𝜎 < 1 (Line search parameters), 𝑘𝑚𝑎𝑥 (maximum number of iterations), and‎ 0 < 𝛼𝑚𝑖𝑛 < 𝛼𝑚𝑎𝑥 < ∞ (minimum and maximum values for 𝛼𝑘). ‎It returns 𝑥 ∗ ≔ 𝑥𝑘 and 𝑓 ∗ ≔ 𝑓𝑘 as an optimum and its function value‎. Note that 𝛼𝑚𝑖𝑛 and 𝛼𝑚𝑎𝑥 prevent the production of too small and large step size, respectively. Algorithm 1 A new conjugate gradient method (S0) Compute the initial function value 𝑓0 ≔ 𝑓(𝑥0), the initial gradient vector 𝑔0 ≔ 𝑔(𝑥0) and set 𝑑0 ≔ −𝑔0. (S1) If ‖𝑔𝑘 ‖ ≤ 𝜀 or 𝑘 > 𝑘𝑚𝑎𝑥 , stop. (S2) Find 𝛼𝑘 satisfying (12) and (14) and restrict 𝛼𝑘 = 𝑚𝑎𝑥{𝛼𝑚𝑖𝑛 , 𝑚𝑖𝑛{𝛼𝑘 , 𝛼𝑚𝑎𝑥 }}. Then, compute 𝑥𝑘+1 ≔ 𝑥𝑘 + 𝛼𝑘 𝑑𝑘 , 𝑓𝑘+1 ≔ 𝑓(𝑥𝑘+1) and 𝑔𝑘+1 ≔ 𝑔(𝑥𝑘+1). (S3) Calculate 𝛽𝑘+1 1 and 𝛽𝑘+1 2 by (15), obtain the parameter 𝑡𝑘+1 by (17), determine the parameter 𝛽𝑘+1 𝑛𝑒𝑤 by (16) and 𝑑𝑘+1 ≔ −𝑔𝑘+1 + 𝛽𝑘+1 𝑛𝑒𝑤 𝑑𝑘. (S4) Replace 𝑘 by 𝑘 + 1 and go to (S1). 3. Convergence analysis In this section, the sufficient descent property and the global convergence of the Algorithm 1 are established. To do so, we make some assumptions on the objective function. (H1)‎‎The level set 𝐿(𝑥0) = {𝑥 ∈ ℝ 𝑛 | 𝑓(𝑥) ≤ 𝑓(𝑥0)} is bounded‎, ‎i.e.‎,‎‎there exists a constant 𝐵 > 0 such that‎ ‖𝑥‖ ≤ 𝐵, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥 ∈ 𝐿(𝑥0). (20) (H2)‎ ‎‎In some neighborhood Ω ⊆ 𝐿(𝑥0),‏‎the gradient of the objective function 𝑓 ‎is Lipschitz continuous‎, ‎i.e.‎, ‎there exists a constant 𝐿 > 0 such that‎ ‖𝑔(𝑥) − 𝑔(𝑦)‖ ≤ 𝐿‖𝑥 − 𝑦‖, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥 ∈ Ω. (21) ‎From (H1) and (H2)‎, ‎there exists a positive constant 𝛾 such that‎ ‖𝑔(𝑥)‖ ≤ 𝛾, (22) ‎see [21]‎. ‎We now show that the generated directions by Algorithm 1 satisfy the sufficient descent‎‎‎condition (11) with 𝑐 = 7 8 ‎ independent of line search type‎. Lemma 1 ‎Suppose that the direction 𝑑𝑘 is generated by Algorithm 1‎. ‎Then‎, ‎we have‎ 𝑔𝑘 𝑇 𝑑𝑘 ≤ − 7 8 ‖𝑔𝑘 ‖ 2. (23) Proof ‌‌By multiplying (19) in 𝑔𝑘 𝑇 and using (18), ‎we obtain‎ SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS 93 𝑔𝑘 𝑇 𝑑𝑘 = −‖𝑔𝑘 ‖ 2 + 𝛽𝑘 𝑛𝑒𝑤 𝑔𝑘 𝑇 𝑑𝑘−1 = −‖𝑔𝑘 ‖ 2 + ( 𝑔𝑘 𝑇 𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 − 2 𝑔𝑘 𝑇 𝑑𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 ‖𝑦𝑘−1‖ 2 𝑔𝑘−1 𝑇 𝑑𝑘−1 ) 𝑔𝑘 𝑇 𝑑𝑘−1 = −‖𝑔𝑘 ‖ 2(𝑔𝑘−1 𝑇 𝑑𝑘−1) 𝟐 + (𝑔𝑘−1 𝑇 𝑑𝑘−1)(𝑔𝑘 𝑇 𝑦𝑘−1)(𝑔𝑘 𝑇 𝑑𝑘−1) − 2‖𝑦𝑘−1‖ 2(𝑔𝑘 𝑇 𝑑𝑘−1) 𝟐 (𝑔𝑘−1 𝑇 𝑑𝑘−1) 𝟐 . ‎Take‎ 𝜐𝑘 ≔ 2(𝑔𝑘 𝑇 𝑑𝑘−1)𝑦𝑘−1 �̃�𝑘 ≔ 1 2 (𝑔𝑘−1 𝑇 𝑑𝑘−1)𝑔𝑘 . ‎Using 𝜐𝑘 𝑇 �̃�𝑘 ≤ 1 2 (‖𝜐𝑘 ‖ 2 + ‖ �̃�𝑘 ‖ 2), we get 𝑔𝑘 𝑇 𝑑𝑘 ≤ 1 Θ1 2 (−‖𝑔𝑘 ‖ 2Θ1 2 + 2Θ2 2‖𝑦𝑘−1‖ 2 + 1 8 Θ1 2‖𝑔𝑘 ‖ 2 − 2‖𝑦𝑘−1‖ 2Θ2 2) = − 7 8 ‖𝑔𝑘 ‖ 2, where Θ1 ≔ 𝑔𝑘−1 𝑇 𝑑𝑘−1 𝑎𝑛𝑑 Θ2 ≔ 𝑔𝑘 𝑇 𝑑𝑘−1. ‎ Therefore‎, ‎the search direction 𝑑𝑘 always satisfies the sufficient descent condition‎.  Lemma 2 ‎Suppose that (H2) holds and the tuning parameter 𝛼𝑚𝑎𝑥‎ is given. ‎Then‎, ‎there exists a constant ω1 > 0 such that‎ |𝛽𝑘 1| ≤ 𝜔1 ‖𝑑𝑘−1‖ ‖𝑔𝑘−1‖ 2 . (24) Proof ‎From Lemma 1‎, ‎we have‎ 𝑔𝑘−1 𝑇 𝑑𝑘−1 ≤ − 7 8 ‖𝑔𝑘−1‖ 2, so that 1 |𝑔𝑘−1 𝑇 𝑑𝑘−1| ≤ 8 7‖𝑔𝑘−1‖ 2 . (25) ‎By the definition of 𝛽𝑘 1‎, we obtain‎ |𝛽𝑘 1| = |− 𝑔𝑘 𝑇 𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 | = | 𝑔𝑘 𝑇 𝑦𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 |. ‎Then‎, ‎from the Cauchy-Schwarz inequality‎, ‎(H2), (22) and (25), ‎we get‎ |𝛽𝑘 1| ≤ ‖𝑔𝑘 ‖‖𝑦𝑘−1‖ |𝑔𝑘−1 𝑇 𝑑𝑘−1| ≤ 8𝛾𝐿𝛼𝑘−1‖𝑑𝑘−1‖ 7‖𝑔𝑘−1‖ 2 = 𝜔1 ‖𝑑𝑘−1‖ ‖𝑔𝑘−1‖ 2 , with 𝜔1: = 8𝛾𝐿𝛼𝑚𝑎𝑥 7 .  Lemma 3 Suppose that (H2) holds and the tuning parameter 𝛼𝑚𝑎𝑥‎ is given‎. ‎Then‎, ‎there exists a constant ω2 > 0 such that‎ |𝛽𝑘 2| ≤ 𝜔2 ‖𝑑𝑘−1‖ 2 ‖𝑔𝑘−1‖ 2 . (26) Proof (H2)‎, ‎(15) and (25) result in‎ |𝛽𝑘 2| = |− ‖𝑦𝑘−1‖ 2 𝑔𝑘−1 𝑇 𝑑𝑘−1 | = ‖𝑦𝑘−1‖ 2 |𝑔𝑘−1 𝑇 𝑑𝑘−1| ≤ 8𝐿2𝛼𝑘−1 2 ‖𝑑𝑘−1‖ 2 7‖𝑔𝑘−1‖ 2 = 𝜔2 ‖𝑑𝑘−1‖ 2 ‖𝑔𝑘−1‖ 2 , where 𝜔2 ≔ 8𝐿2𝛼𝑚𝑎𝑥 2 7 .  Lemma 4 ‎If (H2) holds‎, ‎then there exists constant 𝜔3 > 0 such that‎ |𝑡𝑘 | ≤ 𝜔3 ‖𝑑𝑘−1‖ ‖𝑔𝑘−1‖ 2 . (27) RAHPEYMAII F. ROSTAMI M. 94 Proof ‎The Cauchy-Schwarz inequality‎, ‎(17)‎, ‎(22) and (25) imply‎ |𝑡𝑘 | = |2 𝑔𝑘 𝑇 𝑑𝑘−1 𝑔𝑘−1 𝑇 𝑑𝑘−1 | ≤ 2 ‖𝑔𝑘 ‖‖𝑑𝑘−1‖ |𝑔𝑘−1 𝑇 𝑑𝑘−1| ≤ 16𝛾‖𝑑𝑘−1‖ 7‖𝑔𝑘−1‖ 2 = 𝜔3 ‖𝑑𝑘−1‖ ‖𝑔𝑘−1‖ 2 , in which 𝜔3 ≔ 16𝛾 7 .  Lemma 5 Suppose that (H1) and (H2) hold. ‎If the sequence {𝑑𝑘 } be generated by Algorithm 1,‎‎then there exists a constant 𝑀 > 0 such that‎ ‖𝑑𝑘 ‖ ≤ 𝑀, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑘 ≥ 0. (28) Proof ‎We use induction to prove this lemma. First(22)‏ implies that ‖𝑑0‖ = ‖𝑔0‖ ≤ 𝛾. From the assumption of induction ‖𝑑𝑘−1‖ is bounded. Hence, the exists constant 𝑀 ∗ > 0 such that‎ ‖𝑑𝑘−1‖ ≤ 𝑀 ∗. (29) Now, the definitions of 𝑑𝑘 and 𝛽𝑘 𝑛𝑒𝑤‎, give‎ ‖𝑑𝑘 ‖ = ‖−𝑔𝑘 + 𝛽𝑘 𝑛𝑒𝑤 𝑑𝑘−1‖ ≤ ‖𝑔𝑘‖ + |𝛽𝑘 𝑛𝑒𝑤|‖𝑑𝑘−1‖ ≤ ‖𝑔 𝑘 ‖ + (|𝛽 𝑘 1| + |𝑡𝑘||𝛽𝑘 2|)‖𝑑𝑘−1‖. ‎We get from (22)‎, (29) and Lemmas 2-4 that‎ ‖𝑑𝑘 ‖ ≤ 𝛾 + (𝜔1 ‖𝑑𝑘−1‖ ‖𝑔 𝑘−1 ‖ 2 + 𝜔2 𝜔3 ‖𝑑𝑘−1‖ 3 ‖𝑔 𝑘−1 ‖ 4 ) ‖𝑑𝑘−1‖ ≤ 𝛾 + ( 𝜔1 𝜀2 ‖𝑑𝑘−1‖ + 𝜔2𝜔3 𝜀4 ‖𝑑𝑘−1‖ 3) ‖𝑑𝑘−1‖. ≤ 𝛾 + ( 𝜔1 𝜀2 𝑀∗ + 𝜔2 𝜔3 𝜀4 (𝑀∗)3) 𝑀∗ ≔ 𝑀. ‎ The following result is a theorem in [29]. Lemma 6 Let 𝑑𝑘 be a sufficient descent direction and assume the step size 𝛼𝑘 satisfies the strong Wolfe line search (12) and (14). Then, based on (H1) and (H2), we have ∑ (𝑔𝑘 𝑇𝑑𝑘) 2 ‖𝑑𝑘‖ 2 < +∞. ∞𝑘=0 (30) Theorem 1 Let 𝑑𝑘 be a sufficient descent direction and {𝑥𝑘 } be the generated sequence by Algorithm 1. Also, (H1) and (H2) hold. Then lim𝑛→∞ inf ‖𝑔𝑘 ‖ = 0. (31) Proof From Lemma 5, we obtain ∑ 1 ‖𝑑𝑘‖ 2 ≥ ∑ 1 𝑀2 = +∞∞𝑘=0 . ∞ 𝑘=0 (32) We use contradiction to prove this theorem. Hence, there exists a constant 𝜖 > 0 such that ‖𝑔𝑘 ‖ ≥ 𝜖. (33) Let Ξ𝑘 = 𝑔𝑘 𝑇𝑑𝑘 ‖𝑔𝑘‖‖𝑑𝑘‖ . (34) Using Lemma 1, we obtain Ξ𝑘 = 𝑔𝑘 𝑇𝑑𝑘 ‖𝑔𝑘‖‖𝑑𝑘‖ ≤ − 7 8 ‖𝑔𝑘‖ 2 ‖𝑔𝑘‖‖𝑑𝑘‖ = − 7 8 ‖𝑔𝑘‖ ‖𝑑𝑘‖ , (35) so that Ξ𝑘 2 ≥ 49 64 ‖𝑔𝑘‖ 2 ‖𝑑𝑘‖ 2 . (36) From (33), (34) and (36), we can obtain 49 64 𝜖2 ‖𝑑𝑘‖ 2 ≤ 49 64 ‖𝑔𝑘‖ 2 ‖𝑑𝑘‖ 2 ≤ Ξ𝑘 2 = (𝑔𝑘 𝑇𝑑𝑘) 2 ‖𝑔𝑘‖ 2‖𝑑𝑘‖ 2 ≤ (𝑔𝑘 𝑇𝑑𝑘) 2 𝜖2‖𝑑𝑘‖ 2 . (37) SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS 95 By taking sums from both sides (37) and using Lemma 6, we have ∑ 1 ‖𝑑𝑘 ‖ 2 ≥ ∑ (𝑔𝑘 𝑇 𝑑𝑘 ) 2 ‖𝑑𝑘 ‖ 2 < +∞ ∞ 𝑘=0 , ∞ 𝑘=0 which contradicts with (32). Hence, the proof of the desired result is completed.  4. Numerical experiments ‎This section gives numerical results of some algorithms on a set of the nonlinear unconstrained optimization‎‎ ‎ ‎test problems from CUTEst collection [11], ‎given in Table 1‎. ‎The dimensions of test problems are from 2 to‎‎12005 while the initial points are standard ones proposed in CUTEst‎.‎ ‎We apply the following algorithms to solve these test problems‎:  M1: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 1𝑑𝑘−1.  M2: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 2𝑑𝑘−1.  M3: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 𝑛𝑒𝑤 𝑑𝑘−1.  M4: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 𝑛𝑒𝑤+𝑑𝑘−1 and 𝛽𝑘 𝑛𝑒𝑤+ ≔ 𝑚𝑎𝑥{0, 𝛽𝑘 𝑛𝑒𝑤 }.  DY: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 𝐷𝑌 𝑑𝑘−1.  HZ: Conjugate gradient method with 𝑑𝑘 ≔ −𝑔𝑘 + 𝛽𝑘 𝐻𝑍 𝑑𝑘−1. All algorithms are implemented in Matlab 2011 programming environment on a 2.3Hz Intel core i3 processor‎ laptop and 4GB of RAM with the double precision data type in Linux operations system‎. All algorithms are terminated whenever the inequality‎‎‖𝑔𝑘 ‖ < 10 −6‎ holds or the maximum number of iterations exceeds 10000‎. ‎The tuning strong Wolfe line search parameters are taken as‎ 𝜌 = 0.0001, 𝜎 = 0.9, 𝛼𝑚𝑖𝑛 = 10 −8 and 𝛼𝑚𝑎𝑥 = 10 8. ‎Here‎, ‎we use the performance profiles of Dolan & More [5] to compare M1‎, M2‎,‎ M3, M4, DY ‎and HZ‎‎ algorithms on the test problems‎.‎‎We consider 𝑃 as designates the percentage of problems which are solved‎‎‎within a factor 𝜏 of the best solver‎. ‎The horizontal axis of the figure gives the percentage of the test problems‎‎‎for which an algorithm is the fastest (efficiency)‎, ‎while the vertical axis gives the percentage of the test problems‎‎ ‎that were successfully solved by each algorithm (robustness)‎. ‎Figures 1-3 show that M4 is the best in terms of the total number of iterations‎,‎ ‎the total number of function evaluations and time in seconds‎‏ ‎in comparison with others‎. Table 1. Test functions taken from CUTEst collection. No. Test function Dim No. Test function Dim No. Test function Dim 1 3PK 3 49 DQDRTIC 10000 97 NONDIA 1000 2 AIRCRFTB 8 50 DQRTIC 5000 98 NONDQUAR 3000 3 ALLINIT 4 51 EDENSCH 100 99 OSCIPANE 5000 4 ALLINITU 4 52 EG2 1000 100 OSCIPATH 2 5 ARGLINA 500 53 EG3 10000 101 OSLBQP 8 6 ARGLINB 200 54 EIGENA 2550 102 PALMER1C 8 7 ARWHEAD 5000 55 ENGVAL1 100 103 PALMER1D 7 8 BARD 3 56 ENGVAL2 3 104 PALMER2C 8 9 BDQRTIC 100 57 ERRINROS 50 105 PALMER3C 8 10 BEALE 2 58 EXPFIT 2 106 PALMER4C 8 11 BIGGS6 6 59 EXTROSNB 1000 107 PALMER5C 6 12 BIGGSB1 100 60 FLETCBV2 10000 108 PALMER6C 8 13 BOX2 3 61 FLETCHCR 500 109 PALMER7C 8 14 BOX3 3 62 FMINSRF2 5625 110 PALMER8A 6 15 BRKMCC 2 63 FMINSURF 5625 111 PALMER8C 8 16 BROWNDEN 4 64 FREUROTH 2 112 PENALTY1 100 17 BROYDN3D 5000 65 GENHUMPS 500 113 PENALTY2 50 18 BROYDN7D 500 66 GENROSE 500 114 POWELLBC 1000 19 BROYDNBD 5000 67 GROWTHLS 3 115 POWELLSG 5000 20 BRYBND 500 68 GULF 3 116 QR3DLS 610 21 CHAINWOO 1000 69 HAIRY 2 117 QUARTC 25 22 CHNROSNB 50 70 HATFLDD 3 118 ROSENBR 2 23 CLIFF 2 71 HATFLDF 3 119 S308 2 RAHPEYMAII F. ROSTAMI M. 96 24 COSINE 1000 72 HATFLDFL 3 120 SCHMVETT 100 25 CRAGGLVY 1000 73 HEART6LS 6 121 SENSORS 2 26 CUBE 2 74 HEART8LS 8 122 SINEVAL 2 27 CUBENE 2 75 HELIX 3 123 SINVALNE 2 28 DALLASM 196 76 HILBERTA 10 124 SISSER 2 29 DALLASS 46 77 HILBERTB 10 125 SNAIL 2 30 DECONVU 63 78 HIMMELBA 2 126 SPARSINE 1000 31 DENSCHNA 2 79 HIMMELBC 2 127 SPARSQUR 10000 32 DENSCHNB 2 80 HIMMELBF 4 128 SPMSRTLS 4999 33 DENSCHNC 2 81 HIMMELBG 2 129 SROSENBR 1000 34 DENSCHNF 2 82 HIMMELBH 2 130 TAME 2 35 DIXMAANA 9000 83 HUMPS 2 131 TESTQUAD 100 36 DIXMAANB 3000 84 JENSMP 2 132 TOINTGOR 50 37 DIXMAANC 3000 85 KOWOSB 4 133 TOINTGSS 10000 38 DIXMAAND 3000 86 LIARWHD 5000 134 TOINTPSP 50 39 DIXMAANE 3000 87 LOGHAIRY 2 135 TOINTQOR 50 40 DIXMAANF 3000 88 MANCINO 100 136 TQUARTIC 10 41 DIXMAANG 3000 89 MATRIX2 6 137 TRIDIA 5000 42 DIXMAANH 3000 90 METHANOL 12005 138 VAREIGVL 500 43 DIXMAANI 3000 91 MODBEALE 2 139 VIBRBEAM 8 44 DIXMAANJ 3000 92 MOREBV 5000 140 WATSON 12 45 DIXMAANK 3000 93 MSQRTALS 1024 141 WEEDS 3 46 DIXMAANL 3000 94 MSQRTBLS 1024 142 WOODS 100 47 DIXON3DQ 1000 95 MINE5D 10733 143 YFITU 3 48 DJTL 2 96 NONCVXU2 1000 144 ZANGWIL2 2 Figure 1. Dolan-More performance profiles for the total number of iterations. SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS 97 Figure 2. Dolan-More performance profiles for the total number of function evaluations. Figure 3. Dolan-More performance profiles for the time in seconds. RAHPEYMAII F. ROSTAMI M. 98 5. Conclusion In this paper‎, ‎we proposed a new conjugate gradient method for solving the unconstrained optimization problems with improving and combining LS and CD parameters‎. ‎The new search directions of our algorithm satisfy‎‎ ‎the sufficient descent condition‎. ‎It inherits the strong global convergence properties of CD‎‎‎and the numerical efficiency of LS‎. ‎The global convergence under some mild assumptions is stablished‎.‎‎Our numerical experiments show that M4 is better than other algorithms in terms of‎‎‎the total number of iterations‎, ‎the number of function evaluations and time in seconds‎. Conflict of interest The authors declare no conflict of interest. Acknowledgment The authors would like to thank the editor and reviewers for their valuable comments which helped to improve the manuscript. References 1. Al-Baali, M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA Journal of Numerical Analysis, 1985, 5, 121-124. 2. Alhawarat, A., Salleh, Z. and Masmali, I.A. A convex combination between two di_erent search directions of conjugate gradient method and application in image restoration, Mathematical Problems in Engineering, 2021. 3. Conn, A. R., Gould, N.I.M. and Toint, P.L. Convergence of quasi-Newton matrices generated by the symmetric rank one update, Mathematical programming, 1991, 50, 177-195. 4. Dai, Y.H. and Yuan, Y. A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 1999, 10, 177-182. 5. Dolan, E.D. and More, J.J. Benchmarking optimization software with performance profiles, Mathematical Programming, 2002, 91, 201-213. 6. Esmaeili, H. and Kimiaei, M. An improved adaptive trust-region method for unconstrained optimization, Mathematical Modelling and Analysis, 2014, 19(4), 469-490. 7. Fletcher, R. Practical Methods of Optimization, John Wiley & Sons, New York, 1987. 8. Fletcher, R. and Reeves, C. Function minimization by conjugate gradients, Computer Journal, 1964, 7(2), 149-154. 9. Gill, P. and Murray, W. Quasi-Newton methods for unconstrained optimization, IMA Journal of Applied Mathe- matics, 1972, 9(1), 91-108. 10. Gill, P. and Leonard, M. W. Reduced-Hessian quasi-Newton methods for unconstrained optimization, SIAM Journal on Optimization, 2001, 12(1), 209-237. 11. Gould, N.I.M., Orban, D. and Toint, P.L. CUTEst: A constrained and unconstrained testing environment with safe threads, Technical Report, RAL-TR-2013-005. 12. Griewank, A. The global convergence of Broyden-like methods with a suitable line search, Journal of the Australian Mathematical Society Ser. B, 1986, 28, 75-92. 13. Hager, W.W. and Zhang, H. A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on optimization, 2005, 16(1), 170-192. 14. Hager, W.W. and Zhang, H. The limited memory conjugate gradient method, SIAM Journal on Optimization, 2013, 23(4), 2150-2168. 15. Hestenes, M.R. and Stiefel, E.L. Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 1952, 49, 409-436. 16. Kimiaei, M. and Ghaderi, S. A new restarting adaptive trust-region method for unconstrained optimization, Journal of the Operations Research Society of China, 2017, 5, 487-507. 17. Kimiaei, M. and Rostami, M. Impulse noise removal based on new hybrid conjugate gradient approach, Kybernetika, 2016, 5, 791-823. 18. Li, Z.F., Chen, J. and Deng, N.Y. A new conjugate gradient method and its global convergence properties, Math- ematical Programming, 1997, 78, 375-391. 19. Li, M. and Feng, H. A sufficient descent LS conjugate gradient method for unconstrained optimization problems, Applied Mathematics and Computation, 2011, 218, 1577-1586. 20. Liu, Y.L. and Storey, C. Efficient generalized conjugate gradient algorithms, part1, Journal of Optimization Theory and Applications, 1991, 69(1), 129-137. 21. Nocedal, J. and Wright, S.J. Numerical Optimization, Springer series in Operation Research, Springer, New York,1999. SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS 99 22. Ortega, J.M. and Rheinboldt, W.C. Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. 23. Polak, E. and Ribiere, G. Note sur la convergence de directions conjugees, Rev. Francaise Informat Recherche Opertionelle, 3e Annee, 1969, 16, 35-43. 24. Polyak, B.T. The conjugate gradient method in extreme problems, USSR Computational Mathematics and Mathematical Physics, 1969, 9, 94-112. 25. Rahpeymaii, F., Kimiaei, M. and Bagheri, A. A limited memory quasi-Newton trust-region method for box con- strained optimization, Journal of Computational and Applied Mathematics, 2016, 303, 105-118. 26. Yang, X., Luo, Z. and Dai, X. A global convergence of LS-CD hybrid conjugate gradient method, Advances in Numerical Analysis, https://doi.org/10.1155/2013/517452. 27. Zhang, L. A new Liu-Storey type nonlinear conjugate gradient method for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 2009, 225, 146-157. 28. Zhou, Q., Zhou, F. and Cao, F. A nonmonotone trust region method based on simple conic models for Unconstrained optimization, Applied Mathematics and Computation, 2013, 225, 295-305. 29. Zoutendijk, G. Nonlinear Programming, Computational Methods. In: Abadie J. (ed) Integer and Nonlinear Programming. Amsterdam, North-Holland, 1970, 37-86. Received 13 July 2021 Accepted 16 June 2022 https://www.sciencedirect.com/science/journal/03770427 https://doi.org/10.1155/2013/517452