  


A tight iterationcomplexity upper bound for the MTY predictorcorrector algorithm via redundant KleeMinty cubes
Murat Mut(mhm309lehigh.edu) Abstract: It is an open question whether there is an interiorpoint algorithm for linear optimization problems with a lower iterationcomplexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the MizunoToddYe predictorcorrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant KleeMinty cube for which the aforementioned algorithm requires $n^{( \frac{1}{2}\epsilon )} $ iterations to reduce the barrier parameter by at least a constant. This is provably the first case of an adaptive step interiorpoint algorithm, where the classical iterationcomplexity upper bound is shown to be tight. Keywords: Curvature, Central path, Polytopes , Complexity, Interiorpoint methods, Linear optimization Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 08/14/2014 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  