On approximations, complexity, and applications for copositive programming

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.