Quadratic convergence of potential-reduction methods for degenerate problems |
| |
Authors: | Reha H Tütüncü |
| |
Institution: | (1) Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA, e-mail: reha+@andrew.cmu.edu, US |
| |
Abstract: | Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the
Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial
time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even
for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This
is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point
algorithms that do not follow the central path.
Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001 |
| |
Keywords: | Mathematics Subject Classification (1991): 90C05 |
本文献已被 SpringerLink 等数据库收录! |
|