On approximations, complexity, and applications for copositive programming

Gijben, L., 2015, [S.l.]: [S.n.]. 125 p.

Research output: ThesisThesis fully internal (DIV)Academic

Copy link to clipboard


  • Title and contents

    Final publisher's version, 467 KB, PDF-document

  • Chapter 1

    Final publisher's version, 460 KB, PDF-document

  • Chapter 2

    Final publisher's version, 300 KB, PDF-document

  • Chapter 3

    Final publisher's version, 735 KB, PDF-document

  • Chapter 4

    Final publisher's version, 383 KB, PDF-document

  • Chapter 5

    Final publisher's version, 400 KB, PDF-document

  • Summary

    Final publisher's version, 211 KB, PDF-document

  • Samenvatting

    Final publisher's version, 212 KB, PDF-document

  • Bibliography

    Final publisher's version, 236 KB, PDF-document

  • Nomenclature

    Final publisher's version, 255 KB, PDF-document

  • Index

    Final publisher's version, 115 KB, PDF-document

  • Complete dissertation

    Final publisher's version, 1 MB, PDF-document

  • Propositions

    Final publisher's version, 34 KB, PDF-document

  • Luuk Gijben
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 fact decide isomorphism using finite levels of some approximation hierarchies of the copositive cone.
Translated title of the contributionBenaderingen, complexiteit, en toepassing voor copositief programmeren
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Dür, Mirjam, Supervisor
  • de Klerk, E. (Etienne), Assessment committee, External person
  • Rendl, F. (Franz), Assessment committee, External person
  • Trentelman, Hendrikus, Assessment committee
Award date23-Jan-2015
Place of Publication[S.l.]
Print ISBNs978-90-367-7527-4
Electronic ISBNs978-90-367-7526-7
Publication statusPublished - 2015

View graph of relations

Download statistics

No data available

ID: 15131647