AbstractsBiology & Animal Science

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.; In this thesis we investigate a number of properties with regards to the copositive and completely positive cone, which are each others dual cone, motivated by results within copositive optimization. We first study the complexity of the membership problem for both cones. We confirm the expected result that the membership problem for the completely positive cone is NP-hard. Moreover, we show that both the weak and the strong membership problem for the copositive as well as the completely positive cone belong to the class NP-hard. We then investigate the property of irreducibility with regards to the cone of nonnegative matrices, a weaker version of extremality. We show that every 5x5 copositive matrix which is not the sum of a nonnegative and a positive semidefinite matrix can be expressed as the sum of a nonnegative and a single irreducible matrix. This result is then used to show that the copositive cone reduces to the level one Parrilo cone under specific scalings. We furthermore prove that we can scale any matrix, that is not the sum of a nonnegative and a positive semidefinite matrix, out of any level r Parrilo cone for r>0 and n>4. We subsequently introduce and investigate the concept of non-decreasing scalings. Finally, we provide an application in the form of a copositive formulation of the graph isomorphism problem and show that we can in…