Optimization Online


The Complexity of Self-Regular Proximity Based Infeasible IPMs

Maziar Salahi (salahi***at***mehr.sharif.edu)
Tama's Terlaky (terlaky***at***mcmaster.ca)
Guoqing Zhang (gzhang***at***uwindsor.ca)

Abstract: Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting perties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to define infeasible neighborhoods. These simple but interesting properties of the proximity function indicate that, when the current iterate is in a large neighborhood of the central path, large-update IIPMs emerge as the only natural choice. Then, we apply these results to design a specific self-regularity based dynamic large-update IIPM in large neighborhood. The new dynamic IIPM always takes large-updates and does not utilize any inner iteration to get centered. An $O(n^{2}\log{\frac{n}{\epsilon}})$ worst-case iteration bound of the algorithm is established. Finally, we report the main results of our computational experiments.

Keywords: Linear Optimization, Infeasible Interior Point Method, Self-Regular Proximity Function, Polynomial Complexity.

Category 1: Linear, Cone and Semidefinite Programming

Citation: Report#2003/3-Advanced Optimization Lab. Department of computing and software-Mcmaster University

Download: [Postscript][PDF]

Entry Submitted: 05/23/2003
Entry Accepted: 05/23/2003
Entry Last Modified: 05/23/2003

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