×

Power series variants of Karmarkar-type algorithms. (English) Zbl 0682.90060

Summary: Many interior-point linear programming algorithms have been proposed since the Karmarkar algorithm for linear programming problems appeared in 1984. These algorithms follow tangent (first-order) approximations to families of continuous trajectories that underlie such algorithms. This paper describes power-series variants of such algorithms that follow higher-order, truncated, power-series approximations to such trajectories. The choice of the power-series parameter is important to the performance of such algorithms, and this paper describes an apparently good choice of parameter. We describe two power-series algorithms; one builds on the dual-affine scaling algorithm and the other on a primal-dual path-following algorithm. Empirical results indicate that, compared to first-order methods, these higher-order power-series algorithms accelerate convergence by reducing the number of iterations. Both of these power-series algorithms have been successfully implemented in the AT&T KORBX system.

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI