1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 """Quasi-Newton Broyden-Fletcher-Goldfarb-Shanno (BFGS) nonlinear optimization.
25
26 This file is part of the U{minfx optimisation library<https://gna.org/projects/minfx>}.
27 """
28
29
30 from numpy import dot, float64, identity, outer
31
32
33 from minfx.base_classes import Line_search, Min
34
35
36 -def bfgs(func=None, dfunc=None, args=(), x0=None, min_options=None, func_tol=1e-25, grad_tol=None, maxiter=1e6, a0=1.0, mu=0.0001, eta=0.9, full_output=0, print_flag=0, print_prefix=""):
37 """Quasi-Newton BFGS minimisation."""
38
39 if print_flag:
40 if print_flag >= 2:
41 print(print_prefix)
42 print(print_prefix)
43 print(print_prefix + "Quasi-Newton BFGS minimisation")
44 print(print_prefix + "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")
45 min = Bfgs(func, dfunc, args, x0, min_options, func_tol, grad_tol, maxiter, a0, mu, eta, full_output, print_flag, print_prefix)
46 if min.init_failure:
47 print(print_prefix + "Initialisation of minimisation has failed.")
48 return None
49 results = min.minimise()
50 return results
51
52
53 -class Bfgs(Line_search, Min):
54 - def __init__(self, func, dfunc, args, x0, min_options, func_tol, grad_tol, maxiter, a0, mu, eta, full_output, print_flag, print_prefix):
55 """Class for Quasi-Newton BFGS minimisation specific functions.
56
57 Unless you know what you are doing, you should call the function 'bfgs' rather than using this class.
58 """
59
60
61 self.func = func
62 self.dfunc = dfunc
63 self.args = args
64 self.xk = x0
65 self.func_tol = func_tol
66 self.grad_tol = grad_tol
67 self.maxiter = maxiter
68 self.full_output = full_output
69 self.print_flag = print_flag
70 self.print_prefix = print_prefix
71
72
73 self.a0 = a0
74
75
76 self.mu = mu
77 self.eta = eta
78
79
80 self.init_failure = 0
81
82
83 self.line_search_options(min_options)
84 self.setup_line_search()
85
86
87 self.f_count = 0
88 self.g_count = 0
89 self.h_count = 0
90
91
92 self.warning = None
93
94
95 self.setup_conv_tests()
96
97
98 self.setup_bfgs()
99
100
101 self.update = self.update_bfgs
102
103
105 """The new parameter function.
106
107 Find the search direction, do a line search, and get xk+1 and fk+1.
108 """
109
110
111 self.pk = -dot(self.Hk, self.dfk)
112
113
114 self.line_search()
115
116
117 self.xk_new = self.xk + self.alpha * self.pk
118 self.fk_new, self.f_count = self.func(*(self.xk_new,)+self.args), self.f_count + 1
119 self.dfk_new, self.g_count = self.dfunc(*(self.xk_new,)+self.args), self.g_count + 1
120
121
122 if self.print_flag >= 2:
123 print(self.print_prefix + "pk: " + repr(self.pk))
124 print(self.print_prefix + "alpha: " + repr(self.alpha))
125 print(self.print_prefix + "xk: " + repr(self.xk))
126 print(self.print_prefix + "xk+1: " + repr(self.xk_new))
127 print(self.print_prefix + "fk: " + repr(self.fk))
128 print(self.print_prefix + "fk+1: " + repr(self.fk_new))
129
130
132 """Setup function.
133
134 Create the identity matrix I and calculate the function, gradient and initial BFGS inverse Hessian matrix.
135 """
136
137
138 self.I = identity(len(self.xk), float64)
139
140
141 self.fk, self.f_count = self.func(*(self.xk,)+self.args), self.f_count + 1
142 self.dfk, self.g_count = self.dfunc(*(self.xk,)+self.args), self.g_count + 1
143 self.Hk = self.I * 1.0
144
145
147 """Function to update the function value, gradient vector, and the BFGS matrix."""
148
149
150 sk = self.xk_new - self.xk
151 yk = self.dfk_new - self.dfk
152 dot_yk_sk = dot(yk, sk)
153
154
155 if dot_yk_sk == 0:
156 self.warning = "The BFGS matrix is indefinite. This should not occur."
157 rk = 1e99
158 else:
159 rk = 1.0 / dot_yk_sk
160
161
162 if self.k == 0:
163 self.Hk = dot_yk_sk / dot(yk, yk) * self.I
164
165 self.Hk = dot(self.I - rk*outer(sk, yk), self.Hk)
166 self.Hk = dot(self.Hk, self.I - rk*outer(yk, sk))
167 self.Hk = self.Hk + rk*outer(sk, sk)
168
169
170 self.xk = self.xk_new * 1.0
171 self.fk = self.fk_new
172 self.dfk = self.dfk_new * 1.0
173