Exploiting sparsity in large-scale optimization

最优化寻求找到参数的最佳组合，根据某个给定的标准，这些参数将产生最佳的可能结果。更准确地说，数学优化问题包括一组描述系统的定义参数，以及依赖于这些参数并确定系统运行情况的目标。此外，可能存在限制允许参数值的条件(在实践中通常是这样)。从计算机科学和工程到运筹学和经济学，优化问题在定量学科中随处可见。常见的日常应用包括最小化生产成本、最大化利润、最小化所需资源等。EPSRC的工程主题领域，包括控制、机械、过程和水工程以及仪器仪表，强调了优化的基本需要。由于求解优化问题的需求如此广泛，优化算法的性能(在时间和/或可靠性方面)的提高对研究、工业、金融、医疗保健等领域都具有潜在的深远意义，在许多实际情况下，参数的数量很大，使得优化问题的求解具有挑战性。然而，经常可以将问题结构化，使得参数之间的交互是局部的，即每个参数仅与少量其他参数直接相关。这导致了所谓的稀疏性。许多大规模优化问题都是自然稀疏的，为了提高效率，在求解算法的开发中使用稀疏性是必不可少的。事实上，尽管有功能强大的现代计算机，除非利用稀疏性，否则许多问题在计算上是难以解决的。优化算法通常需要访问数学模型中函数的一阶和二阶导数。不幸的是，可能很难提供获得所谓的海森矩阵所需的二阶导数。本项目的目的是通过提出一种构造海森矩阵逼近的新方法来提高大规模优化的效率和可靠性。核心是将问题表述为一个非常大的稀疏线性方程组，它可能是超定的或欠定的(即可能有比未知数更多的方程式或比未知数更少的方程式)。这一提法将允许利用稀疏数值线性代数的思想。该项目的成果不仅是新的算法和理论，还包括高质量软件的实施，这些软件将作为我们国际知名的数学软件库的一部分得到充分支持和维护。这将使新思想得到广泛的接受，远远超出数学研究界的范畴。

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.