curvature – 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

Curvature Integrals and Iteration Complexities in SDP and Symmetric Cone Programs

Published: 2011/09/30

Satoshi Kakihara

Atsumi Ohara

Takashi Tsuchiya

Linear, Cone and Semidefinite Programming curvature, interior point methods, iteration complexities, path-following methods, primal-dual algorithms, semidefinite programming, symmetric cones

In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. The idea to exploit the curvature of the central path for the analysis of iteration … Read more

The central curve in linear programming

Published: 2010/12/17

Jesús A. De Loera

Bernd Sturmfels

Cynthia Vinzant

Convex Optimization, Linear Programming, Nonlinear Optimization central path, curvature, degree, gauss map, groebner basis, hyperbolic polynomial, hyperplane arrangement, interior point methods, linear programming, matroid, projective variety, tutte polynomial

The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more

The continuous d-step conjecture for polytopes

Published: 2007/09/28

Antoine Deza

Tamás Terlaky

Yuriy Zinchenko

Linear, Cone and Semidefinite Programming, Polyhedra central path, curvature, d-step conjecture, diameter, hirsch conjecture, polytope

The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more

A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

Published: 2005/09/30

Renato D.C. Monteiro

Takashi Tsuchiya

Linear Programming, Linear, Cone and Semidefinite Programming affine-scaling, central path, condition number, crossover events, curvature, interior point methods, layered least squares steps, linear programming, path following, polynomial complexity, predictor-corrector, primal-dual algorithms, scale-invariance, strongly polynomial

The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more