Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

Y.B. ZHAO (ybzhaoamss.ac.cn)

Abstract: It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far best known iteration complexity and superlinear (or quadratic) convergence of the original interior-point algorithms. The idea of our methods is to use the global minimizers of proximity measure functions.

Keywords: Linear programming, interior-point algorithms, iteration complexity, neighborhoods.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation:

Download: [PDF]

Entry Submitted: 06/27/2005
Entry Accepted: 06/27/2005
Entry Last Modified: 06/27/2005

Modify/Update this entry