SPB Git

Repository Public

Minimize.swift 10.3 KB 222 lines swift

1import Foundation23/// Outcome of a minimisation.4public struct MinimizeResult: Sendable, Hashable, Codable {5    /// Location of the minimum found.6    public var x: [Double]7    /// Objective value at `x`.8    public var value: Double9    public var iterations: Int10    public var functionEvaluations: Int11    public var converged: Bool12    public var method: String1314    public init(x: [Double], value: Double, iterations: Int, functionEvaluations: Int, converged: Bool, method: String) {15        self.x = x; self.value = value; self.iterations = iterations16        self.functionEvaluations = functionEvaluations; self.converged = converged; self.method = method17    }18}1920public enum Minimizer {21    /// Golden-section search for the minimum of a unimodal function on [lower, upper].22    /// Stops when the bracket is narrower than `xtol`.23    public static func goldenSection(_ f: (Double) throws -> Double, lower: Double, upper: Double,24                                     xtol: Double = 1e-10, maxIterations: Int = 500) rethrows -> MinimizeResult {25        let invPhi = (5.0.squareRoot() - 1) / 226        var a = min(lower, upper), b = max(lower, upper)27        var c = b - invPhi * (b - a), d = a + invPhi * (b - a)28        var fc = try f(c), fd = try f(d)29        var evals = 2, iters = 030        while abs(b - a) > xtol && iters < maxIterations {31            iters += 132            if fc < fd {33                b = d; d = c; fd = fc34                c = b - invPhi * (b - a); fc = try f(c)35            } else {36                a = c; c = d; fc = fd37                d = a + invPhi * (b - a); fd = try f(d)38            }39            evals += 140        }41        let x = fc < fd ? c : d42        return MinimizeResult(x: [x], value: min(fc, fd), iterations: iters, functionEvaluations: evals,43                              converged: abs(b - a) <= xtol, method: "golden-section")44    }4546    /// Brent's bounded minimisation (golden section + successive parabolic interpolation) on [lower, upper].47    public static func brent(_ f: (Double) throws -> Double, lower: Double, upper: Double,48                             xtol: Double = 1e-10, maxIterations: Int = 500) rethrows -> MinimizeResult {49        let cgold = 0.381966011250105150        var a = min(lower, upper), b = max(lower, upper)51        var x = a + cgold * (b - a), w = x, v = x52        var fx = try f(x), fw = fx, fv = fx53        var d = 0.0, e = 0.054        var evals = 155        for iter in 1...max(1, maxIterations) {56            let xm = 0.5 * (a + b)57            let tol1 = Double.ulpOfOne.squareRoot() * abs(x) + xtol / 358            let tol2 = 2 * tol159            if abs(x - xm) <= tol2 - 0.5 * (b - a) {60                return MinimizeResult(x: [x], value: fx, iterations: iter, functionEvaluations: evals, converged: true, method: "brent")61            }62            var useGolden = true63            if abs(e) > tol1 {64                let r = (x - w) * (fx - fv)65                var q = (x - v) * (fx - fw)66                var p = (x - v) * q - (x - w) * r67                q = 2 * (q - r)68                if q > 0 { p = -p }69                q = abs(q)70                let etemp = e71                e = d72                if !(abs(p) >= abs(0.5 * q * etemp) || p <= q * (a - x) || p >= q * (b - x)) {73                    d = p / q74                    let u = x + d75                    if u - a < tol2 || b - u < tol2 { d = xm >= x ? tol1 : -tol1 }76                    useGolden = false77                }78            }79            if useGolden {80                e = x >= xm ? a - x : b - x81                d = cgold * e82            }83            let u = abs(d) >= tol1 ? x + d : x + (d >= 0 ? tol1 : -tol1)84            let fu = try f(u)85            evals += 186            if fu <= fx {87                if u >= x { a = x } else { b = x }88                v = w; fv = fw; w = x; fw = fx; x = u; fx = fu89            } else {90                if u < x { a = u } else { b = u }91                if fu <= fw || w == x {92                    v = w; fv = fw; w = u; fw = fu93                } else if fu <= fv || v == x || v == w {94                    v = u; fv = fu95                }96            }97        }98        return MinimizeResult(x: [x], value: fx, iterations: maxIterations, functionEvaluations: evals, converged: false, method: "brent")99    }100101    public struct NelderMeadOptions: Sendable, Hashable {102        /// Absolute spread of the simplex vertices at which the search stops.103        public var xtol = 1e-8104        /// Absolute spread of the objective over the simplex at which the search stops.105        public var ftol = 1e-8106        /// nil = 200 × dimension.107        public var maxIterations: Int?108        /// nil = 400 × dimension.109        public var maxEvaluations: Int?110        /// Relative size of the initial simplex (SciPy uses 5 %; zero coordinates move by 0.00025).111        public var initialStep = 0.05112        /// After convergence the simplex is rebuilt around the best point and the search repeated, up to113        /// this many times, until a restart no longer improves the objective by more than `ftol`. Restarts114        /// cure the simplex collapsing onto a bound (or a ridge) short of the minimum. 0 = plain Nelder–Mead.115        public var restarts = 4116        public init() {}117    }118119    /// Nelder–Mead downhill simplex (reflection 1, expansion 2, contraction 0.5, shrink 0.5).120    /// With `bounds`, every trial point is clipped to the box (as SciPy does), so the search never121    /// evaluates the objective outside it. Derivative-free; suited to smooth low-dimensional problems.122    public static func nelderMead(_ f: ([Double]) throws -> Double, start: [Double],123                                  bounds: [ClosedRange<Double>]? = nil,124                                  options: NelderMeadOptions = NelderMeadOptions()) throws -> MinimizeResult {125        var best = try nelderMeadOnce(f, start: start, bounds: bounds, options: options)126        var remaining = options.restarts127        while remaining > 0 {128            remaining -= 1129            let again = try nelderMeadOnce(f, start: best.x, bounds: bounds, options: options)130            let improved = best.value - again.value131            let merged = MinimizeResult(x: again.value <= best.value ? again.x : best.x, value: min(again.value, best.value),132                                        iterations: best.iterations + again.iterations,133                                        functionEvaluations: best.functionEvaluations + again.functionEvaluations,134                                        converged: again.converged, method: best.method)135            best = merged136            if !(improved > options.ftol) { break }137        }138        return best139    }140141    private static func nelderMeadOnce(_ f: ([Double]) throws -> Double, start: [Double],142                                       bounds: [ClosedRange<Double>]?, options: NelderMeadOptions) throws -> MinimizeResult {143        let n = start.count144        guard n > 0 else { throw StatError.invalidInput("Nelder–Mead needs at least one variable") }145        if let bounds, bounds.count != n { throw StatError.invalidInput("one bound per variable is required") }146        func clip(_ x: [Double]) -> [Double] {147            guard let bounds else { return x }148            return zip(x, bounds).map { Swift.min(Swift.max($0, $1.lowerBound), $1.upperBound) }149        }150        var evals = 0151        func eval(_ x: [Double]) throws -> Double {152            evals += 1153            let v = try f(x)154            return v.isNaN ? .infinity : v155        }156        let x0 = clip(start)157        var simplex = [x0]158        for i in 0..<n {159            var p = x0160            p[i] = p[i] != 0 ? p[i] * (1 + options.initialStep) : 0.00025161            p = clip(p)162            if p[i] == x0[i] {   // clipped back onto the start: step inwards instead163                p[i] = x0[i] != 0 ? x0[i] * (1 - options.initialStep) : -0.00025164                p = clip(p)165            }166            simplex.append(p)167        }168        var values = try simplex.map { try eval($0) }169        let maxIter = options.maxIterations ?? 200 * n170        let maxEval = options.maxEvaluations ?? 400 * n171        var iters = 0172        var converged = false173        func order() {174            let idx = values.indices.sorted { values[$0] < values[$1] }175            simplex = idx.map { simplex[$0] }176            values = idx.map { values[$0] }177        }178        order()179        while iters < maxIter && evals < maxEval {180            var xSpread = 0.0, fSpread = 0.0181            for k in 1...n {182                fSpread = Swift.max(fSpread, abs(values[k] - values[0]))183                for i in 0..<n { xSpread = Swift.max(xSpread, abs(simplex[k][i] - simplex[0][i])) }184            }185            if xSpread <= options.xtol && fSpread <= options.ftol { converged = true; break }186            iters += 1187            var centroid = [Double](repeating: 0, count: n)188            for k in 0..<n { for i in 0..<n { centroid[i] += simplex[k][i] / Double(n) } }189            func along(_ t: Double) -> [Double] { clip((0..<n).map { centroid[$0] + t * (simplex[n][$0] - centroid[$0]) }) }190            let xr = along(-1)191            let fr = try eval(xr)192            if fr < values[0] {193                let xe = along(-2)194                let fe = try eval(xe)195                if fe < fr { simplex[n] = xe; values[n] = fe } else { simplex[n] = xr; values[n] = fr }196            } else if fr < values[n - 1] {197                simplex[n] = xr; values[n] = fr198            } else {199                var shrink = false200                if fr < values[n] {201                    let xc = along(-0.5)202                    let fc = try eval(xc)203                    if fc <= fr { simplex[n] = xc; values[n] = fc } else { shrink = true }204                } else {205                    let xc = along(0.5)206                    let fc = try eval(xc)207                    if fc < values[n] { simplex[n] = xc; values[n] = fc } else { shrink = true }208                }209                if shrink {210                    for k in 1...n {211                        simplex[k] = clip((0..<n).map { simplex[0][$0] + 0.5 * (simplex[k][$0] - simplex[0][$0]) })212                        values[k] = try eval(simplex[k])213                    }214                }215            }216            order()217        }218        return MinimizeResult(x: simplex[0], value: values[0], iterations: iters, functionEvaluations: evals,219                              converged: converged, method: "nelder-mead")220    }221}222
Files main
Menu

Theme