Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

Immanuel M. Bomze

Date and Time: 

Wednesday, September 25, 2013 - 4:00pm

For all-quadratic problems (without any linear constraints), it is well known that the semidefinite relaxation coincides basically with the Lagrangian dual problem. Here we study a more general case where the constraints can be either quadratic or linear. To be more precise, we include explicit sign constraints on the problem variables, and study both the full Lagrangian dual as well as the Semi-Lagrangian
relaxation. We show that the stronger Semi-Lagrangian dual bounds coincide with the ones resulting from copositive relaxation. This way, we arrive at a full hierarchy of tractable conic bounds stronger than the usual Lagrangian dual (and thus than the SDP) bounds. We also specify sucient conditions for tightness of the Semi-Lagrangian (i.e. copositive) relaxation and show that copositivity of the slack
matrix guarantees global optimality for KKT points of this problem.

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 scientific 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 scientific 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 scientific 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.