ABSTRACT
In this project, different gradient type methods which can be applied to
solve an unconstrained optimization problem have been investigated. This
project focuses on Barzilai and Borwein Gradient method, Monotone Gra-
dient method via weak secant equation and Monotone Gradient method via
Quasi-Cauchy Relation. Iterative scheme for each method was studied. To
apply each of these methods, the functions was assumed to be convex and
twice continuous differentiable. In yields of the application, a few stan-
dard unconstrained functions have been chosen for testing purposes. The
results obtained show the number of iterations used for getting an optimal
point. The result were used for analyzing the efficiency of the methods
studied. Two comparisons had been made in this project. First is the
Barzilai and Borwein Gradient method with Monotone Gradient method
via weak secant equation and the second is Barzilai and Borwein Gradi-
ent method with Monotone Gradient method via Quasi-Cauchy Relation.
These comparisons show that the Monotone Gradient type methods per-
form better as compared to the Barzilai and Borwein Gradient method.
The number of iterations clearly was not affected by the dimension. Fi-
nally, verification for the two proposed algorithms was done to show the
flow of the algorithms.
TABLE OF CONTENTS
TITLE i
DECLARATION OF ORIGINALITY ii
ACKNOWLEDGEMENTS vii
ABSTRACT viii
LIST OF FIGURES xi
LIST OF TABLES xii
CHAPTER 1 Introduction 1
1-1 Objective 2
1-2 Scope
2
1-3 Problem Statement 2
1-4 Research Methodology 2
1-5 Methodology and Planning 3
CHAPTER 2 Literature Review 6
CHAPTER 3 Gradient Type Methods 9
3-1 Terminology and Definition 9
3-2 Optimality Condition for Unconstrained Optimization 12
3-3 Overview of Gradient-type Methods 13
3-4 Steepest Descent Method 14
3-4-1 Convergence of the Steepest Descent Method 15
3-5 Newton Method 16
3-5-1 Convergence of the Newton Method 17
3-6 Quasi Newton Method 18
3-7 Barzilai and Borwein (BB) Gradient Method 18
3-7-1 Convergence of the Barzilai and Borwein (BB) Gra-
dient Method 19
3-8 Monotone Gradient Method via Weak Secant Equation 20
3-8-1 Convergence of the Monotone Gradient Method via
Weak Secant Equation 21
3-9 Monotone Gradient method via Quasi-Cauchy Relation 22
3-9-1 Convergence of the Monotone Gradient method via
Quasi-Cauchy Relation 24
CHAPTER 4 Results and Discussions 25
4-1 Comparison of Gradient Type Methods 25
4-1-1 Barzilai and Borwein Gradient Method and Mono-
tone Gradient Method via Weak Secant Equation 25
4-1-2 Barzilai and Borwein Gradient Method and Mono-
tone Gradient method via Quasi-Cauchy Relation 28
4-2 Verification of Algorithm 31
4-2-1 Barzilai and Browein method 31
4-2-2 Monotone Gradient Method via Weak Secant Equa-
tion 32
CHAPTER 5 Conclusion 34
APPENDIX A Test Function
LIST OF FIGURES
11 Milestone for Project 1 4
12 Task Description for Project 1 5
13 Milestone for Project 2 5
14 Task Description for Project 2 5
31 Local Minimizer and Global Minimizer 9
32 Concave Function and Convex Function 10
33 First Order Characteristic of Convex Function 11
34 Zigzagging in Steepest Descend Method 16
LIST OF TABLES
41 Numerical result of BB Method and MonoGrad method 25
42 Numerical result of BB Method and MonoGrad method (continue) 26
43 Numerical result of BB Method and MonoGrad method (continue) 27
44 Numerical result of BB Method and MonoCauchy method 28
45 Numerical result of BB Method and MonoCauchy method (continue) 29
46 Numerical result of BB Method and MonoCauchy method (continue) 30
47 Algorithm Verification for BB method 32
48 Algorithm Verification for Monotone Gradient method via Weak Se-
cant Equation 33
