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 )
Entry Submitted: 06/27/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|