izpis_h1_title_alt

Semidefinite approximations for quadratic programs over orthogonal matrices
Povh, Janez (Avtor)

URLURL - Predstavitvena datoteka, za dostop obiščite http://dx.doi.org/10.1007/s10898-009-9499-7 Povezava se odpre v novem oknu

Izvleček
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.

Jezik:Angleški jezik
Ključne besede:quadric programming, semidefinite programming, copositive programming, eigenvalue bound, quadratic assignment problem, graph partitioning problem
Vrsta gradiva:Delo ni kategorizirano (r6)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:NTF - Naravoslovnotehniška fakulteta
Leto izida:2010
Št. strani:str. 447-463
Številčenje:Vol. 48, no. 3
UDK:519.8
ISSN pri članku:0925-5001
COBISS.SI-ID:1024132929 Povezava se odpre v novem oknu
Število ogledov:553
Število prenosov:235
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Gradivo je del revije

Naslov:Journal of global optimization
Skrajšan naslov:J. glob. optim.
Založnik:Kluwer Academic Publishers
ISSN:0925-5001
COBISS.SI-ID:2822695 Povezava se odpre v novem oknu

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj