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.