EXPERIMENTAL STUDY OF THE BROYDEN CLASS UPDATING METHOD FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS

  • 0 Review(s)

Product Category: Projects

Product Code: 00007352

No of Pages: 107

No of Chapters: 1-5

File Format: Microsoft Word

Price :

$20

ABSTRACT


 Unconstrained optimization is an optimization process where no restriction is placed on the range of the unknown variable. Several methods can be adopted in the solution of unconstrained optimization problems. In this work, emphasis is on the Broyden class updating methods of Davidon-Fletcher-Powel (DFP) algorithm, Broyden Fletcher Goldfarb Shannon(BFGS) algorithm and their linear combinations.  Linear constants ranging from 0.1 to 0.9 are simulated in MATLAB and the numerical solutions are extensively presented for the following commonly tested functions: Freudenstein and Roth function, Beales function and Woods function. The result of the simulations in MATLAB environment and the graphical analysis in Microsoft excel reveal that BFGS formula gives the best performance as it gives the same convergence rate and better average time than DFP in all the test functions. The average time and the number of iterations of the test functions increase as the linear constant increases for the Linear Combination (LC) algorithm. It is recommended that BFGS algorithm should be adopted when finding solution to unconstrained optimization problems.





TABLE OF CONTENTS

                                                                                                                  

Title page                                                                                                                              

Cover page                                                                                                   i                                                                                    

Declaration                                                                                          ii

Dedication                                                                                           iii

Certification                                                                                        iv

Acknowledgements                                                                              v

Table of contents                                                                                 vi

List of tables                                                                                       vii

List of figures                                                                                                             viii      

List of abbreviations, symbols and terms                                                                   ix

Abstract                                                                                                                      x

 

CHAPTER 1: INTRODUCTION

1.1       Background                                                                                                                1

1.2       Statement of the Problem                                             4

1.3       Aim and Objectives                                                     6

1.4       Scope of the Study                                                                6

1.5       Structure of Thesis                                                                6

1.6       Definition of Term                                                                          7


CHAPTER 2: LITERATURE REVIEW AND THEORETICAL FRAMEWORK

2.1       Introduction                                                                                                                9

2.2       Literature Review                                                                                                       9

2.3       Test functions                                                                                                             14

2.3.1    Freudenstein and Roth function                                                                                 14

2.3.2    Beales function                                                                                                           14

2.3.3    Woods function                                                                                                          14

 

CHAPTER 3: METHODOLOGY

3.1       Introduction                                                                                                                15

3.2       Derivation of Broyden Class Updating Method for Unconstrained

            Optimization Problems.                                                                                              15

3.2.1    Construction of the Inverse                                                                                        15

3.2.2    Rank One Correction.                                                                                                 17

3.3       Davidon Fletcher Powell Method                                                                              19

3.3.1    DFP algorithm (Nocedal and Yuan (1998))                                                               20

3.4       Broyden Fletcher Goldfarb Shannon                                                                         21

3.4.1    BFGS algorithm (Adewale and Oruh, 2013)                                                             22

3.5       Linear Combination of DFP and BFGS                                                                     23

3.5.1    Linear combination of DFP and BFGS algorithm (Wen Huang et al., 2014)            24

3.6       Material and Method                                                                                                  25

 

CHAPTER 4: ANALYSIS AND DISCUSSIONS OF RESULTS

4.1       Analysis                                                                                                                      26

4.1.1    Analytical procedure                                                                                                   26

4.1.2    Numerical procedure                                                                                                   51

4.2       Matlab Simulation result                                                                                             51

4.2.1    Freudenstein and Roth function                                                                                 52

4.2.2    Beales function                                                                                                           58

4.2.3    Woods function                                                                                                          66

4.3      Graphical Analysis of Results                                                                                      75

4.4       Discussions of Results                                                                                                76

 

CHAPTER 5: CONCLUSION AND RECOMMENDATION

5.1       Conclusion                                                                                                                  78

5.2      Recommendation                                                                                                         78

References                                                                                                                  79

Appendices                                                                                                                 82

 

 

 

 

 

LIST OF TABLES

 

