Repository Public
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