Bundfuss, Stefan:
ISBN 9783899598636

Copositive Matrices, Copositive Programming, and Applications # Pb., 156 S., 8 Abb., davon 4 in Farbe, 3 Tabellen

SCHLAGWORTE:
kontinuierliche Optimierung
continuus optimization
Approximationsalgorithmen
approximation algorithma
copositiver Kegel
copositive cone
copositive Matrix
kombinatorische Optimierung
combinatorial optimization
quadratische Optimierung
quadratic programming

Viele schwierige Optimierungsprobleme - sowohl kontiniuierliche als auch ganzzahlige - können als copositives Programm formuliert werden, das heißt als lineares Programm über dem Kegel der copositiven Matrizen. Beispiele sind das Max-Clique-Problem, Graph-Partitioning Probleme, das Quadratic-Assignement-Problem, das Standard Quadratische Problem, nicht konvexe quadratische Probleme und einige fraktionale Probleme. Folglich ist das Lösen copositiver Programme NP-schwer und sogar das Entscheidungsproblem, ob eine Matrix nicht copositiv ist, ist NP-vollständig.
Das Buch stellt die wichtigsten Eigenschaften von copositiven Matrizen vor, gibt einen umfassenden Überblick über die Optimierungsprobleme, die sich als kopositives Programm formulieren lassen, und stellt die bisher bekannten Algorithmen zum Testen, ob eine Matrix copositiv ist, und zum Lösen von copositiven Programmen vor.


Many hard optimization problems can be formulated as copositive programs, i.e., linear programs over the cone of copositive matrices. Examples are the max-clique problem, graph partitioning problems, the quadratic assignment problem, the standard quadratic problem, non convex quadratic problems, and certain fractional problems. Therefore solving copositive programs is NP-hard and even to decide whether a matrix is not copositive is a NP-complete problem.
The book presents the most important facts about copositive matrices, gives an overview of optimization problems which can be formulated as copositive program, and states algorithms to test whether a matrix is copositive and to solve copositive programs approximately.

	^