Applications of Weighted Least Squares

加权最小二乘法的应用

• 批准号: 9619489
• 负责人: Stephen Vavasis
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9619489&HistoricalAwards=false
• 关键词: Applications; Weighted; Least; Squares

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.

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