4.1a             Result generated using DFP (Freudenstein and Roth)                      53

4.1b             Result generated using BFGS (Freudenstein and Roth)                    53

4.1ci            Result generated using LC at 0.1(Freudenstein and Roth)                         54

4.1cii            Result generated using LC at 0.2(Freudenstein and Roth)                         54

4.1ciii           Result generated using LC at 0.3(Freudenstein and Roth)                         55

4.1civ           Result generated using LC at 0.4(Freudenstein and Roth)                         55

4.1cv            Result generated using LC at 0.5(Freudenstein and Roth)                         56

4.1cvi           Result generated using LC at 0.6(Freudenstein and Roth)                         56

4.1cvii          Result generated using LC at 0.7(Freudenstein and Roth)                         57

4.1cviii         Result generated using LC at 0.8(Freudenstein and Roth)                         57

4.1cix           Result generated using LC at 0.9(Freudenstein and Roth)                         58

4.2a                 Result generated using DFP                                                                           59

 4.2b                Result generated using BFGS                                                                        59

4.2ci                Result generated using linear combination for linear constant 0.1                 60

4.2cii               Result generated using linear combination for linear constant 0.2                 60

4.2ciii              Result generated using linear combination for linear constant 0.3                 61

4.2civ              Result generated using linear combination for linear constant 0.4                 61

4.2cv               Result generated using linear combination for linear constant 0.5                 62

4.2cvi              Result generated using linear combination for linear constant 0.6                 63

4.2cvii             Result generated using linear combination for linear constant 0.7                 63

4.2cviii Result generated using linear combination for linear constant 0.8                 64

4.2cix              Result generated using linear combination for linear constant 0.9                 65

4.3a                 Result generated using DFP                                                                           66

4.3b                 Result generated using BFGS                                                                        67

4.3ci                Result generated using linear combination for linear constant 0.1                 67

4.3cii               Result generated using linear combination for linear constant 0.2                 68

4.3ciii              Result generated using linear combination for linear constant 0.3                 68

4.3civ              Result generated using linear combination for linear constant 0.4                 69

4.3cv               Result generated using linear combination for linear constant 0.5                 70

4.3cvi             Result generated using linear combination for linear constant 0.6                 70

4.3cvii             Result generated using linear combination for linear constant 0.7                 71

4.3cviii Result generated using linear combination for linear constant 0.8                 72

4.3cxi              Result generated using linear combination for linear constant 0.9                 72

4.4                   Average time for the test functions                                                                73

4.5                   Number of iterations for the test functions                                                    74

 

 

 

 

 

 

 

LIST OF FIGURES

 

4.1a             Excel Graph of  Average Time of Test Functions                                      75

4.1b             Matlab Plot of Average Time of Text Functions                               75

4. 2a            Excel Graph of Number of Iterations of Test Functions                    76

4.2b             Matlab Plot of Average Time of Text Functions                               76

 

 

 

 


 

LIST OF ABBREVIATION, SYMBOLS AND TERMS

Average time                                       Time it took the program to get the result

BFGS                                                  Broyden Fletcher Goldfarb Shannon

DFP                                                     Davidon Fletcher Powell

LBFGS                                               Limited memory Broyden Fletcher Goldfarb Shannon

LC                                                       Linear combination

NM                                                      Newton’s method

FN                                                       Fixed Newton

CN                                                      Classical Newton

CB                                                       Classical Broyden

QP                                                       Quadratic Programming

SQP                                                     Sequential Quadratic Programming

WORHP                                             We Optimize Really Huge Problems

ODE                                                    Ordinary Differential Equation

CPU                                                    Central Processing Unit

CUTEr                                                This is an open source testing environment for optimization and linear algebra solvers

                                                          Step length

                                                          Norm of the gradient

                                                         Hessian matrix

                                                       A symmetric and positive definite Hessian matrix

                                           Inverse Hessian approximation                      

                                                         A function of each iteration

                                                    Function of x

                                    Gradient of function

                                                          Number of iteration

 and                                             Variables

 

 

 

 

 

 



 

 

CHAPTER 1

INTRODUCTION

1.1 BACKGROUND

