Comparative analysis of affine scaling algorithms based on simplifying assumptions

The paper analyzes several affine potential reduction algorithms for linear programming based on simplifying assumptions. It shows that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be with high probability, compared to the guaranteed . ( is a parameter in the potential function and n is the number of variables.) Under the same assumption, the paper further>a1.25<shows that the objective reduction rate of Dikin's affine scaling algorithm is with high probability, compared to no guaranteed convergence rate.