Original scientific paper
https://doi.org/10.17535/crorr.2014.0001
From combinatorial optimization to real algebraic geometry and back
Janez Povh
; Faculty of Information Studies Novo Mesto
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
Hrčak ID:
133615
URI
Publication date:
30.12.2014.
Visits: 2.150 *