On approximations, complexity, and applications for copositive programming

Vertaalde titel van de bijdrage: Benaderingen, complexiteit, en toepassing voor copositief programmeren

Luuk Gijben

Onderzoeksoutput

2446 Downloads (Pure)

Samenvatting

In deze thesis onderzoeken wij een aantal eigenschappen met betrekking tot de copositieve en compleet positieve kegel, welke elkaars duale kegel zijn, gemotiveerd door resultaten binnen de copositieve optimalisatie. We bestudeerden als eerste de complexiteit van het lidmaatschap probleem van de beide kegels. We bevestigen het verwachte resultaat dat het lidmaatschap probleem van de compleet positieve kegel NP-moeilijk is. Sterker, we laten zien dat zowel het zwakke als het sterke lidmaatschap probleem voor zowel de copositieve alsmede de compleet positieve kegel tot de klasse NP-moeilijk behoort. We onderzoeken tevens de eigenschap van onverkleinbaarheid met betrekking tot de kegel van niet-negatieve matrices, zijnde een zwakkere versie van extremaliteit. We laten zien dat elke 5x5 copositieve matrix die niet de som is van een niet-negatieve en een positief-semidefiniete matrix kan worden geschreven als de som van een niet-negatieve matrix en een enkele onverkleinbare matrix. Dit resultaat gebruiken we vervolgens om te laten zien dat de copositieve kegel kan worden gereduceerd tot de niveau één Parrilo kegel met behulp van schalingen. We bewijzen verder dat we elke matrix, welke niet de som van een niet-negatieve en een positief-semidefiniete matrix is, uit elke willekeurige niveau r Parrilo kegel kunnen schalen voor r>0 en n>4. Daarnaast introduceren en onderzoeken we het begrip niet-negatieve schalingen. Tenslotte verstrekken we een toepassing in de vorm van een copositieve formulering van het graaf isomorphisme probleem en laten we zien dat we isomorphisme kunnen vaststellen met behulp van een eindig niveau van enkele benadering hiërarchieën voor de copositieve kegel.
Vertaalde titel van de bijdrageBenaderingen, complexiteit, en toepassing voor copositief programmeren
Originele taal-2English
KwalificatieDoctor of Philosophy
Toekennende instantie
  • Rijksuniversiteit Groningen
Begeleider(s)/adviseur
  • Dür, Mirjam, Supervisor
Datum van toekenning23-jan.-2015
Plaats van publicatie[S.l.]
Uitgever
Gedrukte ISBN's978-90-367-7527-4
Elektronische ISBN's978-90-367-7526-7
StatusPublished - 2015

Citeer dit