Copositive programming: separation and relaxations

A large portion of research in science and engineering, as well as in business, concerns one similar problem: how to make things "better”? Once properly modeled (although usually a highly nontrivial task), this kind of questions can be approached via a mathematical optimization problem. Optimal solution to a mathematical optimization problem, when interpreted properly, might corresponds to new knowledge, effective methodology or good decisions in corresponding application area. As already proved in many success stories, research in mathematical optimization has a significant impact on numerous aspects of human life. Recently, it was discovered that a large amount of difficult optimization problems can be formulated as copositive programming problems. Famous examples include a large class of quadratic optimization problems as well as many classical combinatorial optimization problems. For some more general optimization problems, copositive programming provides a way to construct tight convex relaxations. Because of this generality, new knowledge of copositive programs has the potential of being uniformly applied to these cases. While it is provably difficult to design efficient algorithms for general copositive programs, we study copositive programming from two standard aspects, its relaxations and its separation problem.

With regard to constructing computational tractable convex relaxations for copositive programs, we develop direct constructions of two tensor relaxation hierarchies for the completely positive cone, which is a fundamental geometric object in copositive programming. We show connection of our relaxation hierarchies with known hierarchies. Then we consider the application of these tensor relaxations to the maximum stable set problem. With regard to the separation problem for copositive programming. We first prove some new results in low dimension of 5 x 5 matrices. Then we show how a separation procedure for this low dimensional case can be extended to any symmetric matrices with a certain block structure. Last but not least, we provide another approach to the separation and relaxations for the (generalized) completely positive cone. We prove some generic results, and discuss applications to the completely positive case and another case related to box-constrained quadratic programming. Finally, we conclude the thesis with remarks on some interesting open questions in the field of copositive programming.