Optimization Online


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

Y.B. ZHAO (ybzhao***at***amss.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society