From combinatorial optimization to real algebraic geometry and back

Autor:	Janez Povh
Jazyk:	angličtina
Rok vydání:	2014
Předmět:	combinatorial optimization copositive programming semidenite programming polynomial optimization sum of squares real algebraic geometry Applied mathematics. Quantitative methods T57-57.97
Zdroj:	Croatian Operational Research Review, Vol 5, Iss 2, Pp 105-117 (2014)
Druh dokumentu:	article
ISSN:	1848-0225 1848-9931
DOI:	10.17535/crorr.2014.0001
Popis:	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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/f3518c7452d045159712c31b87998f31 Zobrazit plný text záznamu View record in DOAJ