chubanov’s method

An extension of Chubanov’s algorithm to symmetric cones

  • Tomonari Kitahara
  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takashi Tsuchiya
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an … Read more

    A Polynomial Column-wise Rescaling von Neumann Algorithm

  • Dan Li
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently Chubanov proposed a method which solves homogeneous linear equality systems with positive variables in polynomial time. Chubanov’s method can be considered as a column-wise rescaling procedure. We adapt Chubanov’s method to the von Neumann problem, and so we design a polynomial time column-wise rescaling von Neumann algorithm. This algorithm is the first variant of … Read more