Least Squares: Fit for the Future

该项目旨在开发新的算法、支持理论和软件，以解决科学、工程、规划和经济学中出现的最小二乘问题。最小二乘涉及找到一个近似解的过度确定或不精确指定的方程组。现实生活中的应用比比皆是。天气预报员希望做出更准确的预报；气候学家希望更好地了解气候变化；医护人员希望实时生成更精确的图像；金融家希望通过将资本资产定价模型拟合到观察到的财务数据中，来分析和量化投资的系统性风险。寻找“最佳”解决方案通常需要构建一个数学模型来描述问题，然后将该模型拟合到观察到的数据中。这种模型通常很复杂；具有数百万个变量和限制的模型并不罕见，但它们都不是相对较小但极其困难的模型。因此，必须在计算机上实现该模型并使用计算机算法进行求解。后一项任务是拟议活动的核心。几乎所有这样的大规模问题都有一个潜在的数学结构，比如稀疏性。也就是说，大型系统的参数之间的相互作用通常是局部的，不涉及所有组件之间的任何直接相互作用。为了有效地解决以这种方式表示的系统和模型，需要开发能够利用这些潜在的“更简单”结构的算法，这通常会减少问题的规模，从而加快解决速度。这项工作通常不仅导致实现现有方法的新软件，而且导致创建新的理论和实用算法。在另一个极端，一些问题涉及所有组件之间的交互，虽然底层结构不太透明，但它仍然存在。在这些情况下，计算负担可能非常高，这类问题通常只能通过复杂地使用大规模并行计算机来解决。我们将开发的方法旨在有效而稳健地解决给定的问题。由于计算机不能精确地解决大多数数学问题，只能近似地解决，因此优先考虑的是确保通过应用我们的算法获得的解是高度精确的，也就是说，接近问题的“真实”解。但我们在不牺牲准确性的前提下快速解决问题也是至关重要的；如果模拟需要我们调查大量不同的场景，或者如果我们寻求解决的问题只是整体更复杂计算中的一个组成部分，或者如果新数据实时到达，我们需要相应地调整模型，这一点尤其正确。在多核机器上开发既快速又准确的算法是一个关键的挑战。我们的目标是从几个不同的角度改进现有的算法，利用新的数学技术，如优化和偏微分方程的解。并行性将被设计到我们的新算法中，允许现代计算机硬件被利用。这些一般性的改进将与新技术的发展相结合，以利用来自重要应用领域的问题的特殊特征，包括x射线显微镜、晶体学和辐射转移建模。我们的新软件将通过国际知名的数学软件库HSL， GALAHAD和SPRAL提供。这些被英国和国外的科学和工程研究界以及一些商业公司广泛使用。自2010年以来，已有50多所英国大学的部门使用HSL进行广泛学科的教学或研究，包括计算化学、工程设计、流体动力学、组合优化和电路理论。

This project seeks to develop new algorithms, supporting theory and software for solving least squares problems that arise in science, engineering, planning and economics. Least squares involves finding an approximate solution of overdetermined or inexactly specified systems of equations. Real-life applications abound. Weather forecasters want to produce more accurate forecasts; climatologists want a better understanding of climate change; medics want to produce more accurate images in real time; financiers want to analyse and quantify the systematic risk of an investment by fitting a capital asset pricing model to observed financial data. Finding the 'best' solution commonly involves constructing a mathematical model to describe the problem and then fitting this model to observed data. Such models are usually complicated; models with millions of variables and restrictions are not uncommon, but neither are relatively small but fiendishly difficult ones. It is therefore imperative to implement the model on a computer and to use computer algorithms for solving it. The latter task is at the core of the proposed activities.Nearly all such large-scale problems exhibit an underlying mathematical structure such as sparsity. That is to say, the interactions between the parameters of a large system are often localised and do not involve any direct interaction between all the components. To solve the systems and models represented in this way efficiently involves developing algorithms that are able to exploit these underlying 'simpler' structures, which often reduces the scale of the problems, and thus speeds up their solution. This enterprise commonly leads not only to new software that implements existing methods, but to the creation of new theoretical and practical algorithms. At the other extreme, some problems involve interaction between all components, and while the underlying structure is less transparent, it is nonetheless present. In these cases, the computational burden may be very high and such problems may generally only be solved by sophisticated use of massively parallel computers.The methods we will develop will aim to solve the given problem efficiently and robustly. Since computers cannot solve most mathematical problems exactly, only approximately, a priority will be to ensure the solution obtained by applying our algorithms is highly accurate, that is, close to the 'true' solution of the problem. But it is also vital that we solve problems fast without sacrificing accuracy; this is particularly true if a simulation requires us to investigate a large number of different scenarios, or if the problem we seek to solve is simply a component in an overall vastly more complicated computation, or if new data arrives in real time and we need to adapt the model accordingly. Developing algorithms that are both fast and accurate on multicore machines presents a key challenge.We aim to improve upon existing algorithms from several different angles, exploiting new mathematical techniques from areas such as optimization and the solution of partial differential equations. Parallelism will be designed into our new algorithms, allowing modern computer hardware to be exploited. These generic improvements will be coupled with the development of new techniques to exploit special features of problems from important application areas, including X-ray microscopy, crystallography and radiative transfer modelling.Our new software will be made available through the internationally renowned mathematical software libraries HSL, GALAHAD and SPRAL. These are extensively used by the scientific and engineering research community in the UK and abroad, as well as by some commercial companies. Since 2010, more than 50 UK university departments have used HSL for teaching or research in a wide range of disciplines that includes computational chemistry, engineering design, fluid dynamics, portfolio optimization, and circuit theory.