Repository Public
1// =============================================================================2// SP BOUCHER | SOFTWARE & RESEARCH3// ARTIFICIAL INTELLIGENCE • FINANCE • ENGINEERING4// =============================================================================5//6// PROJECT METADATA7// -----------------------------------------------------------------------------8// Project : ORIX Sheet9// File : Packages/SheetAnalytics/Sources/Statistics/Optimization/LevenbergMarquardt.swift10// Module : Statistics11// Repository : https://git.spboucher.ai/orix-sheet12// Created : 2026-11-2113// Last Modified : 2026-11-2114//15// =============================================================================16// AUTHOR & PROFESSIONAL AFFILIATION17// =============================================================================18//19// Author : Simon-Pierre Boucher20// Position : Professor of Finance21// Institution : Université du Québec en Outaouais (UQO)22// Department : Département des sciences administratives23// Organization : SP Boucher24//25// Website : https://spboucher.ai26// Git : https://git.spboucher.ai27//28// =============================================================================29// OFFICIAL CONTACT DIRECTORY30// =============================================================================31//32// General : info@spboucher.ai33// Professional : contact@spboucher.ai34// Direct : simon@spboucher.ai35// Research : research@spboucher.ai36// Development : dev@spboucher.ai37// Support : support@spboucher.ai38// Security/Admin : admin@spboucher.ai39// Notifications : notifications@spboucher.ai40//41// Preferred Contact: support@spboucher.ai42//43// =============================================================================44// COPYRIGHT & INTELLECTUAL PROPERTY45// =============================================================================46//47// Copyright (c) 202648// Simon-Pierre Boucher49//50// All rights reserved where applicable.51//52// This file is governed by the applicable project license,53// copyright notices, institutional agreements and relevant law.54//55// Unless expressly authorized by the applicable license or56// rights holder, copying, redistribution, sublicensing,57// publication and commercial exploitation are not permitted.58//59// Existing third-party rights and notices remain unaffected.60//61// =============================================================================62// CONFIDENTIALITY & SECURITY63// =============================================================================64//65// Classification : Public66// Distribution : Public repository; use is governed by the project license67// Security Contact : admin@spboucher.ai68//69// Access to this source does not independently grant permission70// to redistribute or disclose confidential materials.71//72// Do not embed credentials, private keys, access tokens,73// certificates or confidential personal information.74//75// =============================================================================76// LICENSE & MAINTENANCE77// =============================================================================78//79// License : None specified (no license file in this repository)80// Maintainer : Simon-Pierre Boucher81// Technical Contact: dev@spboucher.ai82//83// =============================================================================84// END OF SP BOUCHER SOURCE HEADER85// =============================================================================8687import Foundation88import SheetCore8990/// Result of a nonlinear least-squares fit.91public struct LeastSquaresResult: Sendable, Hashable, Codable, TableReport {92 public var parameters: [Double]93 /// Residuals at the solution.94 public var residuals: [Double]95 /// Σ r_i².96 public var sumOfSquares: Double97 /// Observations minus parameters.98 public var degreesOfFreedom: Int99 /// s² = SSE / (n − p); NaN when n ≤ p.100 public var residualVariance: Double101 /// Asymptotic covariance of the estimates s²·(JᵀJ)⁻¹ (what `scipy.optimize.curve_fit` returns with102 /// `absolute_sigma=False`); nil when JᵀJ is singular or n ≤ p.103 public var covariance: Matrix?104 /// √diag(covariance).105 public var standardErrors: [Double]?106 /// Max-norm of the gradient Jᵀr at the solution.107 public var gradientNorm: Double108 public var iterations: Int109 public var functionEvaluations: Int110 public var converged: Bool111 /// "gradient", "step", "reduction" or "max iterations".112 public var termination: String113114 public func table() -> [[Value]] {115 var out: [[Value]] = [116 Report.row("Method", "Levenberg–Marquardt least squares"),117 Report.row("Converged", converged ? "yes (\(termination))" : "no (\(termination))"),118 Report.row("Iterations", iterations),119 Report.row("Sum of squares", sumOfSquares),120 Report.row("Residual variance", residualVariance),121 Report.row("Degrees of freedom", degreesOfFreedom),122 [.text("Parameter"), .text("Estimate"), .text("Std. error")],123 ]124 for (i, p) in parameters.enumerated() {125 out.append([.text("b\(i + 1)"), Report.num(p), Report.num(standardErrors?[i])])126 }127 return Report.rectangular(out)128 }129}130131public enum LeastSquares {132 public enum JacobianMethod: String, Sendable, Codable { case forward, central }133134 public struct Options: Sendable, Hashable {135 public var maxIterations = 500136 /// Stop when the max-norm of the gradient Jᵀr falls below this.137 public var gradientTolerance = 1e-10138 /// Stop when the step is smaller than stepTolerance·(‖x‖ + stepTolerance).139 public var stepTolerance = 1e-12140 /// Stop when an accepted step reduces the sum of squares by less than this fraction.141 public var reductionTolerance = 1e-14142 /// Finite-difference scheme for the Jacobian when none is supplied.143 public var jacobian = JacobianMethod.central144 /// Initial damping relative to the largest diagonal entry of JᵀJ.145 public var initialDamping = 1e-3146 public init() {}147 }148149 /// Minimises Σ r_i(x)² by the Levenberg–Marquardt method (Marquardt's diagonal scaling, Nielsen's150 /// gain-ratio damping update).151 /// - Parameters:152 /// - residuals: returns the residual vector at x (its length must not change).153 /// - jacobian: optional analytic Jacobian ∂r_i/∂x_j (n × p); otherwise finite differences with relative154 /// step ε^{1/2} (forward) or ε^{1/3} (central).155 public static func levenbergMarquardt(residuals: ([Double]) throws -> [Double], start: [Double],156 jacobian: (([Double]) throws -> Matrix)? = nil,157 options: Options = Options()) throws -> LeastSquaresResult {158 let p = start.count159 guard p > 0 else { throw StatError.invalidInput("at least one parameter is required") }160 var evals = 0161 func resid(_ x: [Double]) throws -> [Double] { evals += 1; return try residuals(x) }162 var x = start163 var r = try resid(x)164 let n = r.count165 guard n > 0, r.allSatisfy(\.isFinite) else { throw StatError.invalidInput("residuals are not finite at the starting point") }166167 func numericJacobian(_ x: [Double], _ r0: [Double]) throws -> Matrix {168 var j = Matrix(rows: n, cols: p)169 for c in 0..<p {170 let scale = max(abs(x[c]), 1e-8)171 if options.jacobian == .forward {172 let h = Double.ulpOfOne.squareRoot() * scale173 var xp = x; xp[c] += h174 let rp = try resid(xp)175 guard rp.count == n else { throw StatError.invalidInput("residual count changed") }176 for i in 0..<n { j[i, c] = (rp[i] - r0[i]) / (xp[c] - x[c]) }177 } else {178 let h = cbrt(Double.ulpOfOne) * scale179 var xp = x, xm = x180 xp[c] += h; xm[c] -= h181 let rp = try resid(xp), rm = try resid(xm)182 guard rp.count == n, rm.count == n else { throw StatError.invalidInput("residual count changed") }183 for i in 0..<n { j[i, c] = (rp[i] - rm[i]) / (xp[c] - xm[c]) }184 }185 }186 return j187 }188 func jac(_ x: [Double], _ r0: [Double]) throws -> Matrix {189 if let jacobian {190 let j = try jacobian(x)191 guard j.rows == n, j.cols == p else { throw StatError.invalidInput("Jacobian must be \(n) × \(p)") }192 return j193 }194 return try numericJacobian(x, r0)195 }196 func sumSq(_ v: [Double]) -> Double { v.reduce(0) { $0 + $1 * $1 } }197198 var f = sumSq(r)199 var j = try jac(x, r)200 var a = j.gram201 var g = j.transposed * r202 var mu = options.initialDamping * max(a.diagonalValues.max() ?? 1, 1e-12)203 var nu = 2.0204 var iterations = 0205 var termination = "max iterations"206 var converged = false207 func gnorm() -> Double { g.reduce(0) { max($0, abs($1)) } }208209 if gnorm() <= options.gradientTolerance { converged = true; termination = "gradient" }210 while !converged && iterations < options.maxIterations {211 iterations += 1212 var lhs = a213 var dscale = [Double](repeating: 0, count: p)214 for i in 0..<p { dscale[i] = max(a[i, i], 1e-12); lhs[i, i] += mu * dscale[i] }215 guard let h = try? LinearAlgebra.solve(lhs, g.map { -$0 }), h.allSatisfy(\.isFinite) else {216 mu *= nu; nu *= 2217 if !mu.isFinite { break }218 continue219 }220 let hnorm = sumSq(h).squareRoot(), xnorm = sumSq(x).squareRoot()221 if hnorm <= options.stepTolerance * (xnorm + options.stepTolerance) { converged = true; termination = "step"; break }222 let xNew = zip(x, h).map(+)223 let rNew = (try? resid(xNew)) ?? []224 let fNew = rNew.count == n && rNew.allSatisfy(\.isFinite) ? sumSq(rNew) : Double.infinity225 var predicted = 0.0 // ½ hᵀ(μ D h − g) · 2 = reduction predicted by the model226 for i in 0..<p { predicted += h[i] * (mu * dscale[i] * h[i] - g[i]) }227 let rho = predicted > 0 ? (f - fNew) / predicted : -1228 if rho > 0, fNew.isFinite {229 let reduction = f - fNew230 x = xNew; r = rNew231 let fOld = f232 f = fNew233 j = try jac(x, r)234 a = j.gram235 g = j.transposed * r236 mu *= max(1.0 / 3, 1 - pow(2 * rho - 1, 3))237 nu = 2238 if gnorm() <= options.gradientTolerance { converged = true; termination = "gradient"; break }239 if reduction <= options.reductionTolerance * fOld { converged = true; termination = "reduction"; break }240 } else {241 mu *= nu242 nu *= 2243 if !mu.isFinite { break }244 }245 }246 let dof = n - p247 let s2 = dof > 0 ? f / Double(dof) : Double.nan248 var cov: Matrix?249 var se: [Double]?250 if dof > 0, let inv = try? LinearAlgebra.inverse(a), inv.data.allSatisfy(\.isFinite) {251 cov = s2 * inv252 se = (0..<p).map { max(cov![$0, $0], 0).squareRoot() }253 }254 return LeastSquaresResult(parameters: x, residuals: r, sumOfSquares: f, degreesOfFreedom: dof, residualVariance: s2,255 covariance: cov, standardErrors: se, gradientNorm: gnorm(), iterations: iterations,256 functionEvaluations: evals, converged: converged, termination: termination)257 }258259 /// Fits y ≈ model(x, parameters) by Levenberg–Marquardt. `weights` (optional, one per observation)260 /// multiply the residuals: use 1/σ_i for known standard deviations.261 public static func curveFit(model: @escaping (Double, [Double]) -> Double, x: [Double], y: [Double], start: [Double],262 weights: [Double]? = nil, options: Options = Options()) throws -> LeastSquaresResult {263 guard x.count == y.count, !x.isEmpty else { throw StatError.invalidInput("x and y must have the same non-zero length") }264 if let weights, weights.count != x.count { throw StatError.invalidInput("one weight per observation is required") }265 return try levenbergMarquardt(residuals: { p in266 (0..<x.count).map { i in (model(x[i], p) - y[i]) * (weights?[i] ?? 1) }267 }, start: start, options: options)268 }269}270