APPLICATION OF DOGLEG METHOD WITH BROYDEN CLASS UPDATING TECHNIQUE FOR SOLVING SOME UNCONSTRAINED MULTIVARIATE NONLINEAR OPTIMIZATION PROBLEMS

  • 0 Review(s)

Product Category: Projects

Product Code: 00007363

No of Pages: 103

No of Chapters: 1-5

File Format: Microsoft Word

Price :

$20

ABSTRACT


In this work, the basic trust-region methods for unconstrained multivariable nonlinear optimization problems were studied using the Dogleg-type trust-region method which employed the Broyden Class updating techniques in generating the approximation matrices to the Hessian of the objective function. Specifically, for the Broyden class updating technique, the values of the scalar parameter  as 0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 and 1 were used for each problem. The values of the initial trust-region radius and the starting point of the decision variables were varied at some points to observe the changes it may have on the solution. The results obtained from the different updating class parameters were compared taking note of the effects of the change in the solutions obtained for each iteration. The results were compared with some known results obtained for the same problems we considered and it shows that our method performed better at some points and poorly at few points. It was discovered that the method employed in this work is sensitive to the nature of initial points used as well as slight changes in the value of the initial trust-region radius. The results show that the value of the scalar parameter Qk = 0.1 performed relatively better than others. Mathlab R2010a was used in executing the program.






TABLE OF CONTENTS

Title Page                                                                                                                                     i

Declaration                                                                                                                                  ii

Certification                                                                                                                               iii

Dedication                                                                                                                                 iv

Acknowledgements                                                                                                                    v

Table of Contents                                                                                                                      vi

List of Tables                                                                                                                          viii

List of Figures                                                                                                                            ix

Abstract                                                                                                                                     xi


CHAPTER 1: INTRODUCTION                                                                                          1

1.1 Background of the Study                                                                                                                 1

1.2 Statement of the Problem                                                                                                                 2

1.3 Aim and Objectives of the Study                                                                                                     3

1.4 Significance of the Study                                                                                                    4

1.5 Justification of the Study                                                                                                     4

1.6 Scope and Limitations of the Study                                                                                     5

1.7 Definition of Terms                                                                                                              5


CHAPTER 2: LITERATURE REVIEW                                                                              7

 

CHAPTER 3: METHODOLOGY                                                                                        13

3.1 Numerical Methods for Multivariate Problems                                                                  13

3.1.1 Line search methods for multivariate problems                                                               13

3.1.2 Trust region methods                                                                                                       14

3.2 Basic Trust-Region Algorithm                                                                                            16

3.3 Expanding the Trust-Region Radius                                                                                  18

3.4 Updating Techniques for                                                                                                18

3.4.1 Broyden-Fletcher-Goldfarb-Shanno (BFGS) updating method                                     19

3.4.2 Davidon-Fletcher-Powell (DFP) updating method                                                         19

3.4.3 Broyden class updating method                                                                                      19

3.5 Solving the Trust-Region Sub-problem                                                                              20

3.5.1 The Dogleg method                                                                                                         20

3.5.2 The new Dogleg method                                                                                                 24

3.6 Demonstrating the Application of our Methods with an Example                                     25

3.7 Numerical Examples                                                                                                           36

3.8 Materials                                                                                                                             37


CHAPTER 4: RESULTS AND DISCUSSION                                                                  38

4.1 Introduction                                                                                                                        38

4.2 Numerical Results of Solved Problems                                                                              39

4.2.1 Problem 1: Rosenbrock function                                                                                     39

4.2.2 Problem 2:                                                                                                                        55

4.2.3 Problem 3: Booth function                                                                                              75

4.2.4 Problem 4: Wood function                                                                                              79

4.3 Analysis of Results                                                                                                             80

4.3.1 Effects of the starting points on the convergence of our method                                   80

4.3.2 Effects of the initial trust-region radius on the convergence of our method                   81

4.3.3 Effects of the Broyden class parameter on the convergence of our method                   82

4.4 Comparison with other Dogleg Methods                                                                           83


CHAPTER 5: CONCLUSIONS AND RECOMMENDATIONS                                     85

5.1 Conclusions                                                                                                                         85

5.2 Recommendations                                                                                                              86

      REFERENCES

      APPENDICES

 

 

 

 

 

 

 

 

LIST OF TABLES

 

3.1: Summary of solutions obtained for the problem            32

4.1: Trust-region Dogleg method with Broyden class update and Qk = 0              39

4.2: Trust-region Dogleg method with Broyden class update and Qk = 0.1                            40

4.3: Trust-region Dogleg method with Broyden class update and Qk = 0.2                            41

4.4: Trust-region Dogleg method with Broyden class update and Qk = 0.3                            43

4.5: Trust-region Dogleg method with Broyden class update and Qk = 0.4                            45

4.6: Trust-region Dogleg method with Broyden class update and Qk = 0.5                            46

4.7: Trust-region Dogleg method with Broyden class update and Qk = 0.6                                        47

