- The Complexity of Self-Regular Proximity Based Infeasible IPMs Maziar Salahi (salahimehr.sharif.edu) Tama's Terlaky (terlakymcmaster.ca) Guoqing Zhang (gzhanguwindsor.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/2003Entry Accepted: 05/23/2003Entry Last Modified: 05/23/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.