Month: January 2011

Klee-Minty’s LP and Upper Bounds for Dantzig’s Simplex Method

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Linear Programming Tags , ,

    Kitahara and Mizuno (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the … Read more

    Target-following framework for symmetric cone programming

  • Chek Beng Chua
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    We extend the target map, together with the weighted barriers and the notions of weighted analytic centers, from linear programming to general convex conic programming. This extension is obtained from a novel geometrical perspective of the weighted barriers, that views a weighted barrier as a weighted sum of barriers for a strictly decreasing sequence of … Read more