SPB Git

Repository Public

LevenbergMarquardt.swift 12.6 KB 270 lines swift

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
Files main
Menu

Theme