On approximations, complexity, and applications for copositive programming

Onderzoek naar copositieve matrices

Luuk Gijben deed onderzoek naar copositieve matrices, een wiskundig onderwerp dat van belang is voor toepassingen in economisch onderzoek, operations research en statistiek. Hij onderzocht een aantal eigenschappen met betrekking tot de copositieve en compleet positieve kegel (een verzameling matrices), die 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 behoort tot de klasse NP-moeilijk.

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-semi-definiete 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.

Ten slotte verstrekken we een toepassing in de vorm van een copositieve formulering van het graaf isomorphismeprobleem 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.

Luuk Gijben verrichtte zijn onderzoek binnen de afdeling Systems, Control and Applied Analysis van het Johan Bernoulli Instituut, faculteit Wiskunde en Natuurwetenschappen. Het werd gefinancierd door NWO.

Proefschrift: http://irs.ub.rug.nl/ppn/387120807