Jieqiu Chen

A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

  • Samuel Burer
  • Jieqiu Chen
    • Categories 0-1 Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , ,

    Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

    Relaxing the Optimality Conditions of Box QP

  • Samuel Burer
  • Jieqiu Chen
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions. We compare these relaxations with a basic semidefinite relaxation due to Shor, particularly in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger. We … Read more