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）研究其有效的 在向量/并行/分布式计算环境中实现。