! Copyright © 2025-2026 Dynare Team ! ! This file is part of Dynare. ! ! Dynare is free software: you can redistribute it and/or modify it under the terms of the ! GNU General Public License as published by the Free Software Foundation, either version 3 of ! the License, or (at your option) any later version. ! ! Dynare is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without ! even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ! GNU General Public License for more details. ! ! You should have received a copy of the GNU General Public License along with Dynare. If not, ! see . ! ! Original author: Normann Rion ! ! Broyden quasi-Newton solver for heterogeneous-agent steady-state calibration ! ! Implements the Broyden method following the Python SSJ implementation ! (sequence_jacobian/utilities/solvers.py). Uses LAPACK dgesv for linear solves. module broyden_solver use iso_fortran_env, only: real64, int32 use ieee_arithmetic, only: ieee_is_finite use blas, only: blint, matvecmul_add, rank_one_update use lapack, only: dgesv use calibration_types, only: broyden_workspace use matlab_mex, only: mexPrintf implicit none (type, external) private public :: broyden_solve ! Default solver parameters real(real64), parameter :: DEFAULT_FD_STEP = 1.0e-5_real64 ! Finite difference step real(real64), parameter :: DEFAULT_BACKTRACK_C = 0.5_real64 ! Backtracking factor integer(int32), parameter :: DEFAULT_MAX_BACKTRACK = 30 ! Max backtracks per iteration ! Return codes integer(int32), parameter, public :: BROYDEN_SUCCESS = 0 integer(int32), parameter, public :: BROYDEN_MAX_ITER = 1 integer(int32), parameter, public :: BROYDEN_SINGULAR_JAC = 2 integer(int32), parameter, public :: BROYDEN_MAX_BACKTRACK = 3 integer(int32), parameter, public :: BROYDEN_FCN_ERROR = 4 ! Abstract interface for residual function callback abstract interface subroutine residual_fcn(n, x, fvec, iflag) use iso_fortran_env, only: real64 integer, intent(in) :: n real(real64), intent(in) :: x(n) real(real64), intent(out) :: fvec(n) integer, intent(inout) :: iflag end subroutine residual_fcn end interface contains !--------------------------------------------------------------------------- ! Broyden quasi-Newton solver ! ! Solves f(x) = 0 using Broyden's method with finite-difference initial ! Jacobian and rank-1 updates. ! ! Arguments: ! ws : Pre-allocated Broyden workspace ! x : On entry: initial guess; on exit: solution ! fvec : On exit: residual at solution ! fcn : Residual function f(x) to solve for f(x) = 0 ! tol : Convergence tolerance (max|fvec| < tol) ! max_iter : Maximum number of Broyden iterations ! nfev : (out) Number of function evaluations ! fd_step : (optional) Finite difference step size ! backtrack_c : (optional) Backtracking factor ! verbosity : (optional) Verbosity level (2 = verbose, 1 = silent) ! lower_bounds : (optional) Lower bounds for variables ! upper_bounds : (optional) Upper bounds for variables ! ! Returns: status code (0 = success) !--------------------------------------------------------------------------- function broyden_solve(ws, x, fvec, fcn, tol, max_iter, nfev, fd_step, backtrack_c, verbosity, & lower_bounds, upper_bounds) result(info) type(broyden_workspace), intent(inout) :: ws real(real64), intent(inout) :: x(:) real(real64), intent(out) :: fvec(:) procedure(residual_fcn) :: fcn real(real64), intent(in) :: tol integer(int32), intent(in) :: max_iter integer(int32), intent(out) :: nfev real(real64), intent(in), optional :: fd_step, backtrack_c integer(int32), intent(in), optional :: verbosity real(real64), intent(in), optional :: lower_bounds(:), upper_bounds(:) integer(int32) :: info ! Local variables integer(int32) :: n, iter, bcount, iflag real(real64) :: h, bc, max_residual integer(blint) :: n_bl, nrhs, lda, ldb, lapack_info real(real64), allocatable :: x_new(:) logical :: has_bounds n = ws%n_vars h = DEFAULT_FD_STEP bc = DEFAULT_BACKTRACK_C if (present(fd_step)) h = fd_step if (present(backtrack_c)) bc = backtrack_c ! Check if bounds are provided has_bounds = present(lower_bounds) .and. present(upper_bounds) allocate(x_new(n)) nfev = 0 info = BROYDEN_SUCCESS ! Step 1: Evaluate initial residual f(x0) iflag = 0 call fcn(n, x, fvec, iflag) nfev = nfev + 1 if (iflag < 0) then info = BROYDEN_FCN_ERROR return end if ! Main iteration loop do iter = 1, max_iter ! Check convergence max_residual = maxval(abs(fvec)) if (max_residual < tol) then info = BROYDEN_SUCCESS return end if ! Step 2: Compute Jacobian (first iteration only) if (iter == 1) then if (present(verbosity)) then if (verbosity == 2) & call mexPrintf(' Computing initial Jacobian via finite differences...'//NEW_LINE('A')) end if call compute_fd_jacobian(ws, x, fvec, fcn, h, nfev, iflag, verbosity) if (iflag < 0) then info = BROYDEN_FCN_ERROR return end if end if ! Step 3: Solve J * dx = -fvec ! Copy J to J_copy (dgesv overwrites it) ws%J_copy = ws%J ! Set dx = -fvec (right-hand side) ws%dx = -fvec ! Call LAPACK dgesv n_bl = int(n, blint) nrhs = 1_blint lda = n_bl ldb = n_bl call dgesv(n_bl, nrhs, ws%J_copy, lda, ws%ipiv, ws%dx, ldb, lapack_info) if (lapack_info /= 0) then info = BROYDEN_SINGULAR_JAC return end if ! Step 4: Backtracking line search do bcount = 1, DEFAULT_MAX_BACKTRACK ! Compute new point: x + dx, then clamp to bounds if present x_new = x + ws%dx if (has_bounds) call clamp_to_bounds(x_new, lower_bounds, upper_bounds, n) ! Try new point iflag = 0 call fcn(n, x_new, ws%fvec_new, iflag) nfev = nfev + 1 if (iflag < 0) then ! Function evaluation failed, backtrack ws%dx = ws%dx * bc else ! Success: update Jacobian with Broyden rank-1 update ! df = fvec_new - fvec ws%df = ws%fvec_new - fvec ! Compute actual dx (may differ from ws%dx due to clamping) ws%dx = x_new - x ! Move to new point (must be done BEFORE broyden_update ! because broyden_update overwrites ws%fvec_new as workspace) fvec = ws%fvec_new x = x_new ! Broyden update: J = J + outer((df - J*dx) / ||dx||^2, dx) call broyden_update(ws) exit end if end do if (bcount > DEFAULT_MAX_BACKTRACK) then info = BROYDEN_MAX_BACKTRACK return end if end do ! Maximum iterations exceeded info = BROYDEN_MAX_ITER end function broyden_solve !--------------------------------------------------------------------------- ! Clamp variables to bounds ! ! For each variable, if the bound is finite (not -Inf or +Inf), clamp. !--------------------------------------------------------------------------- subroutine clamp_to_bounds(x, lb, ub, n) real(real64), intent(inout) :: x(:) real(real64), intent(in) :: lb(:), ub(:) integer(int32), intent(in) :: n integer :: i do i = 1, n if (ieee_is_finite(lb(i))) x(i) = max(x(i), lb(i)) if (ieee_is_finite(ub(i))) x(i) = min(x(i), ub(i)) end do end subroutine clamp_to_bounds !--------------------------------------------------------------------------- ! Compute initial Jacobian via forward finite differences ! ! J(:,i) = (f(x + h*e_i) - f(x)) / h !--------------------------------------------------------------------------- subroutine compute_fd_jacobian(ws, x, fvec, fcn, h, nfev, iflag, verbosity) type(broyden_workspace), intent(inout) :: ws real(real64), intent(in) :: x(:), fvec(:) procedure(residual_fcn) :: fcn real(real64), intent(in) :: h integer(int32), intent(inout) :: nfev integer, intent(out) :: iflag integer(int32), intent(in), optional :: verbosity integer(int32) :: i, n real(real64) :: x_orig character(len=256) :: msg n = ws%n_vars iflag = 0 do i = 1, n ! Perturb x(i) x_orig = x(i) ws%fvec_new(1:n) = x ! Use fvec_new as temporary x_pert ws%fvec_new(i) = x_orig + h ! Evaluate f(x + h*e_i) call fcn(n, ws%fvec_new, ws%df, iflag) nfev = nfev + 1 if (iflag < 0) return ! Forward difference: J(:,i) = (f_pert - f) / h ws%J(:, i) = (ws%df - fvec) / h ! Debug output if (present(verbosity)) then if (verbosity == 2) then write(msg, '(A,I2,A,ES12.5,A,ES12.5,A,ES12.5,A,ES12.5)') & ' FD[', i, ']: x=', x_orig, ', h=', h, & ', f=', fvec(1), ', f_pert=', ws%df(1) call mexPrintf(trim(msg)//NEW_LINE('A')) write(msg, '(A,ES12.5)') ' J=', ws%J(1, i) call mexPrintf(trim(msg)//NEW_LINE('A')) end if end if end do end subroutine compute_fd_jacobian !--------------------------------------------------------------------------- ! Broyden rank-1 update ! ! J = J + outer((df - J*dx) / ||dx||^2, dx) ! ! where df = fvec_new - fvec (already computed in ws%df) ! dx = Newton step (in ws%dx) !--------------------------------------------------------------------------- subroutine broyden_update(ws) type(broyden_workspace), intent(inout) :: ws integer(int32) :: n real(real64) :: dx_norm_sq, scale n = ws%n_vars ! Compute ||dx||^2 dx_norm_sq = dot_product(ws%dx, ws%dx) ! Skip update if dx is too small to avoid division by zero if (dx_norm_sq < 1.0e-30_real64) return ! Compute correction = J * dx using BLAS (store in fvec_new as temp) ws%fvec_new = 0.0_real64 call matvecmul_add('N', 1.0_real64, ws%J, ws%dx, 0.0_real64, ws%fvec_new) ! fvec_new = (df - J*dx) / ||dx||^2 scale = 1.0_real64 / dx_norm_sq ws%fvec_new = (ws%df - ws%fvec_new) * scale ! Rank-1 update: J = J + outer(fvec_new, dx) using BLAS dger ! dger: A = alpha * x * y^T + A call rank_one_update(n, n, 1.0_real64, ws%fvec_new, ws%dx, ws%J) end subroutine broyden_update end module broyden_solver