Unconstrained optimization problems can be solved using various methods. Amongst the methods of solution are steepest (gradient) descent method, Newton method and quasi-Newton method. Gradient descent method is a way to find a local minimum of a function. The way it works is we start with an initial guess of the solution and we take the gradient of the function at that point. We step the solution in the negative direction of the gradient and we repeat the process. The algorithm will eventually converge where the gradient is zero (which corresponds to a local minimum). Its brother, the gradient ascent, finds the local maximum nearer the current solution by stepping it towards the positive direction of the gradient. They are both first-order algorithms because they take only the first derivative of the function. In optimization, Newton's method is applied to the derivative of a twice differentiable function  f  to find the roots of the derivative (solutions to f ′(x)=0), also known as the critical points of f. This method stems from the Newton's method for solving systems of nonlinear equations. Newton's method uses curvature information to take a more direct route, that is, can identify better search directions than can be obtained via the gradient method. Quasi-Newton methods are arguably the most effective methods for finding a minimizer of a smooth nonlinear function  when second derivatives are either unavailable or too expensive to calculate. Quasi-Newton methods build up second-derivative information by estimating the curvature along a sequence of search directions. Each curvature estimate is installed in an approximate Hessian by applying a rank-one or rank-two update. One of the most successful updates is the Broyden Fletcher Goldfarb Shanno (BFGS) formula, which is a member of the wider Broyden class of rank-two updates. Despite the success of these methods on a wide range of problems, it is well known that conventional quasi-Newton methods can require a disproportionately large number of iterations and function evaluations on some problems. This inefficiency may be caused by a poor choice of initial approximate Hessian or may result from the search directions being poorly defined when the Hessian is ill-conditioned (Philip and Michael, 2001).

In the quasi-Newton context, the availability of an explicit basis for the gradient subspace makes it possible to represent the approximate curvature in terms of a reduced approximate Hessian matrix with order at most k + 1. Quasi-Newton algorithms that explicitly calculate a reduced Hessian have been proposed by Fenelon (1981) and Nazareth (1986), who also considered modified Newton methods in the same context. Siegel (1992) proposed methods that work with a reduced inverse approximate Hessian. In practical terms, the reduced-Hessian formulation can require significantly less work per iteration when k is small relative to n. This property can be exploited by forcing iterates to linger on a manifold while the objective function is minimized to greater accuracy. While iterates linger, the search direction is calculated from a system that is generally smaller than the reduced Hessian. In many practical situations convergence occurs before the dimension of the lingering subspace reaches n, resulting in substantial savings in computing time.

More recently, Siegel (1994) proposed the conjugate-direction scaling algorithm, which is a quasi-Newton method based on a conjugate-direction factorization of the inverse approximate Hessian. Although no explicit reduced Hessian is updated, the method maintains a basis for the expanding subspaces and allows iterates to linger on a manifold. The method also has the benefit of finite termination on a quadratic function (Leonard, 1995). More importantly, Siegel’s method includes a feature that can considerably enhance the benefits of lingering. Siegel notes that the search direction is the sum of two vectors: one with the scale of the estimated derivatives and the other with the scale of the initial approximate Hessian. Siegel suggests rescaling the second vector using newly computed approximate curvature. Algorithms that combine lingering and rescaling have the potential for giving significant improvements over conventional quasi-Newton methods. Lingering forces iterates to remain on a manifold until the curvature has been sufficiently established; rescaling ensures that the initial curvature in the unexplored manifold is commensurate with curvature already found.

Several algorithms based on maintaining the triangular factors of an explicit reduced Hessian have been proposed. How these factors can be used to force iterates to linger while curvature information continues to be accumulated along directions away from the manifold has been demonstrated. With the Broyden Fletcher Goldfarb Shanno (BFGS) method, it is shown that while lingering takes place, the new curvature is restricted to an upper-trapezoidal portion of the factor of the reduced Hessian and the remaining portion retains the diagonal structure of the initial approximate Hessian. It follows that conjugate-direction scaling is equivalent to simply reinitializing the diagonal part of the reduced Hessian with freshly computed curvature information. Despite the similarities between reduced Hessian re-initialization and conjugate direction scaling, it must be emphasized that these methods are not the same, in the sense that they involve very different storage and computational overheads. Moreover, the reduced-Hessian factorization has both practical and theoretical advantages over Siegel’s conjugate-direction factorization. On the practical side, the early search directions can be calculated with significantly less work. This can result in a significantly faster minimization when the dimension of the manifold grows relatively slowly, as it does on many problems. On the theoretical side, the simple structure exhibited by the reduced-Hessian factor allows the benefits of re initialization to be extended to the large-scale case (Gill and Leonard, 1997).

