Neculai ANDREI^1,2
1 Center for Advanced Modeling and Optimization,
I C I Bucharest
(National Institute for R & D in Informatics)
8-10 Averescu Blvd.
011455 Bucharest 1, Romania
nandrei@ici.ro
² Academy of Romanian Scientists
54, Splaiul Independenţei, Bucharest 5, Romania

Abstract: A numerical evaluation and comparisons using performance profiles of some representative conjugate gradient algorithms for solving a large variety of large-scale unconstrained optimization problems are carried on. In this intensive numerical study we selected eight known conjugate gradient algorithms: Hestenes and Stiefel (HS), Polak-Ribière-Polyak (PRP), CONMIN, ASCALCG, CG-DESCENT, AHYBRIDM, THREECG and DESCON. These algorithms are different in many respects. However, they have a lot of concepts in common, which give the numerical comparisons sense and confident expectations. The initial search direction in all algorithms is the negative gradient computed in the initial point and the step length is computed by the Wolfe line search conditions. Excepting CONMIN and CG-DESCENT, all the algorithms from this numerical study implement an acceleration scheme which modifies the step length in a multiplicative manner to improve the reduction of the functions values along the iterations. The numerical study is based on a set of 800 artificially large-scale unconstrained optimization test functions of different complexity and with different structures of their Hessian matrix. A detailed numerical evaluation based on performance profiles is applied to the comparisons of these algorithms showing that all of them are able to solve difficult large-scale unconstrained optimization problems. However, comparisons using only artificially test problems are weak and dependent on arbitrary choices concerning the stopping criteria of the algorithms and on decision of whether an algorithm found a solution or not. To get definitive conclusions using this sort of comparisons based only on artificially test problems is an illusion. However, using some real unconstrained optimization applications we can get a more confident conclusion about the efficiency and robustness of optimization algorithms considered in this numerical study.

Keywords: Large scale unconstrained optimization. Conjugate gradient algorithms. Numerical comparisons. Benchmarking, Performance profiles, Data profiles, MINPACK-2 applications.

>>Full text
CITE THIS PAPER AS:
Neculai ANDREI, A Numerical Study on Efficiency and Robustness of Some Conjugate Gradient Algorithms for Large-scale Unconstrained Optimization, Studies in Informatics and Control, ISSN 1220-1766, vol. 22 (4), pp. 259-284, 2013. https://doi.org/10.24846/v22i4y201302

Introduction

Conjugate gradient method represents an important computational innovation for continuously differentiable large scale unconstrained optimization with strong local and global convergence properties and very modest and predictable memory requirements. This family of algorithms includes a lot of variants and extensions with important convergence properties and numerical efficiency. Different from the Newton or quasi-Newton methods (including here the limited-memory quasi-Newton methods), the descent condition plays a crucial role in convergence of the conjugate gradient algorithms. As a characteristic the searching directions in conjugate gradient algorithms are selected in such a way that, when applied to minimize a strongly quadratic convex function, two successive directions are conjugate, subject to the Hessian of the quadratic function. Therefore, to minimize a convex quadratic function in a subspace spanned by a set of mutually conjugate directions is equivalent to minimize this function along each conjugate direction in turn. This is a very good and productive idea, leading us to many variants of conjugate gradient algorithms, but the performance of these algorithms is strongly dependent on the accuracy of the line search.

For solving the nonlinear unconstrained optimization problem:

                                                                                                                              (1)

where is a continuously differentiable function, bounded from below, starting from an initial guess x₀, a nonlinear conjugate gradient algorithm generates a sequence of points {x_k}, according to the following recurrence formula

,                                                                                                                 (2)

where α_k is the step length, usually obtained by Wolfe line search [51, 52],

                                                                          (3a)

                                                                                                              (3b)

with and the directions d_k are computed as:

,                                         (4)

Here β_k is a scalar known as the conjugate gradient parameter, and . In the following . Even that the conjugate gradient algorithms correspond to different choices for the parameter β_k, often they are designed in a specific manner in such a way that the search direction d_k satisfies the sufficient descent condition for some arbitrary positive constant c>0. In these algorithms, the conjugacy condition, or the modified conjugacy condition, is or where is a scalar. When applied to general nonlinear functions, often, the searching directions in conjugate gradient algorithms are computed using some formulas which do not satisfy the conjugacy condition. However, by extension we call they conjugate gradient algorithms.

