# A Simple Sufficient Descent Method for Unconstrained Optimization

Authors: Ming-Liang Zhang; Yun-Hai Xiao; Dangzhen Zhou
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

We develop a sufficient descent method for solving large-scale unconstrained optimization problems. At each iteration, the search direction is a linear combination of the gradient
at the current and the previous steps. An attractive property of this method is that the generated directions are always descent. Under some appropriate conditions, we show that the proposed
method converges globally. Numerical experiments on some unconstrained minimization problems
from CUTEr library are reported, which illustrate that the proposed method is promising.


---

## Body

## 1. Introduction

In this paper, we consider the unconstrained optimization problem(1.1)min⁡f(x),x∈Rn,
where f:ℝn→ℝ is a continuously differentiable function, and its gradient at point xk is denoted by g(xk), or gk for the sake of simplicity. n is the number of variables, which is automatically assumed to be large. Large-scale optimization is one of the important research areas both in optimization theory and algorithm design. There exist some kinds of effective methods available for solving (1.1), as for instance, inexact Newton, limited memory quasi-Newton, conjugate gradient, spectral gradient, and subspace methods [1–4].The iterative formula the method is given by(1.2)xk+1=xk+αkdk,
where αk is a steplength, and dk is a search direction. Generally, we say that dk is a descent direction of f at xk if dk⊤gk<0. Furthermore, if there exists a positive constant C>0 such that dk⊤gk≤-C∥gk∥2, then dk is often called a sufficient descent direction. The descent property is very important for the iterative method to be global convergent, especially for the conjugate gradient method [5]. Unfortunately, for the earliest spectral gradient method [6] and the PRP conjugated gradient method, their generated directions are not always descent. Therefore, in the last years, much effort has been done to smooth away the drawback and develop new methods, for example, [7].As is wellknown, if Armijo line search is used, the standard PRP method can cycle infinitely without approaching any optimal point when solving nonconvex minimization problems. To overcome this drawback, Hager and Zhang [8] made a slight modification on the PRP formula. Consequently, the resulting method own the remarkable property: for any line search, the generated direction always satisfies the sufficient descent condition dk⊤gk≤-(7/8)∥gk∥2. Moreover, Zhang et al. [9] further studied the PRP formula and proposed a three-term modified PRP method, in which the generated directions satisfy(1.3)dk⊤gk=-‖gk‖2,
and this property is independent of any line search. Additionally, for improving the numerical performance of the standard FR method, Zhang et al. [10] developed a modified FR method where the direction also satisfy (1.3).Although much progress has been made in designing a sufficient descent direction in a conjugate gradient method, it seemingly receive little attention in other methods. Very recently, An et al. [5] proposed a robust technique to construct a sufficient descent direction for unconstrained optimization. The descent direction is a linear combination of the steepest descent direction and the projection of the original direction, that is,(1.4)dk=-gk+λk(I-gkgk⊤‖gk‖2)d¯k,
where λk is a scalar and d¯k is an original direction. Based on the definition of dk, it is easy to deduce that the sufficient descent condition (1.3) holds. This technique has been applied to the PSB updated formula and showed that the resulting method converges globally and superlinearly for an uniformly convex function. Moreover, the direction in [11] is truly a special case of (1.4).We note that (1.4) can be considered as a general form of a nonlinear conjugate gradient method, in which(1.5)dk=-gk+βkdk-1,
where βk is a scalar. Comparing with (1.4), we see that the scalar βk takes the place of the coefficient matrix of d¯k. In this paper, we further study the sufficient descent technique (1.4), and propose a simple sufficient descent method for solving unconstrained optimization problems. Our motivation is simple, we choose d¯k as the gradient of the previous step in (1.4). The search direction in this proposed method always satisfies a sufficient descent condition. Under some conditions, we show that the algorithm converges globally by using a special line search. The performance of the method on some CUTEr test problems indicates that it is encouraging.We organize this paper as follows. In the next section, we construct the sufficient descent direction. In Section3, we state the steps of our new algorithm with a special line search. We also report some experiments on some large-scale unconstrained optimization problems. Finally, we conclude this paper with some remarks in the last section. Throughout this paper, the symbol ∥·∥ denotes the Euclidean norm of a vector.


