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 Rn which
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
Login To Comment