Reduced Space vs. Full Space Optimization

Resources

• Biros, George, Volkan Akçelik, Omar Ghattas, Judith Hill, David Keyes, Bart Van, and Bloemen Waanders. n.d. “Parallel Algorithms for PDE-Constrained Optimization.”
• Hicken, Jason, and Juan Alonso. 2013. “Comparison of Reduced- and Full-Space Algorithms for PDE-Constrained Optimization.” In 51st AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition. Aerospace Sciences Meetings. American Institute of Aeronautics and Astronautics. https://doi.org/10.2514/6.2013-1043.
• Adavani, Santi S., and George Biros. 2008. “Multigrid Algorithms for Inverse Problems with Linear Parabolic PDE Constraints.” SIAM Journal on Scientific Computing 31 (1): 369–97. https://doi.org/10.1137/070687426.

Related

• Inverse Problems

Main Idea

Within PDE Constrained Optimization there are broadly two classes of methods: full and reduced space methods. For a state vector $\mathbf{u}$, design/optimization variables $\mathbf{d}$, an objective function $\mathcal{J}(\mathbf{u},\mathbf{d})$, and a PDE residual $\mathbf{c}(\mathbf{u},\mathbf{d})$, the general problem is

The PDE problem is well posed; given $\mathbf{d}$, we can uniquely determine $\mathbf{u}$ from $\mathbf{c}$. Although multiple $\mathbf{d}$ may produce the same value of $\mathcal{J}$, meaning the optimization problem can be ill-posed. In the discretized case, we have $\mathbf{u}\in {\mathbb{R}}^n$, $\mathbf{d}\in {\mathbb{R}}^m$, $\mathbf{c}\in {\mathbb{R}}^n$, and $\mathcal{J}(\mathbf{u},\mathbf{d})\in \mathbb{R}$. With adjoint variables or Lagrange multipliers as $\lambda \in {\mathbb{R}}^n$, the Lagrangian is

and the first-order optimality conditions (KKT Conditions) require that its gradient vanishes, implying

Now to focus on a few terms:

• $[{\partial }_{\mathbf{u}}\mathbf{c}]$ is the standard Jacobian of the PDE, which is often used in its solution. This first equation is also known as the Adjoint Equation.
• The $\mathbf{c}=0$ condition (Primal Feasibility) simply states that $\mathbf{u}$ must satisfy the PDE corresponding to $\mathbf{d}$.
• In many cases, ${\partial }_{\mathbf{d}}\mathcal{J}$ is $\mathbf{0}$, as $\mathbf{d}$ does not explicitly appear in the loss, e.g. in (unregularized) Inverse Problems.
  There are $2n+m$ resulting equations.

Full Space methods solve the KKT system directly, optimizing over $2n+m$ variables, while Reduced Space methods solve the first and third sets of equations before tackling the second set. In other words, they remove $\mathbf{u}$ and $\lambda$ from the optimization problem by solving the original PDE and the adjoint equation, respectively, for a given value of $\mathbf{d}$.

Full Space

Applying a Newton step to the KKT system gives a $2n+m\times 2n+m$ matrix system for the update to $\mathbf{u},\mathbf{d}$ and $\lambda$. This is generally too large for a direct solve, but Iterative Linear Solvers also suffer from ill-conditioning. These methods generally require specialized Preconditioners and may be slow to converge.

Reduced Space

We can rewrite the optimization such that $\mathbf{u}$ depends on $\mathbf{d}$, which happens implicitly through $\mathbf{c}(\mathbf{u},\mathbf{d})=\mathbf{0}$. Then our problem is

where ${\mathcal{J}}^{\prime }(\mathbf{d})=\mathcal{J}(\mathbf{u}(\mathbf{d}),\mathbf{d})$, and $\mathbf{c}(\mathbf{u}(\mathbf{d}),\mathbf{d})=\mathbf{0}$ by construction. This option is more clearly dependent on the well-posedness of the forward problem, as we must invert $\mathbf{c}(\bullet ,\mathbf{d})$ to get $\mathbf{u}(\mathbf{d})$. With this simplification we can either reduce the original KKT system or apply first order optimality again to get the same result of

Note also that $\lambda =\lambda (\mathbf{d})$, implicitly through the adjoint equation. These methods require full forward (and adjoint) solves far from the optimum. Through the inversion of $\mathbf{c}(\bullet ,\mathbf{d})$ (or strict enforcement of $\mathbf{c}(\mathbf{u},\mathbf{d})=0$), the problem may be more nonlinear in $\mathbf{d}$.