Superlinear convergence of the affine scaling algorithm |
| |
Authors: | T Tsuchiya R D C Monteiro |
| |
Institution: | (1) The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, 106 Tokyo, Japan;(2) School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332 Atlanta, GA, USA |
| |
Abstract: | In this paper we show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly
convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates
is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that 2/3 is
a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the
optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend
on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical
explanation for why 2/3 is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates.
The work of this author was based on research supported by the Overseas Research Scholars of the Ministry of Education, Science
and Culture of Japan, 1992.
The work of this author was based on research supported by the National Science Foundation (NSF) under grant DDM-9109404 and
the Office of Naval Research (ONR) under grant N00014-93-1-0234. This work was done while the second author was a faculty
member of the Systems and Industrial Engineering Department at the University of Arizona. |
| |
Keywords: | Interior point algorithms Affine scaling algorithm Linear programming Superlinear convergence Global convergence |
本文献已被 SpringerLink 等数据库收录! |
|