Linear, Cone and Semidefinite Programming

A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming

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

    We develop a natural variant of Dikin’s affine-scaling method, first for semidefinite programming and then for hyperbolic programming in general. We match the best complexity bounds known for interior-point methods. All previous polynomial-time affine-scaling algorithms have been for conic optimization problems in which the underlying cone is symmetric. Hyperbolicity cones, however, need not be symmetric. … Read more

    Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

  • Tomonari Kitahara
  • Noriyoshi Sukegawa
    • Categories Linear Programming Tags , ,

    Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the … Read more

    Decomposition theorems for linear programs

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories Linear Programming, Network Optimization Tags , , , ,

    It is well known that any feasible arc-flow solution to a network problem defined on a graph $G = (N, A)$, where $N$ is the set of nodes whereas $A$ is the set of arcs, can be expressed using at most $|A| + |N|$ paths and cycles having nonzero flow, out of these, at most … Read more

    Tools for primal degenerate linear programs: IPS, DCA, and PE

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories Linear Programming Tags , , , , , ,

    This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the Improved Primal Simplex (IPS) algorithm which turns degeneracy into a possible advantage. The constraints of the original problem are dynamically partitioned based on the numerical values of the current basic variables. The idea is to work … Read more

    Efficient First-Order Methods for Linear Programming and Semidefinite Programming

  • James Renegar
    • Categories Linear Programming, Semi-definite Programming Tags , , ,

    We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally “smoothed,” thereby allowing most first-order … Read more

    A Gentle, Geometric Introduction to Copositive Optimization

  • Samuel Burer
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more

    Semidefinite Optimization Approaches to Applications in Facility Layout and Logistics

  • Philipp Hungerländer
    • Categories Facility Planning and Design, Semi-definite Programming, Transportation

    The main contributions of this thesis are the comparison of existing and the design of new exact approaches based on linear, quadratic and semidefinite relaxations for row layout problems and several applications in logistic. In particular we demonstrate that our suggested semidefinite approach is the strongest exact method to date for most row layout problems. … Read more