A reduced-Hessian method allows expansion of the manifold on which curvature information is known. Thus, when implementing software, it is necessary either to allocate new memory dynamically as the reduced Hessian grows or to reserve sufficient storage space in advance. In practice, however, the order of the reduced Hessian often remains much less than n, i.e., the problem is solved without needing room for an n × n matrix. Notwithstanding this benefit, on very large problems it may be necessary to explicitly limit the amount of storage used, by placing a limit on the order of the reduced Hessian. Such limited-memory reduced-Hessian methods discard old curvature information whenever the addition of new information causes a predefined storage limit to be exceeded. Methods of this type have been considered by Fenelon (1981) and Siegel (1994).

In recent years, a class of iterative processes for solving non-linear equation or minimization problem in  has been considered frequently and applied to many practical problems. Its members are variously called quasi-Newton methods, variable metric methods, modification methods, or update methods. Most of the studies about these methods were framed in a minimization setting. In this setting, Powell (1970 and 1978) proved a global convergence theorem for the best known member of this class, the Davidon Fletcher Powell (DFP) method. Only recently, Dennis and More (1977), in continuation of earlier work by Dennis (1970 and 1971) developed highly interesting local convergence results for a class of update methods without assuming the minimization setting or requiring specific relaxation factors.

In numerical analysis, Broyden’s method is a quasi-Newton method for finding roots in k variables. Newton’s method for solving  uses the Jacobian matrix, J, at every iteration. However, computing this Jacobian is a difficult and expensive operation. The idea behind Broyden’s method is to compute the whole Jacobian only at the first iteration, and to do a rank-one update at the other iterations.


1.2 STATEMENT OF THE PROBLEM

Many methods suggested different ways for solving unconstrained optimization problems, among these are steepest descent method, Newton method and quasi Newton method. Even among the quasi Newton, there are varieties of algorithms such as Davidon Fletcher Powell’s method, Broyden Fletcher Goldfarb Shannon’s method, etc.

To improve the existing limited memory Broyden Fletcher Goldfarb Shannon (BFGS) method, the Limited memory Broyden Fletcher Goldfarb Shannon (LBFGS) method has been developed. The limited memory Broyden Fletcher Goldfarb Shannon (LBFGS) method has been specially created for solving nonlinear optimization problems by an SQP method. In the limited memory Broyden Fletcher Goldfarb Shannon (LBFGS), the compact representation of the limited memory in Broyden Fletcher Goldfarb Shannon (BFGS) formula for the Hessian matrix is replaced in quadratic programming (QP) sub problems arising from the sequential quadratic programming (SQP) method. Introducing a fix small number of auxiliary variables and imposing an additional constraint, the QP problem is transformed. Then, the obtained QP problem is solved using an interior point method. In this way, the computational cost is less than the one needed by the limited memory BFGS. The LBFGS method has been implemented successfully in “We Optimize Really Huge Problems” (WORHP). Its performance has been tested on the optimal control problem arising from a robotic application, on multi-phase optimal control problems arising from an aerospace application, and on two sets of optimization problems arising from various applications. The results were compared with other Hessian approximation methods available in WORHP. The test results have shown that LBFGS is a robust and efficient method. It was able to solve highly nonlinear optimal control problems and difficult multi-phase optimal control problems with less computational time and less major iterations than the other methods. The LBFGS method solved the same number or in some cases even more problems from the CUTEr test set than the exact Hessian method (Sonja, 2014). It is important to compare the performance of the quasi Newton’s algorithms and also determine the effect of their linear combination at various points.

