Source code for morphogen.optimization.mma

"""Method of moving asymptotes (Svanberg 1987, 2002).

Each iteration replaces the problem

    minimize f0(x)  subject to  fi(x) <= 0 (i = 1..m),  xmin <= x <= xmax

by a convex separable approximation built on moving asymptotes ``low < x < upp`` and
solves it by a primal-dual interior-point method, as in Svanberg's notes "MMA and GCMMA,
two methods for nonlinear optimization" (2007), with artificial variables ``y_i`` of
cost ``c_i y_i + d_i y_i^2 / 2`` that make every subproblem feasible.
"""

from __future__ import annotations

import numpy as np


[docs] class MMA: """Optimizer state: call :meth:`update` with the current point, objective and constraint values and gradients; it returns the next point.""" def __init__( self, n: int, m: int, xmin, xmax, *, move: float = 0.5, asyinit: float = 0.5, asyincr: float = 1.2, asydecr: float = 0.7, c: float = 1000.0, ): self.n, self.m = int(n), int(m) if self.m < 1 or self.m >= self.n: raise ValueError("MMA here needs 1 <= m < n constraints") self.xmin = np.broadcast_to(np.asarray(xmin, dtype=float), (self.n,)).copy() self.xmax = np.broadcast_to(np.asarray(xmax, dtype=float), (self.n,)).copy() self.move = float(move) self.asyinit, self.asyincr, self.asydecr = asyinit, asyincr, asydecr self.a0 = 1.0 self.a = np.zeros(self.m) self.c = np.full(self.m, float(c)) self.d = np.ones(self.m) self.iteration = 0 self.xold1 = None self.xold2 = None self.low = None self.upp = None
[docs] def reset(self) -> None: """Forget the asymptotes after a change of the problem (a continuation step): asymptotes tightened by past oscillations would hold the design in place.""" self.iteration = 0 self.xold1 = None self.xold2 = None
[docs] def update(self, x, f0, df0, fval, dfdx) -> np.ndarray: x = np.asarray(x, dtype=float).copy() df0 = np.asarray(df0, dtype=float).reshape(self.n) fval = np.atleast_1d(np.asarray(fval, dtype=float)) dfdx = np.asarray(dfdx, dtype=float).reshape(self.m, self.n) self.iteration += 1 span = self.xmax - self.xmin if self.iteration <= 2 or self.xold2 is None: self.low = x - self.asyinit * span self.upp = x + self.asyinit * span else: sign = (x - self.xold1) * (self.xold1 - self.xold2) factor = np.ones(self.n) factor[sign > 0] = self.asyincr factor[sign < 0] = self.asydecr self.low = x - factor * (self.xold1 - self.low) self.upp = x + factor * (self.upp - self.xold1) self.low = np.clip(self.low, x - 10.0 * span, x - 0.01 * span) self.upp = np.clip(self.upp, x + 0.01 * span, x + 10.0 * span) albefa = 0.1 alpha = np.maximum.reduce( [self.xmin, self.low + albefa * (x - self.low), x - self.move * span] ) beta = np.minimum.reduce( [self.xmax, self.upp - albefa * (self.upp - x), x + self.move * span] ) xmami = np.maximum(span, 1e-5) ux1 = self.upp - x xl1 = x - self.low ux2, xl2 = ux1 * ux1, xl1 * xl1 raa0 = 1e-5 p0 = np.maximum(df0, 0.0) q0 = np.maximum(-df0, 0.0) pq0 = 0.001 * (p0 + q0) + raa0 / xmami p0 = (p0 + pq0) * ux2 q0 = (q0 + pq0) * xl2 p = np.maximum(dfdx, 0.0) q = np.maximum(-dfdx, 0.0) pq = 0.001 * (p + q) + raa0 / xmami p = (p + pq) * ux2 q = (q + pq) * xl2 b = p @ (1.0 / ux1) + q @ (1.0 / xl1) - fval xnew = _subsolve( self.m, self.n, self.low, self.upp, alpha, beta, p0, q0, p, q, self.a0, self.a, b, self.c, self.d, ) self.xold2 = self.xold1 self.xold1 = x return xnew
def _subsolve( m, n, low, upp, alpha, beta, p0, q0, p, q, a0, a, b, c, d, epsimin: float = 1e-7 ) -> np.ndarray: """Primal-dual Newton solution of the MMA subproblem (Svanberg's subsolv).""" een = np.ones(n) eem = np.ones(m) epsi = 1.0 x = 0.5 * (alpha + beta) y = eem.copy() z = 1.0 lam = eem.copy() xsi = np.maximum(een / (x - alpha), een) eta = np.maximum(een / (beta - x), een) mu = np.maximum(eem, 0.5 * c) zet = 1.0 s = eem.copy() def residual(x, y, z, lam, xsi, eta, mu, zet, s, epsi): ux1 = upp - x xl1 = x - low plam = p0 + p.T @ lam qlam = q0 + q.T @ lam gvec = p @ (1.0 / ux1) + q @ (1.0 / xl1) dpsidx = plam / ux1**2 - qlam / xl1**2 return np.concatenate( [ dpsidx - xsi + eta, c + d * y - mu - lam, [a0 - zet - a @ lam], gvec - a * z - y + s - b, xsi * (x - alpha) - epsi, eta * (beta - x) - epsi, mu * y - epsi, [zet * z - epsi], lam * s - epsi, ] ) while epsi > epsimin: res = residual(x, y, z, lam, xsi, eta, mu, zet, s, epsi) resnorm = np.linalg.norm(res) resmax = np.max(np.abs(res)) inner = 0 while resmax > 0.9 * epsi and inner < 200: inner += 1 ux1 = upp - x xl1 = x - low ux2, xl2 = ux1**2, xl1**2 ux3, xl3 = ux1 * ux2, xl1 * xl2 plam = p0 + p.T @ lam qlam = q0 + q.T @ lam gvec = p @ (1.0 / ux1) + q @ (1.0 / xl1) gg = p / ux2 - q / xl2 # (m, n) dpsidx = plam / ux2 - qlam / xl2 delx = dpsidx - epsi / (x - alpha) + epsi / (beta - x) dely = c + d * y - lam - epsi / y delz = a0 - a @ lam - epsi / z dellam = gvec - a * z - y - b + epsi / lam diagx = 2.0 * (plam / ux3 + qlam / xl3) + xsi / (x - alpha) + eta / (beta - x) diagy = d + mu / y diaglamyi = s / lam + 1.0 / diagy blam = dellam + dely / diagy - gg @ (delx / diagx) alam = np.diag(diaglamyi) + (gg / diagx) @ gg.T aa = np.zeros((m + 1, m + 1)) aa[:m, :m] = alam aa[:m, m] = a aa[m, :m] = a aa[m, m] = -zet / z sol = np.linalg.solve(aa, np.concatenate([blam, [delz]])) dlam, dz = sol[:m], sol[m] dx = -delx / diagx - (gg.T @ dlam) / diagx dy = -dely / diagy + dlam / diagy dxsi = -xsi + epsi / (x - alpha) - xsi * dx / (x - alpha) deta = -eta + epsi / (beta - x) + eta * dx / (beta - x) dmu = -mu + epsi / y - mu * dy / y dzet = -zet + epsi / z - zet * dz / z ds = -s + epsi / lam - s * dlam / lam xx = np.concatenate([y, [z], lam, xsi, eta, mu, [zet], s]) dxx = np.concatenate([dy, [dz], dlam, dxsi, deta, dmu, [dzet], ds]) stmxx = np.max(-1.01 * dxx / xx) stmalfa = np.max(-1.01 * dx / (x - alpha)) stmbeta = np.max(1.01 * dx / (beta - x)) step = 1.0 / max(stmxx, stmalfa, stmbeta, 1.0) old = (x, y, z, lam, xsi, eta, mu, zet, s) newnorm = 2.0 * resnorm tries = 0 while newnorm > resnorm and tries < 50: tries += 1 x = old[0] + step * dx y = old[1] + step * dy z = old[2] + step * dz lam = old[3] + step * dlam xsi = old[4] + step * dxsi eta = old[5] + step * deta mu = old[6] + step * dmu zet = old[7] + step * dzet s = old[8] + step * ds res = residual(x, y, z, lam, xsi, eta, mu, zet, s, epsi) newnorm = np.linalg.norm(res) step *= 0.5 resnorm = newnorm resmax = np.max(np.abs(res)) epsi *= 0.1 return x