From combinatorial optimization to real algebraic geometry and back

Abstract

In this paper, we explain the relations between combinatorial optimization and real algebraic geometry with a special focus to the quadratic assignment problem. We demonstrate how to write a quadratic optimization problem over discrete feasible set as a linear optimization problem over the cone of completely positive matrices. The latter formulation enables a hierarchy of approximations which rely on results from polynomial optimization, a sub- eld of real algebraic geometry.

Keywords

• combinatorial optimization
• copositive programming
• semidenite programming
• polynomial optimization
• sum of squares
• real algebraic geometry