This thesis intends to analyze and compare some algorithms for solving unconstrained optimization problems, and determine the best method for solving unconstrained minimization problems with the best result.


1.3 AIM AND OBJECTIVES

The main purpose of this study is to analyze and compare some algorithms for solving unconstrained optimization problems, and determine the best method for solving unconstrained minimization problems with the best result among them.

The following objectives are stated to achieve the aim of the study.

1.      To review various methods of solving unconstrained optimization problems.

2.      To compare the algorithms for solving unconstrained optimization problems using the Broyden class updating methods.

3.      To obtain the linear combination of the Broyden class updating methods for all the tested functions.

4.      To determine the method with the best performance for each tested function.


1.4 SCOPE OF THE STUDY

This work is limited to unconstrained minimization problem with focus on the Broyden class updating methods (DFP and BFGS). It is applied to the following commonly tested functions:

      ·         Freudenstein and Roth function

      ·         Beales function

      ·         Woods function


1.5 STRUCTURE OF THESIS

The thesis is structured as follows: Chapter two contains the reviewed literatures and the basic mathematical theory for nonlinear optimization problems is formulated. Then the necessary and sufficient conditions for the existence of the optimal solution are discussed. Afterwards some numerical methods for finding a solution of nonlinear optimization problems are presented. In Chapter three, the systematic methods of achieving the aim and objectives of the research are described. The algorithms for Davidon Fletcher Powell (DFP), Broyden Fletcher Goldfarb Shanno (BFGS) and the linear combination of Davidon Fletcher Powell (DFP) and Broyden Fletcher Goldfarb Shanno (BFGS) for the minimization problem are presented. Here, the focus is the Broyden class updating methods (DFP and BFGS).

In Chapter 4, Davidon Fletcher Powell (DFP), Broyden Fletcher Goldfarb Shanno (BFGS) and the linear combination of Davidon Fletcher Powell (DFP) and Broyden Fletcher Goldfarb Shanno (BFGS) are simulated in MATLAB; graphical analysis is done in Microsoft excel and discussions of results are made. The numerical solutions are extensively presented in MATLAB for the following commonly tested functions:

·         Freudenstein and Roth function

·         Beales function

·         Woods function

In Chapter 5 the final conclusions are drawn and recommendation made.

 

1.6 DEFINITION OF TERM

Broyden class of quasi Newton methods

A Broyden class is family of quasi Newton methods that depend on a real parameter  Its Hessian approximation update formula is

where stands for the update obtained by the Broyden Fletcher Goldfarb Shanno (BFGS) method and for the update of the Davidon Fletcher Powell (DFP) method. In this case, all members of the Broyden class satisfy the well known secant equation, central to many quasi Newton method.

Both the DFP and BFGS methods are just special cases of Broyden family.  = 0 – DFP method and 1- BFGS method.

Linear combination

In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of x and y would be any expression of the form ax + by, where a and b are constants) (Strang, 2006). The concept of linear combinations is central to linear algebra and related fields of mathematics. In optimization, you compute the search direction by a linear combination of the current gradient and the previous search direction.

 

 

Click “DOWNLOAD NOW” below to get the complete Projects

FOR QUICK HELP CHAT WITH US NOW!

+(234) 0814 780 1594

Buyers has the right to create dispute within seven (7) days of purchase for 100% refund request when you experience issue with the file received. 

Dispute can only be created when you receive a corrupt file, a wrong file or irregularities in the table of contents and content of the file you received. 

ProjectShelve.com shall either provide the appropriate file within 48hrs or send refund excluding your bank transaction charges. Term and Conditions are applied.

Buyers are expected to confirm that the material you are paying for is available on our website ProjectShelve.com and you have selected the right material, you have also gone through the preliminary pages and it interests you before payment. DO NOT MAKE BANK PAYMENT IF YOUR TOPIC IS NOT ON THE WEBSITE.

In case of payment for a material not available on ProjectShelve.com, the management of ProjectShelve.com has the right to keep your money until you send a topic that is available on our website within 48 hours.

You cannot change topic after receiving material of the topic you ordered and paid for.

Ratings & Reviews

0.0

No Review Found.


To Review


To Comment