Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Semidefinite approximations for quadratic programs over orthogonal matrices
    Povh, Janez, 1973-
    Finding global optimum of a non-convex quadratic function is in general a verydifficult task even when the feasible set is a polyhedron. We show that when the feasible set of a quadratic problem ... consists of orthogonal matrices from Rn*k, then we can transform it into a semidefinite program in matrices oforder kn which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial optimization, like the Graph partitioning problem (GPP), the Quadratic assignment problem (QAP) etc. In particular we show how to improve significantly the well-known Donath-Hoffman eigenvalue lower bound for GPP by semidefinite programming. In the last part of the paper we show that the copositive strengthening of the semidefinite lower bounds for GPP and QAP yields the exact values.
    Vir: Journal of global optimization. - ISSN 0925-5001 (Vol. 48, no. 3, nov. 2010, str. 447-463)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 1024132929

    Povezava(-e):

    http://dx.doi.org/10.1007/s10898-009-9499-7

vir: Journal of global optimization. - ISSN 0925-5001 (Vol. 48, no. 3, nov. 2010, str. 447-463)
loading ...
loading ...
loading ...

Vnos na polico