《《1998 Primal-dual affine scaling interior point methods for linear complementarity problems》.pdf

PRIMAL-DUAL AFFINE SCALING INTERIOR POINT METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS ∗ FLORIAN A. POTRA † Abstract. A first order affine scaling method and two mth order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has O(nL2 (log nL2 )(log log nL2 )) iteration complexity. If the LCP admits a strict complementary solu- tion then both the duality gap and the iteration sequence converge superlinearly with Q-order two. If m = Ω(log(√nL)), then both higher order methods have O(√n)L iteration complexity. The Q-order of convergence of one of the methods is (m + 1) for problems that admit a strict complementarity solution while the Q-order of convergence of the other method is (m + 1)/2 for general monotone LCPs. Key words. linear complementarity, interior-point, affine scaling, large neighborhood, super- linear convergence AMS subject classifications. 90C51, 65K05, 49M15, 90C05, 90C20 1. Introduction. The primal-dual affine scaling direction plays a special role in the theory and practice of interior point methods. It turns out that the search direction used by most primal-dual interior point methods is a convex combination (1 − γ )w + γw of the primal-dual affine scaling method w and the centering direction w (see the monographs [35, 48, 49]). Optimality is improved along the affine scaling direction, while centrality is improved on the centering direction. The first interior point method of this type was proposed, in the context of linear programming (LP), by Kojima, Mizuno and Yoshise [15]. They proved that the algorithm had O(nL) iteration complexity, the