There's a general setup common to many design optimization problems. We'd like to minimize (or equivalently maximize) some measure of goodness $f$ of a given object $x$. Meanwhile, the design of that object is determined by a (usually smaller) set of parameters $p$. If the object is to exist in the physical world then it will likely have to balance a force equilibrium equation $g(x,p) = 0$.

Written as a constrained optimization problem, we're looking for the design parameters $p$ that minimize $f$ while satisfying the equilibrium according to $g$:

Even if the objective $f$ is a simple function (e.g., linear, quadratic in $x$) and even if the design $x$ is a simple function (e.g., linear in $p$), if the constraint function $g$ is a non-linear function of the design parameters $p$ then this is a difficult problem to solve.

One approach to this problem is called sensitivity analysis. It's been used a lot in computer graphics by folks like David Levin and Bernhard Thomaszewski. The idea is to start with feasible design parameters $p_0$. That is, parameters that satisfy our constraint function $g$:

The goal now is to improve these parameters with respect to minimizing the objective $f$ while maintaining feasibility (maintaining $g=0$). In other words, we'd like our change in parameters $ ∆p $ to keep us at $g = 0$. Or in other words, we'd like that total derivative of the constraint $g$ with respect to our parameters $p$ is zero (i.e., zero plus no change is still zero):

This total derivative is composed of the partial derivatives of the constraint with respect to the parameters $p$ and the partial derivatives of the constraint with respect to the design $x$ and applying the chain rule the partial derivative of the design $x$ with respect to the parameters $p$:

$$ \frac{d g}{d p} = \frac{∂ g}{∂ p} + \frac{∂ g}{∂ x} \frac{∂ x}{∂ p}. $$

We can solve for the change in the design w.r.t. the parameters that keeps this quantity zero:

$$ \frac{∂ g}{∂ p} + \frac{∂ g}{∂ x} \frac{∂ x}{∂ p} = 0 \\ \frac{∂ g}{∂ x} \frac{∂ x}{∂ p} = -\frac{∂ g}{∂ p} \\ \frac{∂ x}{∂ p} = -\left( \frac{∂ g}{∂ x} \right)^{-1} \frac{∂ g}{∂ p}. $$

Remember $\frac{∂ g}{∂ x}$ is a $k \times n$ matrix. Numerically we'll construct this matrix but we won't actually compute it's inverse. Instead anytime we read $A^{-1} B$ we think of this as invoking a solver that solves the equation: $A X = B$.

So far we have found a change in the parameters $p$. that will maintain (up to first order) satisfaction of our constraints $g$. The final step is to use this to minimize our objective $f$. We can use any first-order optimization strategy (e.g., gradient descent, NADAM, quasi-Newton, LBFGS). These rely on computing the gradient of the objective $f$ with respect to the optimization variables (in our case, the design parameters $p$). We can derive these by again invoking the chain rule:

Plugging in our formula for $\frac{∂ x}{∂ p}$ above we get and expression for the change in the objective with respect to the change in parameters:

$$ \frac{∂ f}{∂ p} = \frac{∂ f}{∂ x} \left( -\left( \frac{∂ g}{∂ x} \right)^{-1} \frac{∂ g}{∂ p} \right). $$

There's one final step that won't change the solution but will speed up computation. This is called the adjoint method. By a simple change in the parenthesis, we switch from solving a linear system against a matrix $ \frac{∂ g}{∂ p} $ on the right to solving against a vector $\frac{∂ f}{∂ x}$ on the left:

$$ \frac{∂ f}{∂ p} = -\left(\frac{∂ f}{∂ x} \left( \frac{∂ g}{∂ x} \right)^{-1}\right) \frac{∂ g}{∂ p} . $$

Remember we don't actually construct the matrix inverse. If we want to compute $b A^{-1}$ then we can solve the system $A^\top x = b^\top$.

Comments

February 28, 2019, Alec

Dave pointed out that often $g = 0$ is the result of minimizing another objective. For example, $A'A x + A'b = 0$ results from $\mathop{\text{minimize}}_x |A x - b|^2$, so sensitivity analysis + adjoint method is actually a method to do multi-objective optimization (in particular a priori lexicographic multiobjective optimization, a.k.a., ??).

March 14, 2019, Miles

Very nice write up Alec! Nice to see the variational point of view.

March 5, 2024, Alec

But what do you do with these gradients?

In non-linear optimization, it's common to combine descent methods with a line search to ensure progress:

while not converged
      x ← run forward sim given p
      df/dp ← - ( df/dx ( dg/dx)⁻¹ ) dg/dp @ x,p
      dp ← - df/dp
      // Conduct a line search which requires full function evaluation
      // of f in turn requiring a forward simulation to get x
      f ← f(x)
      t ← 1
      for a few iterations
            p₁ ← p + α dp
            // This is very expensive!
            x₁ ← run forward sim given p₁
            if f(x₁,p₁) < f + 0.01 (df/dxᵀ dp)
                  break
            t ← ½ t
      p ← p + t dp

This is very expensive because every line search requires a full forward simulation.

Instead, it may be better to use a fixed time step and even coast a bit before finding a valid $x$ via simulation. Rather we'll update $x$ using a matching step along $\frac{\partial f}{\partial x}$:

while not converged
      x ← run forward sim given p
      // Now we know that g(x,p) = 0
      for a few iterations or maybe until ‖ g(x,p) ‖ > ε
            // all these terms need to be recomputed but we don't need
            // to rerun the forward sim yet.
            df/dp ← - ( df/dx ( dg/dx)⁻¹ ) dg/dp @ x,p
            x ← p - γ df/dx
            p ← p - γ df/dp
            // Now we hope that g(x,p) ≈ 0

Design optimization using sensitivity analysis and the adjoint method

Alec Jacobson

February 23, 2019

weblog/

Comments