Achievable Potential Reductions in the Method of Kojima et al. in the Case of Linear Programming.

摘要

Kojima et al. proposed a primal-dual interior point method, based on potential reduction, for solving the linear complementarity problem, and they derived an O((square root of n)L) iteration bound. In the derivation of the bound they used equal step sizes in the primal and the dual space, and they showed that taking the step size equal to 0.4 the potential reduction is at least 0.2. In the paper the authors specialize to the case of linear programming and they show that the latter constant can be improved to 0.267. Further, admitting different step sizes in both spaces, the authors show that a further improvement of the constant to 0.345 is possible. Furthermore, for the case of equal step sizes it is shown that the duality gap is monotonically decreasing. (Copyright (c) 1991 by Faculty of Technical Mathematics and Informatics, The Netherlands.)