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.