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