## 2. New Search Direction

This section aims to state the new direction formula and investigate its properties. Now, if we takegk-1 as d¯k and set λk≡1 in (1.4), we get(2.1)dk=-gk+(I-gkgk⊤‖gk‖2)gk-1.
Obviously, the direction is a linear combination of the gradient at the current and the previous steps. Additionally, to obtain the global convergence of PRP method, Cheng [11] introduced a descent direction defined as(2.2)dk=-gk+βkPRP(I-gkgk⊤‖gk‖2)dk-1.
We note that (2.2) is only a special choice of (1.4), in which d¯k is replaced by dk-1 and λk is chosen as the scalar βkPRP. If we denote(2.3)Hk=I-gkgk⊤‖gk‖2,
then it is easy to see that for any y≠0, we have (2.4)y⊤Hky=y⊤HkHk⊤y=‖Hk⊤y‖2≥0,
which indicates that Hk is a symmetric and positive semidefinite matrix.


## 3. Sufficient Descent Method

As we have stated in the previous section, the directions in (2.1) satisfy a sufficient descent condition. In this section, we list our algorithm and establish its global convergence.Firstly, we state the steps of the simple sufficient descent method. In order to achieve the global convergence of our method, we consider the backtracking line search of Grippo and Lucidi (GL) [12]. That is, for given δ∈(0,1), β>0, ρ∈(0,1), find the first jk (j=1,2,…) such that αk=βρjk satisfies(3.1)f(xk+αkdk)≤f(xk)-δαk2‖dk‖2.Now, we are ready to state the steps of the Simple Sufficient Descent (SSD) method.Algorithm 3.1 (SSD).
We have the following steps.Step 1.
Givenx0∈ℝn. Let 0<δ<1, and d0=-g0. Set k:=0.Step 2.
If∥gk∥=0, then stop.Step 3.
Computedk by (2.1).Step 4.
Find the steplengthαk satisfying (3.1). Let xk+1=xk+αkdk.Step 5.
Setk:=k+1, go to Step 2.The remainder of this section is devoted to investigate the global convergence of Algorithm3.1. We first state some assumptions.Assumption.
Functionf is continuously differentiable and the level set ℱ={x∈ℝn∣f(x)≤f(x0)} is bounded.Assumption.
The gradient off is Lipschitz continuous, that is, there exists a constant L>0 such that
(3.2)‖g(x)-g(y)‖≤L‖x-y‖,∀x,y∈Rn.We first prove the following lemma.Lemma 3.4.
Let the sequence{xk} be generated by Algorithm 3.1. Suppose that Assumptions 3.2 and 3.3 hold. Then,
(3.3)∑k=0∞‖gk‖2‖dk‖2<∞.Proof.
We have the following cases.Case 1.
Consider firstly the GL line search (3.1). If αk≠β, then ρ-1αk may not satisfy (3.1). That is,
(3.4)f(xk+ρ-1αkdk)>f(xk)-δρ-2αk2‖dk‖2.
By the mean value theorem and Assumption 3.3, there exists θk∈(0,1) such that
(3.5)f(xk+ρ-1αkdk)-f(xk)=ρ-1αkg(xk+θkρ-1αkdk)⊤dk=ρ-1αkgk⊤dk+ρ-1αk(g(xk+θkρ-1αkdk)⊤-gk)dk≤ρ-1αkgk⊤dk+Lρ-2αk2‖dk‖2,
where L>0 is the Lipschitz constant of g. Substituting the last inequality into (3.4), we get
(3.6)αk≥-1ρ-1(L+δ)‖gk‖2‖dk‖2=c1‖gk‖2‖dk‖2.
This implies that there is a constant M>0 such that
(3.7)‖gk‖4‖dk‖2≤M(f(xk)-f(xk+1)).Case 2.
Ifα=β, then we have
(3.8)‖gk‖4‖dk‖2≤‖gk‖2≤‖dk‖2≤δ-1β-2(f(xk)-f(xk-1)),
which shows that (3.7) holds with M=δ-1β-2. Moreover, (3.7) indicates the lemma claims.Theorem 3.5.
Let{xk} be generated by Algorithm 3.1 with GL backtracking line search (3.1). Then
(3.9)lim⁡inf⁡k→∞‖gk‖=0.Proof.
From Assumption3.3, we know that there exists a positive constant γ¯ such that
(3.10)‖gk‖≤γ¯.
By the definition of dk in (2.1), we have
(3.11)‖dk‖≤‖gk‖+‖Hkgk-1‖≤‖gk‖+‖gk-1‖≤2γ¯,
which shows that ∥dk∥ is bounded. We get from (3.1) that
(3.12)∑k=0∞αk2‖dk‖2<∞.
Consequently, we have
(3.13)lim⁡k→∞αk‖dk‖=0.
For the sake of contradiction, we suppose that (3.9) does not hold. Then there is a constant ϵ>0 such that ∥gk∥≥ϵ for all k≥0.
Ifliminfk→∞αk>0, we get from (3.13) that liminfk→∞∥dk∥=0, which shows liminfk→∞∥gk∥=0. This contradicts the assumption (3.9).
Ifliminfk→∞αk=0, that is, there is an infinite index set K such that(3.14)lim⁡k∈K,k→∞αk=0.
It follows from the line search step in Algorithm 3.1 that when k∈K is sufficiently large, ρ-1αk does not satisfy (3.1). Then from the first part of the proof of Lemma 3.4 we see that (3.6) holds. Since ∥dk∥ is bounded and limk∈K,k→∞αk=0, (3.6) implies liminfk→∞∥gk∥=0. This also yields a contradiction. The proof is complete.


