A nasty cone with nice properties - new issues in Copositive Optimization

Immanuel M. Bomze

Date and Time: 

Monday, November 19, 2012 - 2:00pm

Event Location: 

Mohler Lab Room 451

A symmetric matrix is called copositive, if it generates a quadratic form taking no negative values over the positive orthant. Contrasting to positive-semideniteness, checking copositivity is NP-hard. In a copositive optimization problem, we have to minimize a linear function of a symmetric matrix over the copositive cone subject to linear constraints. This convex program has no non-global local solutions. On the other hand, there are several hard non-convex programs which can be formulated as copositive programs, among them mixed-binary QPs or Standard QPs. Applications range from machine learning, optimization under uncertainty, to several combinatorial optimization problems, including the maximum-clique problem or the maximum-cut problem.

The dual conic program, unlike the more popular SDP case, involves a different matrix cone, that of completely positive matrices (those which allow for a symmetric, possibly rectangular factorization with no negative entries). This conic optimization technique shifts complexity from global optimization towards sheer feasibility questions. Therefore it is of central importance to devise positive and negative certifcates of copositivity and/or complete positivity.

Bio Sketch: 

Immanuel M. Bomze was born in Vienna, Austria, in 1958. He received the degree Magister rerum naturalium in Mathematics at the University of Vienna in 1981. After a postgraduate scholarship at the Institute for Advanced Studies, Vienna from 1981 to 1982, he received the degree Doctor rerum naturalium in Mathematics at the University of Vienna. He held several visiting research positions at the International Institute for Applied Systems Analysis, Laxenburg, Austria, at the Institute for Advanced Studies, Vienna, at the Department of Economics, University of Melbourne, Australia, and at the Department of Mathematics, Wilfrid Laurier University,Waterloo, ON, Canada. Since 2004, he holds a chair (full professor) of Applied Mathematics and Statistics at the University of Vienna. His research interests are in the areas of nonlinear optimization, qualitative theory of dynamical systems, game theory, mathematical modeling and statistics, where he has edited one and published four books, as well as over 80 peer-reviewed articles in scientic journals and monographs. The list of his coauthors comprises almost sixty scientists from a dozen countries in four continents.

As a member of program and/or organizing committees, he co-organized various scientifc events and he is an Associate Editor for ve international journals. For several Science Foundations and Councils (based in Germany, Great Britain, Israel, Italy, the Netherlands, Portugal, Spain, USA), and for almost 50 scientifc journals he acted as a reporting referee. Currently he serves as an Editor of the European Journal of Operational Research, one of the worldwide leading journals in the field.