Multigrid Algorithms for Discretized Optimization Problems

Stephen Nash
George Mason University
Systems Eng. & Op. Res.

Many large optimization problems represent a family of models of varying size, corresponding to different discretizations.
An example is the optimization of systems governed by differential equations. In such problems, one has a set of design
variables along with a set of state variables, the two sets of variables being related through a set of differential equation
constraints. The overall computational cost of optimization is determined by the level of discretization used to numerically
solve the governing differential equations. If a fine discretization is used, one expects a greater degree of physical and
mathematical fidelity to the problem under consideration, but the large number of state variables can make the cost of
optimization prohibitive.

We present a multigrid algorithm that uses solutions to optimization problems based on coarser discretizations, which
are less expensive to compute, in a systematic manner to obtain the solution of the optimization problem based on a
finer discretization. Of interest is the fact that the approach is applicable in situations where multigrid applied only to the
solution of the differential equation might not be effective. We give evidence (both theoretical and numerical) that a multigrid
approach can often be successful in the more general setting of optimization, and that the optimization setting offers a
number of practical advantages for solving problems of this type.

Speaker bio
Presentation (PowerPoint File)

Back to Multilevel Optimization in VLSICAD