A Modified Algorithm for Broyden Family Using Natural Cubic Spline Interpolation Polynomial

Source abstract

The approximation of the objective function's second-derivatives matrix underlies the Broyden family (BF) of unconstrained optimization methods, and richer gradient information generally yields a more accurate approximation. This paper proposes a new optimization technique that replaces the traditional two-point, secant-based linear model of the gradient with a Natural Cubic Spline Interpolation Polynomial (NCSIP), constructed using either three points (M=2) or four points (M=3). The proposed method was implemented in MATLAB and tested against the traditional Broyden family method (M=1) on a set of standard unconstrained test problems across the range The traditional method (M=1) recorded a total of 11564 iterations and 14867 function/gradient evaluations, while the four-point NCSIP model (M=3) achieved a clear efficiency improvement, with totals of 11063 iterations and 14082 function/gradient evaluations; the improvement achieved by the three-point model (M=2) was comparatively modest (11627 iterations and 14750 function/gradient evaluations). The best performance of the M=3 model was observed at higher values of the parameter Φ (near Φ=1), where it clearly outperformed the traditional method. The proposed method was also compared against the related Newton Divided Difference Interpolation (NDDI) method, using its corresponding three-point (M=4) and four-point (M=5) variants; the results showed a marginal numerical advantage of NCSIP over NDDI in total function/gradient evaluations when using four points (14082 vs. 14187). Taken together, these findings suggest that the number of gradient evaluations exploited, rather than the specific interpolation scheme, is the primary driver of efficiency gains. It should be noted that the algorithm's convergence properties are inferred from its algebraic reduction to the classical secant-based Broyden equation near the minimum, rather than established through a formal convergence proof.