4.8: Trust-region Dogleg method with Broyden class update and Qk = 0.7                            48

4.9: Trust-region Dogleg method with Broyden class update and Qk = 0.8                                       49

4.10: Trust-region Dogleg method with Broyden class update and Qk = 0.9                           51

4.11: Trust-region Dogleg method with Broyden class update and Qk = 1                            53

4.12: Summary of results obtained from solving Rosenbrock Function at different Qk           54

4.13: Trust-region Dogleg method with Broyden class update and Qk = 0                              55

4.14: Trust-region Dogleg method with Broyden class update and  Qk = 0.1                         56

4.15: Trust-region Dogleg method with Broyden class update and Qk = 0.2                           57

4.16: Trust-region Dogleg method with Broyden class update and Qk = 0.3                        59

4.17: Trust-region Dogleg method with Broyden class update and  Qk = 0.4                        61

4.18: Trust-region Dogleg method with Broyden class update and Qk = 0.5                         63

4.19: Trust-region Dogleg method with Broyden class update and Qk = 0.6                         65

4.20: Trust-region Dogleg method with Broyden class update and Qk = 0.7                         67

4.21: Trust-region Dogleg method with Broyden class update and Qk = 0.8                         69

4.22: Trust-region Dogleg method with Broyden class update and Qk = 0.9                         71

4.23: Trust-region Dogleg method with Broyden class update and  Qk = 1                           73

4.24: Summary of results obtained from solving Problem 2 at different Qk                              74

4.25: Trust-region Dogleg method with Broyden class update and Qk = 0                             75

4.26: Trust-region Dogleg method with Broyden class update and Qk = 0.1                          75

4.27: Trust-region Dogleg method with Broyden class update and Qk = 0.2                          75

4.28: Trust-region Dogleg method with Broyden class update and Qk = 0.3                          76

4.29: Trust-region Dogleg method with Broyden class update and Qk = 0.4                          76

4.30: Trust-region Dogleg method with Broyden class update and Qk = 0.5                          76

4.31: Trust-region Dogleg method with Broyden class update and Qk = 0.6                          77

4.32: Trust-region Dogleg method with Broyden class update and Qk = 0.7                          77

4.33: Trust-region Dogleg method with Broyden class update and Qk = 0.8                          77

4.34: Trust-region Dogleg method with Broyden class update and Qk = 0.9                          78

4.35: Trust-region Dogleg method with Broyden class update and Qk = 1.0                          78

4.36: Summary of results obtained from solving Problem 3 at different Qk                              79

4.37: Summary of results obtained from solving Problem 4 at different Qk                             79

4.38: Point of convergence for Problem 1 with starting point                                80

4.39: Point of non-convergence for Problem 4 with starting Point                   80

4.40: Point of non-convergence for Problem 1 with starting point                      80 

4.41: Point of convergence for Problem 3 with starting point                              81

4.42: Point of non-convergence for Problem 3 with starting point                     81

4.43: Point of non-convergence for Problem 3 with starting point                   81

4.44: Point of convergence for Problem 1 with starting point                                    82

4.45: Point of non-convergence for Problem 1 with starting point                                82

4.46: Point of non-convergence for Problem 1 with starting point                           82

4.47: Comparison of our results and other known Dogleg methods                                        83

 

 

 

 

 

 

 

 

LIST OF FIGURES

 

3.1: The Cauchy Point Arc                                                                                                       21

3.2: The Dogleg Path                                                                                                                22

 

 

 

 

 

 

CHAPTER 1

INTRODUCTION


1.1    BACKGROUND OF THE STUDY

Most problems in life always appear as nonlinear multivariate problems when expressed mathematically. Sometimes, these problems may have some conditions which its decision variables must satisfy and in this case, we say the problem is constrained, otherwise unconstrained. The process of either minimizing or maximizing such a problem is called optimization or mathematical programming as can be obtained in some texts. Optimization is all about finding the best possible pathway in a set of circumstance. It involves choices informed by the study of the situations and parameters affecting those situations in order to either minimize cost/efforts or maximize benefits. It could be a cost minimization function, profit maximization function, transportation problem or an assignment problem. Avriel (2003), the function to be optimized can be called an objective function, a loss function (minimization), an indirect utility function (minimization), an utility function (maximization), a fitness function (maximization), an energy function, or energy functional.

According to Chong and Zak (2001), optimization is central to any problem involving decision making, whether in engineering or in economics. The challenge facing making decision involves choosing among many options. This choice is influenced by our quest to get the "best" alternative. The degree of goodness of the alternatives is described by a performance index also called the objective function. Hence, theory of Optimization and its methods deal with selecting the best option among many alternatives.

Optimization problems can be linear or nonlinear, convex or concave, constrained or unconstrained, etc. However the case, we are concerned in this work with solving some nonlinear multivariate unconstrained optimization problems.

 

The basic unconstrained optimization problem can be expressed as


The solution to (1.1) can be obtained by analytical procedures or by numerical approach. Practically, most problems are multivariate. Solving a one-dimensional optimization problem analytically is very trivial and corresponds to just equating the gradient of the function to zero and simplifying to obtain the solution. But, for numerical approach, there are many methods which some authors have done some researches on. However, obtaining the solution of multivariate nonlinear problems by numerical procedures is of more interest to us in this work.


1.2 STATEMENT OF THE PROBLEM

Many problems relating to (1.1) have been solved using line search methods, trust-region methods as well as methods that combined elements of both line search and trust-region methods. Most of these methods have reduced the number of iterations and functional value evaluations needed to arrive at the solutions but we still keep researching to see if we can find better approaches. Gertz (2004) who used the classical trust-region method embedded with a line search technique that makes use of the BFGS method to update the approximation matrices achieved a considerable lower of iterations before reaching the solution. Also, Oruh and Bamigbola (2013) proposed a new Dogleg method for solving the trust-region sub-problem which performed better than the traditional trust-region methods though they still used BFGS methods in generating the approximation matrices of the objective functions.

So, this work explores what happened within the Broyden class when used in generating the sequence of approximation matrices of the trust-region sub-problem instead of the BFGS method widely used by other authors.

Thus, given the trust-region sub-problem of the form: 


we seek a solution of the form:


by employing the new Dogleg method developed by Oruh and Bamigbola (2013) but using the Broyden class updating technique in generating the approximation matrix .


1.3 AIM AND OBJECTIVES OF THE STUDY

The aim of this work is to study and analyze the application of Dogleg method with Broyden class updating technique for solving unconstrained multivariate nonlinear optimization problems

Our specific objectives are;

i. To understand the basics of applying the Dogleg method in solving the trust-region sub-problem of our unconstrained multivariate optimization problems.

ii. To understand the basics of applying Broyden Class updating techniques in generating a sequence of positive definite approximation matrix of the objective problems.

iii. To apply the understudied method in (i) and (ii) in solving some nonlinear unconstrained multivariate optimization problems.

iv. To examine the effects of the trust-region radius on the convergence of the method.

v. To examine the effects of the initial value of our decision parameters on the convergence of the method.

vi. To examine the effects of the Broyden class updating parameter on the convergence of the method.

vii. To investigate how the method performed in comparison to other existing methods.

 

1.4 SIGNIFICANCE OF THE STUDY

Trust-region methods have wide applications to many scientific and non-science fields of study. In medicine, it is used in determining biomedical imaging while in behavioural sciences; it is applied in finding the Pareto critical points.

It is also applied in stochastic differential equation in solving complimentary linear equations.

In Statistics, it can also be applied in real-time tracking as an improvement on line search based mean-shift tracker.

It is equally applied in finance in solving the calibration problem associated with error analysis in optimal control problems.

Because of these and many more applications of trust-region methods, this work will offer a more convenient way of solving the trust-region sub-problems associated with real life and applicative problems arising in these other fields of studies.

This work when concluded will suggest the best way of minimizing an unconstrained non-linear multivariate optimization problem with faster convergence and stability. It will also help to suggest an approach that will be more cost effective than most of its counterpart methods.


1.5 JUSTIFICATION OF THE STUDY

Our major motivation in doing this work is to explore what happens within the Broyden class when used in generating sequence of matrices for solving trust-region sub-problems of unconstrained nonlinear optimization problems. This is because many authors have majorly worked on BFGS and DFP methods but Nocedal and Wright (1999) said that the Broyden class when allowed to be negative in a strictly controlled manner performs better than the BFGS and DFP methods in line search computations. So, we decided to investigate the Broyden class in trust-region methods.

The work of Oruh and Bamigbola (2013) equally motivated this research because they developed a new Dogleg method that gave better convergence results than some other known results but they equally used the BFGS method in generating the sequence of approximation matrices for their trust-region sub-problem. Hence, we decided to try to see how we can improve on their work.


1.6 SCOPE AND LIMITATIONS OF THE STUDY

In this work, we only considered some convex functions in Rwhich are twice continuously differentiable. In generating the approximation matrices, we restricted the values of and only considered the new Dogleg method by Oruh and Bamigbola (2013) in solving the trust-region sub-problems. The norm employed in this work is the Euclidean norm only.

However, we were not able to handle functions with order more than 4 in and we did not also consider systems of equations.


1.7 DEFINITION OF TERMS

Minimum point: Given a function  a point is said to be a minimum point of if           

                                     

Maximum point: A point is said to be a maximum point of a function  if


Convex function: A function  defined on a convex set is convex if and only if for all and , we have

              

Constraint function: This is a function which describes the conditions that the decision variables are subjected to. It can be an equation or an inequality.

Linear optimization problem: An optimization problem is said to be linear if the objective function is linear and the decision variables are subject to linear constraints.

Nonlinear optimization problem: An optimization problem is said to be nonlinear if either the objective function or the constraint function is nonlinear.

Constrained optimization problem: An optimization problem is said to be constrained if its decision variables are subject to some constraints or condition. It is given as thus;



Positive definiteness: A matrix is said to be positive definite if given a vector then

 

 

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