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.
|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|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be