Murat Mut – Optimization Online

A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes

Published: 2014/08/14

Linear Programming central path, complexity, curvature, interior point methods, linear programming, polytope

It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity 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 Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant … Read more

An analogue of the Klee-Walkup result for Sonnevend’s curvature of the central path

Published: 2013/04/10

Murat Mut

Tamás Terlaky

Linear Programming

For linear optimization (LO) problems, we consider a curvature integral ﬁrst introduced by Sonnevend et al. (1991). Our main result states that in order to establish an upper bound for the total Sonnevend curvature of the central path, it is sufficient to consider only the case when n = 2m. This also implies that the … Read more

On the Volumetric Path

Published: 2010/10/28

Murat Mut

Tamás Terlaky

Linear Programming analytic center, central path, interior point methods, logarithmic barrier function, volumetric barrier function, volumetric center, volumetric path

We consider the logarithmic and the volumetric barrier functions used in interior point methods. In the case of the logarithmic barrier function, the analytic center of a level set is the point at which the central path intersects that level set. We prove that this also holds for the volumetric path. For the central path, … Read more