  


New Complexity Analysis of IIPMs for Linear Optimization Based on a Specific SelfRegular Function
Maziar Salahi (salahimmcmaster.ca) Abstract: Primaldual InteriorPoint Methods (IPMs) have shown their ability in solving large classes of optimization problems efficiently. Feasible IPMs require a strictly feasible starting point to generate the iterates that converge to an optimal solution. The selfdual embedding model provides an elegant solution to this problem with the cost of slightly increasing the size of the problem. On the other hand, Infeasible Interior Point Methods (IIPMs) can be initiated by any positive vector, and thus are popular in IPM softwares. In this paper we propose an adaptive largeupdate IIPM based on a specific selfregular proximity function, with barrier degree $1+\log n,$ that operates in the infinity neighborhood of the central path. An $O\left(n^\frac{3}{2} \log n \log\frac{n}{\epsilon}\right)$ worstcase iteration bound of our new algorithm is established. This iteration bound improves the so far best $O\left(n^2 \log{\frac{n}{\epsilon}}\right)$ iterations bound of IIPMs in a large neighborhood of the central path. Keywords: Linear Optimization, Infeasible Interior Point Methods, SelfRegular Functions, Adaptive Large Update, Polynomial Complexity Category 1: Linear, Cone and Semidefinite Programming Citation: Advaced Optimization lab Report, McMaster University, June 2005 Download: [PDF] Entry Submitted: 06/21/2005 Modify/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  