Applications of Weighted Least Squares

本项目涵盖了加权最小二乘问题的新算法的开发和分析及其应用。在许多实际应用中，权重会因很大的因素而变化，从而产生病态情况。在过去的十年中，几位作者独立地证明了这种情况下的病态权矩阵的范数界。在之前的工作中，PI在这个范数界的基础上发现了一个稳定的加权最小二乘算法。“稳定”是指算法的精度不受权矩阵病态的影响。范数界和稳定算法被证明有一些意想不到的应用。例如，发现了一种新的内点法，与以往的内点法不同，它的运行时间不依赖于目标函数的数值数据。此外，还发现了一种稳定求解一类有限元方法的方法，而以前已知的算法在这类方法上是失败的。在这个研究项目中，加权最小二乘问题将沿着以下几条线进行：(1)将开发加权最小二乘的迭代方法，以及改进的稀疏矩阵方法，(2)线性规划的结果将扩展到半定规划，(3)将发明用于电力网络中出现的高度非线性问题的新算法，这些问题的核心是广义加权最小二乘问题，(4)将解决逆有限元问题。该项目的成果将为科学和工程中出现的优化和模拟问题提供更准确、更有效的算法。

This project covers the development and analysis of new algorithms for weighted least-squares problems and their applications. In many practical applications, the weights vary by large factors, giving rise to ill-conditioned cases. In the past decade several authors independently proved a norm bound for this case of an ill-conditioned weight matrix. In previous work the PI followed up on this norm bound with the discovery of a stable algorithm for weighted least squares. ``Stable'' means that the accuracy of the algorithm is not affected by ill- conditioning of the weight matrix. The norm bound and the stable algorithm turn out to have several unexpected applications. For example, a new interior point method was discovered whose running time, unlike for all previous interior point methods, does not depend on the numerical data of the objective function. Also, a way was found to stably solve a class of finite element methods on which previously known algorithms would have failed. In this research project, weighted least-squares problems will be pursued along several lines: (1) iterative methods for weighted least squares will be developed, as well as improved sparse-matrix methods, (2) results for linear programming will be extended to semidefinite programming, (3) new algorithms will be invented for the highly nonlinear problems arising in electric power networks, which have at their core a generalized weighted least-squares problem, and (4) inverse finite element problems will be addressed. The outcome of this project will be more accurate and more efficient algorithms for optimization and simulation problems arising in science and engineering.