Dissertation/Thesis Abstract

Copositive programming: Separation and relaxations
by Dong, Hongbo, Ph.D., The University of Iowa, 2011, 124; 3494023
Abstract (Summary)

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 (often a highly nontrivial task), this kind of question can be approached via a mathematical optimization problem. An optimal solution to a mathematical optimization problem, when interpreted properly, might correspond to new knowledge, effective methodology or good decisions in the 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 number 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 computationally 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 the 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 dimensions of 5 × 5 matrices. Then we show how a separation procedure for this low dimensional case can be extended to any symmetric matrix with a certain block structure.

Last but not least, we provide another approach to separation and relaxation 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.

Indexing (document details)
Advisor: Anstreicher, Kurt M., Burer, Samuel A.
Commitee: Jay, Laurent O., Krokhmal, Pavlo, Ohlmann, Jeffrey W.
School: The University of Iowa
Department: Applied Mathematical & Computational Sciences
School Location: United States -- Iowa
Source: DAI-B 73/05, Dissertation Abstracts International
Subjects: Applied Mathematics, Computer science
Keywords: Completely positive cone, Convex relaxation, Copositive programming, Separation
Publication Number: 3494023
ISBN: 9781267151919
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy