M2: Design optimisation

Project completed September 30, 2010

Background

Partial differential equations (PDEs) can be used to describe many different physical processes. They are a very important mathematical tool for understanding the physical world, and are utilised by researchers across numerous disciplines.

Many modern PDE problems are too complex to be solved analytically and thus rely on numerical methods. There have been tremendous improvements in the methods used to compute solutions to the discretised PDEs over the last few decades. However, even with powerful computers, the numerical solution to PDEs can be a great computational burden. The solutions of important mathematical, physical and engineering problems depend on the ability to efficiently and accurately calculate a numerical solution, and finding improved methods remains a huge area of research.

Researchers at the Oxford Centre for Collaborative Applied Mathematics (OCCAM) have developed methods to improve the performance of solving design optimisation problems, with PDE constraints. These problems involve solving an inverse problem, where some optimality criterion is to be satisfied, and with additional constraints, which are themselves PDE problems, linked to design parameters. These are distinctly different from traditional ‘forward’ problems and present additional numerical challenges.

Techniques and Challenges

To understand an inverse problem, consider the example of the shape of a car. The airflow over the car is described by a PDE that depends on the shape, material and speed of the car. The forward problem would be, given the parameters (shape, material and speed) “find the airflow over the car”, which is found by solving the PDE. On the other hand, the inverse problem would be “find the shape and material of a car that yields, for example, the most fuel efficient design”, given that the airflow is described by a PDE. Here, the PDE is a constraint based on the physics of the problem. This is a PDE-constrained optimisation problem.

Inverse problems are often ill-posed, meaning that they may need to be reformulated before they can be solved numerically. This project formulated preconditioning strategies to enable the efficient solution of a number of different optimal control problems.

A preconditioner is an operator that transforms an existing problem into one that can be solved more efficiently numerically. A preconditioned problem will typically arrive at a solution more quickly.

This work considered inverse problems in the form of PDE-constrained optimisation problems, of which there are many variations. Two specific problems, outlined below, were shown to reduce to a linear system – the so-called saddle point form – and then solved efficiently using iterative methods with a preconditioner.

When a problem that is time-dependent is solved numerically, it must first be discretised. Rather than solve the inverse problem at each individual time step, an ‘all-at-once’ or ‘one-shot’ formulation solves for all time steps at the same time, as well as the optimality conditions. Solving a problem all-at-once strongly couples the constraints and optimisation at the level of linearisation.

Another specific problem that was examined in this work was the Allen-Cahn variational inequalities, which are used to model the behaviour of iron alloys during phase transitions and are also used in image processing techniques. This problem can be formulated as a PDE-constrained optimisation problem.

Results

The researchers first showed that the all-at-once formulation leads to a problem in saddle point form. To solve this linear problem efficiently, preconditioners were proposed and it was shown via numerical simulation that these preconditioners achieved significant speed up with essentially the same amount of storage and computation as an iteration of an uncoupled approach.

At the heart of solving the Allen-Cahn variational inequalities again lies solving the saddle point form linear problem. Using an appropriate preconditioner, these problems can be solved efficiently. For this problem, especially when the number of discretisation points is very large, the preconditioning reduces the number of iterations, and thus computation time, significantly.

The Future

The main aim of the project was the development of fast solvers for design optimisation problems with PDE constraints. These problems are prevalent in the physical sciences, common in fields such as aerospace engineering, computers, and electronics. The project achieved its goal and the work allows for significant speed up using preconditioning strategies. The methods developed enable the efficient solution of a number of different optimisation problems. 

References

[10/25] Blank L., Sarbu L., Stoll M.: Preconditioning for Allen-Cahn Variational Inequalities with Non-Local Constraints

[09/29] Rees T., Stoll M., Wathen A.: All-at-once preconditioning in PDE-constrained optimization, Kybernetika

[09/25] Stoll M., Wathen A.: Preconditioning for active set and projected gradient methods as semi-smooth Newton methods for PDE-constrained optimization with control constraints, Numerical Linear Algebra with Applications

[09/15] Rees T., Stoll M.: Block triangular preconditioners for PDE constrained optimization, Numerical Linear Algebra with Applications