M. Kojima et al., THEORETICAL CONVERGENCE OF LARGE-STEP PRIMAL DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING, Mathematical programming, 59(1), 1993, pp. 1-21
Citations number
35
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Applications & Cybernetics
This paper proposes two sets of rules, Rule G and Rule P, for controll
ing step lengths in a generic primal-dual interior point method for so
lving the linear programming problem in standard form and its dual. Th
eoretically, Rule G ensures the global convergence, while Rule P, whic
h is a special case of Rule G, ensures the O(nL) iteration polynomial-
time computational complexity. Both rules depend only on the lengths o
f the steps from the current iterates in the primal and dual spaces to
the respective boundaries of the primal and dual feasible regions. Th
ey rely neither on neighborhoods of the central trajectory nor on pote
ntial function. These rules allow large steps without performing any l
ine search. Rule G is especially flexible enough for implementation in
practically efficient primal-dual interior point algorithms.