Multilevel Methods for Large-Scale Nonlinear Optimization

12da3c27-4a63-44ca-8b7d-7a8658226238

Closed

EPSRC
EPSRC
EPSRC
EPSRC
EPSRC

£43,755

Jan. 19, 2009

April 18, 2009

The solution of large-scale nonlinear optimization - -minimization ormaximization - problems lies at the heart of scientificcomputation. Structures take up positions of minimal constrainedpotential energy, investors aim to maximize profit while controllingrisk, public utilities run transmission networks to satisfy demand atleast cost, and pharmaceutical companies desire minimal drug doses totarget pathogens. All of these problems are large either because themathematical model involves many parameters or because they are actuallyfinite discretisations of some continuous problem for which thevariables are functions.The purpose of this research is to support the design, analysis anddevelopment of new algorithms for nonlinear optimization that areparticularly aimed at the large-scale case, and most especially thoseinvolving constraints arising from the discretisation of (ordinary orpartial) differential equations. Different levels of discretisationlead to different, but related, descriptions of the original problem - afine discretisation leads to an accurate approximation which may beexpensive to solve, while a coarse discretisation may be less accurateby cheaper to solve. Multi-level methods move between differentdiscretisations, refining solutions from the coarse ones so that theyprovide good starting guesses for solutions on the finer ones. This then often leads to a very effective solution method.While such methods are appropriate when multilevel discretisations areavailable, in many problems this is not the case. In our research, weaim to address this difficulty by using algebraic methods recursively toidentify hidden multi-level or dominant structures. Ultimately, ouraim is to automate the detection of such structure so that this istransparent to the users of general-purpose constrained-optimizationsoftware.