EAGER: Optimization without Round-off Errors

EAGER：无舍入误差的优化

• 批准号: 1252456
• 负责人: Erick Moreno-Centeno
• 金额: $ 12万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-15 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1252456&HistoricalAwards=false
• 关键词: EAGER; Optimization; without; Round; off

This Early-concept Grant for Exploratory Research (EAGER) provides funding to further develop an algorithm to solve systems of linear equations with a specific advantage over Gaussian Elimination in that the algorithm does not have round-off errors. The algorithm will be tailored and adapted to be used within existing optimization algorithms. The key property of the algorithm being further developed is that it maintains the integrality of the numbers throughout its execution. In particular, although the algorithm does contain divisions (which is crucial for the polynomial-time complexity of thealgorithm) all the divisions have a remainder of zero. A detailed complexity analysis of the algorithm will be performed; specifically, both its running time and the number of bits required to represent the numbers throughout the algorithm's execution will be investigated. A modification of the algorithm to perform LU factorizations will also be studied. Finally, the algorithm will be adapted to enable its use for the basis updates performed in state-of-the-art implementations of the revised simplex method.If successful, the outcomes of this research will lead to a deeper understanding of computational linear algebra free of round-off errors and the associated applications within optimization algorithms. In the linear programming (LP) context, this research will enable us to solve large-scale LPs exactly; this, in turn, will significantly improve the accuracy and speed of integer programming solvers. In addition, since solving systems of linear equations is a critical subroutine of many numerical algorithms, this research will impact many application areas where linear systems frequently arise, including economics, physics, chemistry, and engineering.

这个早期概念的探索性研究补助金（EAGER）提供资金，以进一步开发一种算法来解决线性方程组，该算法比高斯消元法具有特定的优势，因为该算法没有舍入误差。该算法将被定制和调整，以在现有的优化算法中使用。正在进一步开发的算法的关键属性是它在整个执行过程中保持数字的完整性。特别是，尽管算法确实包含除法（这对算法的多项式时间复杂度至关重要），但所有除法的余数都为零。一个详细的复杂性分析的算法将进行具体的，它的运行时间和所需的位数来表示整个算法的执行将进行调查。也将研究修改的算法进行LU分解。最后，该算法将进行调整，使其用于基础更新的国家的最先进的实现的修订simplex方法。如果成功的话，这项研究的成果将导致更深入地了解计算线性代数的舍入误差和相关的应用程序内的优化算法。在线性规划（LP）的背景下，这项研究将使我们能够解决大规模的LP准确，这反过来，将显着提高整数规划求解器的精度和速度。此外，由于求解线性方程组是许多数值算法的关键子程序，因此这项研究将影响线性系统经常出现的许多应用领域，包括经济学，物理学，化学和工程学。