Exploiting sparsity in large-scale optimization

Optimization seeks to find the best combination of parameters that will result in the best possible outcome according to some given criterion. More precisely, a mathematical optimization problem consists of a set of defining parameters that describe the system, together with an objective that depends on the parameters and determines how well the system is performing. In addition, there may be (and often are in practice)
conditions that constrain the allowable parameter values.

Optimization problems arise everywhere in quantitative disciplines, ranging from computer science and engineering to operations research and economics. Common everyday applications include minimizing production costs, maximizing profits, minimizing required resources, and so on. The essential need for optimization is highlighted by EPSRC theme areas in engineering, including control, mechanical, process and water engineering and instrumentation. Because the need to solve optimization is so widespread, improvements in performance (in terms of time and/or reliability) of optimization algorithms have potentially far-reaching benefits for research, industry, finance, healthcare and beyond.

In many practical situations, the number of parameters is large, making the optimization problem challenging to solve. However, it is frequently possible to structure the problem so that the interactions between parameters are local, that is, each parameter is only directly involved with a small number of other parameters. This leads to what is known as sparsity. Many large-scale optimization problems are naturally sparse and for efficiency it is essential that the sparsity is used in the development of solution algorithms. Indeed, despite the availability of powerful modern computers, unless sparsity is exploited, many problems are computationally intractable.

Optimization algorithms often require access to first and second derivatives of functions within the mathematical model. Unfortunately, it can be difficult to provide the second derivatives needed to obtain so-called Hessian matrices. The aim of this project is to improve the efficiency and reliability of large-scale optimization by proposing a new approach for constructing approximations to Hessian matrices. Central to this will be formulating the problem as a very large sparse system of linear equations, which may be over-determined or under-determined (that is, there may be more equations than unknowns or fewer equations than unknowns). This formulation will allow the exploitation of ideas from sparse numerical linear algebra.

The outcomes of the project will not only be new algorithms and theory but also implementations in high-quality software that will be fully supported and maintained as part of our internationally-renowned mathematical software libraries. This will enable wide take-up of the new ideas, well beyond the mathematics research community.