## 4. Numerical Results

In this section, we test the feasibility and effectiveness of the Algorithm SSD. The algorithm is implemented in Fortran77 code using double precision arithmetic. All runs are performed on a PC ( Intel Pentium Dual E2140 1.6 GHz, 256 MB SDRAM) with Linux operations system. The algorithm stops if the infinity-norm of the final gradient is below 10−5, that is(4.1)‖∇f(x)‖≤10-5.
The iteration is also stopped if the number of iterations exceeds 10000 or the number of function evaluations reaches 20000. Our experiments are performed on the subset of the nonlinear unconstrained problems from CUTEr [13] collection. The second-order derivatives of all the selected problems are available. Since we are interested in large problems, we refined this selection by considering only problems where the number of variables is at least 50. The parameter in line search (3.1) is taken as: β=1, ρ=0.1, and δ=10-4. The numerical results of the algorithms SSD are listed in Table 1. The columns have the following meanings: Problem: name of the test problem,Dim: dimension of the test problem,Iter: number of iterations,Nf: number of function evaluations,Time: CPU time in seconds,Fv: final function value,Norm-2:l2-norm of the final gradient, andNorm-0:∞-norm of the final gradient.Table 1
Test results for SSD method.
ProblemDimIterNfTimeFvNorm-2Norm-0ARGLINA200230.010.2000000E+030.15350E-120.28232E-23ARWHEAD500012340.030.5550005E-120.80345E-050.89063E-10BROWNAL200317551261.400.1475222E-080.29801E-050.93967E-10BROYDN7D50005986966420.090.1815779E+040.17731E-050.20076E-10BRYBND50001051600.280.3534654E-110.29153E-050.29287E-10DIXMAANA30001401900.110.1000000E+010.24750E-060.93362E-10DIXMAANB30001301790.100.1000000E+010.30449E-060.61730E-10DIXMAANC30001201660.100.1000000E+010.10046E-050.86335E-10DIXMAAND30001391880.110.1000000E+010.15385E-050.77064E-10QDRTIC5000109517571.720.2290216E-100.95704E-050.94807E-10DQRTIC50001962820.110.3480734E-060.68218E-060.46755E-10EDENSCH2000871360.060.1200328E+050.38002E-050.97655E-10ENGVAL15000701200.120.5548668E+040.37840E-050.82778E-10FLETCBV25000010.00-0.5002682E+000.79960E-070.19455E-10MANCINO10026560.710.3102390E-170.91840E-060.23394E-10QUARTC50001962820.110.3480734E-060.68218E-060.46755E-10SCHMVETT50002553861.12-0.1499400E+050.68017E-050.67249E-10SENSORS100561840.85-0.2101781E+040.46106E-050.35706E-10SPMSRTLS4999348956298.740.1833147E-080.90139E-050.96204E-10TOINTGSS5000911320.110.1000400E+020.76757E-050.60378E-10VARDIM200120.000.1479114E-300.44409E-150.59165E-30VAREIGVL50671060.000.1042896E-100.38234E-050.87845E-10EG21000450.00-0.9989474E+030.13514E-050.18263E-11MOREBV50001722790.220.1462269E-080.42417E-050.88342E-10TOINTGOR50143223030.020.1373905E+040.49818E-050.88106E-10TOINTQOR502473760.000.1175472E+040.55492E-050.88045E-10In addition, we also present extensive numerical results of the state-of-the-art algorithm CG_DESCENT [8, 14]. CG_DESCENT is a conjugate gradient descent method for solving large-scale unconstrained optimization problems. A new nonmonotone line search were used in CG_DESCENT which makes this algorithm very efficient. The Fortran code can be obtained from http://www.math.ufl.edu/~hager/. When running of CG_DESCENT, default values are used for all parameters. The results are summarized in Table 2.Table 2
Test results for CG_DESCENT.
ProblemDimIterNfNgTimeFvNorm-2ARGLINA2001320.010.20000E+030.21133E-06ARWHEAD5000919120.020.00000E+000.83931E-06BROWNAL200415130.010.14731E-080.11790E-05BROYDN7D50001444288514535.130.19785E+040.68854E-05BRYBND50003164340.100.14292E-100.65055E-05DIXMAANA300081790.010.10000E+010.15586E-05DIXMAANB3000919100.000.10000E+010.35546E-06DIXMAANC30001021110.010.10000E+010.70236E-06DIXMAAND30001123120.010.10000E+010.32593E-05DQDRTIC500071580.020.41826E-140.18957E-06DQRTIC50003265330.020.28560E-040.30250E-05EDENSCH20002956330.020.12003E+050.74432E-05ENGVAL150002345320.050.55487E+040.53164E-05FLETCBV250000110.01-0.50027E+000.79960E-07MANCINO1001123120.300.20215E-170.97074E-06QUARTC50003265330.020.28560E-040.30250E-05SCHMVETT50003563460.19-0.14994E+050.90275E-05SENSORS1002355400.19-0.21085E+040.29929E-05SPMSRTLS49991863791950.510.19502E-080.82452E-05TOINTGSS50003740.010.10002E+020.60471E-05VARDIM2002857290.000.27052E-220.20805E-08VAREIGVL5052142900.000.40508E-100.71079E-05EG210003740.00-0.99895E+030.81318E-05MOREBV50003265340.040.10103E-080.89736E-05TOINTGOR501072061210.000.13739E+040.88894E-05TOINTQOR502855310.000.11755E+040.49970E-05Observing the tables, we see that SSD works well, as it reached a stationary point based on the stopping criterion (4.1) for almost all these test problems. Although SSD requires large number of iterations or function evaluations, it needs less time consuming comparatively. However, the numerical comparisons tell us that the state-of-the-art algorithm CG_DESCENT performs a little better than SSD, but for some specific problems, the enhancement of SSD is still noticeable. The numerical experiments also show that SSD can potentially used to solve unconstrained optimization problems with higher dimensions.


## 5. Concluding Remarks

In this paper, motivated by a descent technique, we have proposed a simple sufficient descent method for solving large-scale unconstrained optimization problems. At each iteration, the generated directions are only related to the gradient information of two successive points. Under some mild conditions, we have shown that this method is global convergent. The numerical results indicate that it works well on some selected problems from CUTEr library. We think there are several other issues that could be lead to improvements. A first point that should be considered is probably the choice of a nonmonotone line search technique. We have adopted the monotone scheme of Grippo and Lucidi (3.1), but this is not the only possible choice, and the framework developed in [15, 16] may allow one to achieve a better performance. Similar to [5], another important point that should be further investigated is a modification of the search direction without violating the nice sufficient descent property. To this end, it is interesting to note that this method is capable of solving nonlinear systems of equations without Jacobian information and cheaply computing.



---

*Source: 684705-2010-12-09.xml*