Debian Codegraph @

mex/sources/heterogeneity/utils/broyden_solver.f08

raw
1 ! Copyright © 2025-2026 Dynare Team
2 !
3 ! This file is part of Dynare.
4 !
5 ! Dynare is free software: you can redistribute it and/or modify it under the terms of the
6 ! GNU General Public License as published by the Free Software Foundation, either version 3 of
7 ! the License, or (at your option) any later version.
8 !
9 ! Dynare is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
10 ! even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 ! GNU General Public License for more details.
12 !
13 ! You should have received a copy of the GNU General Public License along with Dynare. If not,
14 ! see <https://www.gnu.org/licenses/>.
15 !
16 ! Original author: Normann Rion <[email protected]>
17 !
18 ! Broyden quasi-Newton solver for heterogeneous-agent steady-state calibration
19 !
20 ! Implements the Broyden method following the Python SSJ implementation
21 ! (sequence_jacobian/utilities/solvers.py). Uses LAPACK dgesv for linear solves.
22
23 module broyden_solver
24 use iso_fortran_env, only: real64, int32
25 use ieee_arithmetic, only: ieee_is_finite
26 use blas, only: blint, matvecmul_add, rank_one_update
27 use lapack, only: dgesv
28 use calibration_types, only: broyden_workspace
29 use matlab_mex, only: mexPrintf
30
31 implicit none (type, external)
32
33 private
34 public :: broyden_solve
35
36 ! Default solver parameters
37 real(real64), parameter :: DEFAULT_FD_STEP = 1.0e-5_real64 ! Finite difference step
38 real(real64), parameter :: DEFAULT_BACKTRACK_C = 0.5_real64 ! Backtracking factor
39 integer(int32), parameter :: DEFAULT_MAX_BACKTRACK = 30 ! Max backtracks per iteration
40
41 ! Return codes
42 integer(int32), parameter, public :: BROYDEN_SUCCESS = 0
43 integer(int32), parameter, public :: BROYDEN_MAX_ITER = 1
44 integer(int32), parameter, public :: BROYDEN_SINGULAR_JAC = 2
45 integer(int32), parameter, public :: BROYDEN_MAX_BACKTRACK = 3
46 integer(int32), parameter, public :: BROYDEN_FCN_ERROR = 4
47
48 ! Abstract interface for residual function callback
49 abstract interface
50 subroutine residual_fcn(n, x, fvec, iflag)
51 use iso_fortran_env, only: real64
52 integer, intent(in) :: n
53 real(real64), intent(in) :: x(n)
54 real(real64), intent(out) :: fvec(n)
55 integer, intent(inout) :: iflag
56 end subroutine residual_fcn
57 end interface
58
59 contains
60
61 !---------------------------------------------------------------------------
62 ! Broyden quasi-Newton solver
63 !
64 ! Solves f(x) = 0 using Broyden's method with finite-difference initial
65 ! Jacobian and rank-1 updates.
66 !
67 ! Arguments:
68 ! ws : Pre-allocated Broyden workspace
69 ! x : On entry: initial guess; on exit: solution
70 ! fvec : On exit: residual at solution
71 ! fcn : Residual function f(x) to solve for f(x) = 0
72 ! tol : Convergence tolerance (max|fvec| < tol)
73 ! max_iter : Maximum number of Broyden iterations
74 ! nfev : (out) Number of function evaluations
75 ! fd_step : (optional) Finite difference step size
76 ! backtrack_c : (optional) Backtracking factor
77 ! verbosity : (optional) Verbosity level (2 = verbose, 1 = silent)
78 ! lower_bounds : (optional) Lower bounds for variables
79 ! upper_bounds : (optional) Upper bounds for variables
80 !
81 ! Returns: status code (0 = success)
82 !---------------------------------------------------------------------------
83 function broyden_solve(ws, x, fvec, fcn, tol, max_iter, nfev, fd_step, backtrack_c, verbosity, &
84 lower_bounds, upper_bounds) result(info)
85 type(broyden_workspace), intent(inout) :: ws
86 real(real64), intent(inout) :: x(:)
87 real(real64), intent(out) :: fvec(:)
88 procedure(residual_fcn) :: fcn
89 real(real64), intent(in) :: tol
90 integer(int32), intent(in) :: max_iter
91 integer(int32), intent(out) :: nfev
92 real(real64), intent(in), optional :: fd_step, backtrack_c
93 integer(int32), intent(in), optional :: verbosity
94 real(real64), intent(in), optional :: lower_bounds(:), upper_bounds(:)
95 integer(int32) :: info
96
97 ! Local variables
98 integer(int32) :: n, iter, bcount, iflag
99 real(real64) :: h, bc, max_residual
100 integer(blint) :: n_bl, nrhs, lda, ldb, lapack_info
101 real(real64), allocatable :: x_new(:)
102 logical :: has_bounds
103
104 n = ws%n_vars
105 h = DEFAULT_FD_STEP
106 bc = DEFAULT_BACKTRACK_C
107 if (present(fd_step)) h = fd_step
108 if (present(backtrack_c)) bc = backtrack_c
109
110 ! Check if bounds are provided
111 has_bounds = present(lower_bounds) .and. present(upper_bounds)
112 allocate(x_new(n))
113
114 nfev = 0
115 info = BROYDEN_SUCCESS
116
117 ! Step 1: Evaluate initial residual f(x0)
118 iflag = 0
119 call fcn(n, x, fvec, iflag)
120 nfev = nfev + 1
121
122 if (iflag < 0) then
123 info = BROYDEN_FCN_ERROR
124 return
125 end if
126
127 ! Main iteration loop
128 do iter = 1, max_iter
129 ! Check convergence
130 max_residual = maxval(abs(fvec))
131 if (max_residual < tol) then
132 info = BROYDEN_SUCCESS
133 return
134 end if
135
136 ! Step 2: Compute Jacobian (first iteration only)
137 if (iter == 1) then
138 if (present(verbosity)) then
139 if (verbosity == 2) &
140 call mexPrintf(' Computing initial Jacobian via finite differences...'//NEW_LINE('A'))
141 end if
142 call compute_fd_jacobian(ws, x, fvec, fcn, h, nfev, iflag, verbosity)
143 if (iflag < 0) then
144 info = BROYDEN_FCN_ERROR
145 return
146 end if
147 end if
148
149 ! Step 3: Solve J * dx = -fvec
150 ! Copy J to J_copy (dgesv overwrites it)
151 ws%J_copy = ws%J
152 ! Set dx = -fvec (right-hand side)
153 ws%dx = -fvec
154
155 ! Call LAPACK dgesv
156 n_bl = int(n, blint)
157 nrhs = 1_blint
158 lda = n_bl
159 ldb = n_bl
160 call dgesv(n_bl, nrhs, ws%J_copy, lda, ws%ipiv, ws%dx, ldb, lapack_info)
161
162 if (lapack_info /= 0) then
163 info = BROYDEN_SINGULAR_JAC
164 return
165 end if
166
167 ! Step 4: Backtracking line search
168 do bcount = 1, DEFAULT_MAX_BACKTRACK
169 ! Compute new point: x + dx, then clamp to bounds if present
170 x_new = x + ws%dx
171 if (has_bounds) call clamp_to_bounds(x_new, lower_bounds, upper_bounds, n)
172
173 ! Try new point
174 iflag = 0
175 call fcn(n, x_new, ws%fvec_new, iflag)
176 nfev = nfev + 1
177
178 if (iflag < 0) then
179 ! Function evaluation failed, backtrack
180 ws%dx = ws%dx * bc
181 else
182 ! Success: update Jacobian with Broyden rank-1 update
183 ! df = fvec_new - fvec
184 ws%df = ws%fvec_new - fvec
185
186 ! Compute actual dx (may differ from ws%dx due to clamping)
187 ws%dx = x_new - x
188
189 ! Move to new point (must be done BEFORE broyden_update
190 ! because broyden_update overwrites ws%fvec_new as workspace)
191 fvec = ws%fvec_new
192 x = x_new
193
194 ! Broyden update: J = J + outer((df - J*dx) / ||dx||^2, dx)
195 call broyden_update(ws)
196
197 exit
198 end if
199 end do
200
201 if (bcount > DEFAULT_MAX_BACKTRACK) then
202 info = BROYDEN_MAX_BACKTRACK
203 return
204 end if
205 end do
206
207 ! Maximum iterations exceeded
208 info = BROYDEN_MAX_ITER
209
210 end function broyden_solve
211
212 !---------------------------------------------------------------------------
213 ! Clamp variables to bounds
214 !
215 ! For each variable, if the bound is finite (not -Inf or +Inf), clamp.
216 !---------------------------------------------------------------------------
217 subroutine clamp_to_bounds(x, lb, ub, n)
218 real(real64), intent(inout) :: x(:)
219 real(real64), intent(in) :: lb(:), ub(:)
220 integer(int32), intent(in) :: n
221
222 integer :: i
223
224 do i = 1, n
225 if (ieee_is_finite(lb(i))) x(i) = max(x(i), lb(i))
226 if (ieee_is_finite(ub(i))) x(i) = min(x(i), ub(i))
227 end do
228 end subroutine clamp_to_bounds
229
230 !---------------------------------------------------------------------------
231 ! Compute initial Jacobian via forward finite differences
232 !
233 ! J(:,i) = (f(x + h*e_i) - f(x)) / h
234 !---------------------------------------------------------------------------
235 subroutine compute_fd_jacobian(ws, x, fvec, fcn, h, nfev, iflag, verbosity)
236 type(broyden_workspace), intent(inout) :: ws
237 real(real64), intent(in) :: x(:), fvec(:)
238 procedure(residual_fcn) :: fcn
239 real(real64), intent(in) :: h
240 integer(int32), intent(inout) :: nfev
241 integer, intent(out) :: iflag
242 integer(int32), intent(in), optional :: verbosity
243
244 integer(int32) :: i, n
245 real(real64) :: x_orig
246 character(len=256) :: msg
247
248 n = ws%n_vars
249 iflag = 0
250
251 do i = 1, n
252 ! Perturb x(i)
253 x_orig = x(i)
254 ws%fvec_new(1:n) = x ! Use fvec_new as temporary x_pert
255 ws%fvec_new(i) = x_orig + h
256
257 ! Evaluate f(x + h*e_i)
258 call fcn(n, ws%fvec_new, ws%df, iflag)
259 nfev = nfev + 1
260
261 if (iflag < 0) return
262
263 ! Forward difference: J(:,i) = (f_pert - f) / h
264 ws%J(:, i) = (ws%df - fvec) / h
265
266 ! Debug output
267 if (present(verbosity)) then
268 if (verbosity == 2) then
269 write(msg, '(A,I2,A,ES12.5,A,ES12.5,A,ES12.5,A,ES12.5)') &
270 ' FD[', i, ']: x=', x_orig, ', h=', h, &
271 ', f=', fvec(1), ', f_pert=', ws%df(1)
272 call mexPrintf(trim(msg)//NEW_LINE('A'))
273 write(msg, '(A,ES12.5)') ' J=', ws%J(1, i)
274 call mexPrintf(trim(msg)//NEW_LINE('A'))
275 end if
276 end if
277 end do
278
279 end subroutine compute_fd_jacobian
280
281 !---------------------------------------------------------------------------
282 ! Broyden rank-1 update
283 !
284 ! J = J + outer((df - J*dx) / ||dx||^2, dx)
285 !
286 ! where df = fvec_new - fvec (already computed in ws%df)
287 ! dx = Newton step (in ws%dx)
288 !---------------------------------------------------------------------------
289 subroutine broyden_update(ws)
290 type(broyden_workspace), intent(inout) :: ws
291
292 integer(int32) :: n
293 real(real64) :: dx_norm_sq, scale
294
295 n = ws%n_vars
296
297 ! Compute ||dx||^2
298 dx_norm_sq = dot_product(ws%dx, ws%dx)
299
300 ! Skip update if dx is too small to avoid division by zero
301 if (dx_norm_sq < 1.0e-30_real64) return
302
303 ! Compute correction = J * dx using BLAS (store in fvec_new as temp)
304 ws%fvec_new = 0.0_real64
305 call matvecmul_add('N', 1.0_real64, ws%J, ws%dx, 0.0_real64, ws%fvec_new)
306
307 ! fvec_new = (df - J*dx) / ||dx||^2
308 scale = 1.0_real64 / dx_norm_sq
309 ws%fvec_new = (ws%df - ws%fvec_new) * scale
310
311 ! Rank-1 update: J = J + outer(fvec_new, dx) using BLAS dger
312 ! dger: A = alpha * x * y^T + A
313 call rank_one_update(n, n, 1.0_real64, ws%fvec_new, ws%dx, ws%J)
314
315 end subroutine broyden_update
316
317 end module broyden_solver