Juan S. Campos

Partial Lasserre relaxation for sparse Max-Cut

  • Juan S. Campos
  • Panos Parpas
  • Ruth Misener
    • Categories Semi-definite Programming Tags , , ,

    A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints … Read more

    A multilevel analysis of the Lasserre hierarchy

  • Juan S. Campos
  • Panos Parpas
  • Ruth Misener
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. … Read more