On the accuracy of uniform polyhedral approximations of the copositive cone

Abstract

We consider linear optimization problems over the cone of copositive matrices. Such conic optimization problems, called copositive programs, arise from the reformulation of a wide variety of difficult optimization problems. We propose a hierarchy of increasingly better outer polyhedral approximations to the copositive cone. We establish that the sequence of approximations is exact in the limit. By combining our outer polyhedral approximations with the inner polyhedral approximations due to de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp. 875–892], we obtain a sequence of increasingly sharper lower and upper bounds on the optimal value of a copositive program. Under primal and dual regularity assumptions, we establish that both sequences converge to the optimal value. For standard quadratic optimization problems, we derive tight bounds on the gap between the upper and lower bounds. We provide closed-form expressions of the bounds for the maximum stable set problem. Our computational results shed light on the quality of the bounds on randomly generated instances.

Keywords:

• copositive cone
• completely positive cone
• standard quadratic optimization
• maximum stable set

AMS Subject Classifications :

• 90C25
• 90C05
• 90C20
• 15A48
• 05C69

Acknowledgements

The author gratefully acknowledges the valuable comments from his colleagues and two anonymous referees on an earlier version of this manuscript. The author was supported in part by TÜBİTAK (Turkish Scientific and Technological Research Council) Grant 109M149.

Additional information

Notes on contributors

E. Alper Yıldırım

The author is now affiliated with the Department of Industrial Engineering, Koc University, 34450 Sarıyer, Istanbul, Turkey.