Local Convergence Properties of New Methods in Linear Programming

概要

論文の詳細を見る
Asymptotic behavior of some of the interior point methods for Linear Programming is investigated without assuming nondegeneracy of constraints. A detailed analysis is given to the fundamental pair of vectors, the Newton direction leading to the center of the problem "d_C" and the direction of the affine-scaling method "d_<AF>". The quadratic convergence property of the iteration by - d_C is demonstrated. Step-sizes for the direction - d_C are also given to maintain feasibility without sacrificing the quadratic convergence. The sequence generated by - d_<AF> is pulled towards the central trajectory while. it converges linearly to the optimal solution. Local convergence properties of Iri and Imai's Multiplicative Barrier Function method and Yamashita's method (a variation of the projective scaling methods) are also discussed. It is shown that the search direction of the method by Iri and Imai converges to - d_C, whereas the direction by Yamashita converges to d_<AF>. A proof is given for the quadratic convergence property of Iri and Imai's method with an exact line search procedure in the case where constraint is degenerate.
社団法人日本オペレーションズ・リサーチ学会の論文