central path

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

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , ,

    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

    Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization

  • Roger Behling
  • Clóvis Caesar Gonzaga
  • Gabriel Haeser
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , ,

    We consider the minimization of a convex function on a compact polyhedron defined by linear equality constraints and nonnegative variables. We define the Levenberg-Marquardt (L-M) and central trajectories starting at the analytic center and using the same parameter, and show that they satisfy a primal-dual relationship, being close to each other for large values of … Read more

    The central curve in linear programming

  • Jesús A. De Loera
  • Bernd Sturmfels
  • Cynthia Vinzant
    • Categories Convex Optimization, Linear Programming, Nonlinear Optimization Tags , , , , , , , , , , ,

    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

    On the Volumetric Path

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , , ,

    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

    Central Swaths (A Generalization of the Central Path)

  • James Renegar
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We develop a natural generalization to the notion of the central path — a notion that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the “derivative cones” of a “hyperbolicity cone,” the derivatives being direct and mathematically-appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative … Read more

    A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more

    The continuous d-step conjecture for polytopes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , , ,

    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 Simpler and Tighter Redundant Klee-Minty Construction

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler … Read more

    Central path curvature and iteration-complexity for redundant Klee-Minty cubes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more

    Polytopes and Arrangements : Diameter and Curvature

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Polyhedra Tags , , ,

    We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature. Citation AdvOL-Report #2006/09 Advanced Optimization … Read more