Studies on Affine Scaling Method

仿射标度法的研究

• 批准号: 9321550
• 负责人: Romesh Saigal
• 金额: $ 17.85万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-01-15 至 1998-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9321550&HistoricalAwards=false
• 关键词: Studies; Affine; Scaling; Method

Affine scaling methods form an important class of point algorithms for solving a linear programming problem, and there have been some major developments in the convergence and convergence rate theory of these methods. In particular, when the problem may be degenerate, if the step size is less than equal to two thirds of the distance to the boundary, the primal converges to the interior of the optimal face, while the dual to the analytic center of the optimal dual face. Also, by a step selection strategy, these methods have been shown to converge superlinearly. More efficient variants have also been developed. Under this project, four different aspects of these methods are being studied: 1) study of their convergence properties, convergence rates and complexity; 2) study of stable implementations to achieve these higher rates of convergence in computer implementations; 3) study of their connection to Kalman filter and their application to solving stochastic linear programming problems; and, 4) study of their efficient implementations in vector/parallel/distributed computing environments.

仿射缩放方法构成了解决线性编程问题的重要点算法类别，并且这些方法的收敛性和收敛速率理论有一些重大发展。 特别是，当问题可能退化时，如果步长小于到边界距离的三分之二的三分之二，则原始层会收敛到最佳面的内部，而双重偶到最佳双面的分析中心。 同样，通过步骤选择策略，这些方法已被证明可以融合超线性。还开发了更有效的变体。 在该项目下，正在研究这些方法的四个不同方面：1）研究其收敛性能，收敛速率和复杂性； 2）研究稳定实施，以实现计算机实施中这些较高的收敛速度； 3）研究他们与卡尔曼过滤器的联系及其在解决随机线性编程问题上的应用； 4）研究其在向量/并行/分布式计算环境中的有效实现。