Minghui Liu

Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    We describe simple and exact duals, and certificates of infeasibility and weak infeasibility in conic linear programming which do not rely on any constraint qualification, and retain most of the simplicity of the Lagrange dual. In particular, some of our infeasibility certificates generalize the row echelon form of a linear system of equations, and the … Read more

    Exact duality in semidefinite programming based on elementary reformulations

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming

    In semidefinite programming (SDP), unlike in linear programming, Farkas’ lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system … Read more