Studies on Affine Scaling Method

仿射标度方法是解决线性规划问题的一类重要的点算法，并且这些方法的收敛性和收敛速度理论已经有了一些重大发展。 特别是，当问题可能退化时，如果步长小于等于到边界距离的三分之二，则原始收敛到最优对偶面的内部，而对偶收敛到最优对偶面的解析中心。 此外，通过步骤选择策略，这些方法已被证明可以超线性收敛。更有效的变体也已被开发出来。 在这个项目下，正在研究这些方法的四个不同方面：1）研究它们的收敛特性、收敛速度和复杂性； 2）研究稳定的实现，以在计算机实现中实现更高的收敛率； 3）研究它们与卡尔曼滤波器的联系及其在解决随机线性规划问题中的应用； 4）研究它们在矢量/并行/分布式计算环境中的有效实现。

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.