Akademska digitalna zbirka SLovenije - logo
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

    Povezava(-e):

    http://oliver.efpu.hr/koi06/koi06_proceedings.pdf

Vnos na polico