VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
• Approximating non-convex quadratic programs by semidefinite and copositive programming
Povh, Janez, 1973- ; Rendl, Franz
Finding an optimum of a non-convex quadratic function is in general a very difficult task even if the feasible set is a polyhedron. We show that when the feasible set of a quadratic problem consists ... of matrices from ${\mathbb{R}}^{n \times k}}$ which have orthogonal columns, then we can transform the quadratic problem into a semidefinite program in matrices of order $kn$, which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial optimization, like the quadratic assignment problem (QAP) and the graph partitioning problem (GP). In particular we show how to improve significantly the well-known Hoffman-Wielandt eigenvalue lower bound for QAP and the Donath- Hoffman eigenvalue lower bound for GP by semidefinite programming. Finally we show how to rewrite some problems from combinatorial optimization as linear programs over the cone of completely positive matrices.
Vir: KOI 2006 : proceedings (Str. 35-45)
Vrsta gradiva - prispevek na konferenci
Leto - 2008
Jezik - angleški
COBISS.SI-ID - 14785625
vir: KOI 2006 : proceedings (Str. 35-45)