The elaboration of nonlinear optimization software using nonlinear conjugate gradient algorithms is a very active field of research. On one hand, many conjugate gradient algorithms have achieved a maturity stage and are frequently used for solving a wide range of real applied problems in a large variety of areas. On the other hand, plenty of conjugate gradient algorithms are continuously elaborated and therefore their efficiency and robustness need to be established. The development of different versions of nonlinear conjugate gradient algorithms can be presented as follows. Classical conjugate gradient algorithms: Hestenes and Stiefel [33], Fletcher and Reeves [26], Daniel [21], Polak and Ribière [42] and Polyak [43], conjugate descent by Fletcher [27], Liu and Storey [36] and Day and Yuan [22]. Hybrid conjugate gradient algorithms using projections: hybrid Dai-Yuan [23], Gilbert and Nocedal [28], Hu and Storey [34], Touati-Ahmed and Storey [50], hybrid Liu and Storey [36], and hybrid conjugate gradient algorithms using the concept of convex combination of classical schemes: convex combination of Hestenes-Stiefel and Dai-Yuan with Newton direction [3, 4, 8], convex combination of Polak-Ribière-Polyak and Dai-Yuan with conjugacy condition [7]. Scaled BFGS preconditioned conjugate gradient algorithms by Shanno [47, 48], Birgin and Martínez [18] and Andrei [2, 9]. Conjugate gradient algorithms with guaranteed descent and guaranteed conjugacy conditions by Hager and Zhang [32] and Andrei [12]. Three-term conjugate gradient algorithms [10, 11].

The purpose of this paper is to study the performance of some conjugate gradient algorithms in a controlled numerical environment to highlight the main differences among them and to indicate the developer of algorithms and practitioner the best algorithms and the types of problems that are well suited to each algorithm. Therefore, we are interested to see the efficiency and robustness of some conjugate gradient algorithms for solving a large class of large-scale unconstrained optimization problems. For this purposes from the above classes of algorithms we selected a number of eight conjugate gradient algorithms, which seem to be the most representative: Hestenes and Stiefel, (HS) [33], Polak-Ribière-Polyak (PRP) [42, 43], CONMIN [47-49], ASCALCG [2, 9], CG-DESCENT [32], AHYBRIDM [3, 8], THREECG [10] and DESCON [12]. For a numerical evaluation of these algorithms the performance profiles [24] or the data profiles [37] are now standards for presenting efficiency and robustness as well as the numerical comparisons. Besides, the collection of unconstrained optimization test problems used in evaluation may have a great influence on the conclusions of the numerical study of these algorithms. In order to see the performances of these algorithms we assembled a collection of 800 large-scale unconstrained optimization test problems of a large variety and of different complexity and different structures of their Hessian matrix. The comparisons among algorithms are presented using the performance profiles. Besides, a number of five applications from MINPACK-2 collection [14] have been used to see the performances of the conjugate gradient algorithms considered in this numerical study. Our study is limited by this collection of test problems we used. However, we have tried to consider a test set of considerable diversity. Some of the artificially test problems are quadratic or nearly quadratic, while others are cubic or cubic perturbed with quadratic and linear. Some are combinations of quadratics including exp, sin or cos functions. There are varying degrees of nonlinearity and ill-conditioning. The functions are expressed in extended or generalized form as a sum or difference of element functions [31]. It is worth saying that the Hessian of the functions from this collection has different structure: diagonal, block-diagonal, tri-diagonal or penta-diagonal, bounded-diagonal, bounded-block-diagonal, etc. or full Hessian. The numerical conclusions concerning the efficiency and robustness of algorithms are based on this sample of functions, but we hope that they may be more generally useful for both the developer of algorithms for unconstrained optimization or practitioners faced with solving practical applications.

All these eight Fortran codes, which implement the conjugate gradient algorithms considered in this numerical study, are not new. The oldest is CONMIN, the 1978 version written by Shanno and Phua [49]. CG-DESCENT is version 1.4, (2005) written by Hager and Zhang [32]. The most recent are ASCALCG (2010) [9], AHYBRIDM (2010) [8], THREECG (2013) [10] and DESCON (2013) [12], all written by Andrei. In our numerical experiments we do not try to tune the algorithms to a particular set of test problems, and a single fixed version of each algorithm with fixed parameters was used.

As a general conclusion of this numerical study we can indicate that the conjugate gradient software analyzed in this numerical study is able to solve a very large diversity of unconstrained optimization problems of different complexity and with different structures of the Hessian matrix. At least for this set of artificially test problems, concerning the efficiency, CG-DESCENT is slightly more efficient, followed by DESCON and followed by THREECG. Subject to robustness by far DESCON is the most robust, followed by THREECG and followed by ASCALCG. It seems that the conjugate gradient algorithms implementing both the sufficient descent condition and the conjugacy condition are the best. However, this is not a definitive conclusion.