Izvorni znanstveni članak

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

Sažetak

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.

Ključne riječi

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

Hrčak ID:

133615

URI

https://hrcak.srce.hr/133615

Datum izdavanja:

30.12.2014.

Posjeta: 2.203 *