On the accuracy of uniform polyhedral approximations of the copositive cone

E. Alper Yildirim*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)155-173
Number of pages19
JournalOptimization Methods and Software
Volume27
Issue number1
DOIs
Publication statusPublished - 1 Feb 2012

Keywords

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

Fingerprint

Dive into the research topics of 'On the accuracy of uniform polyhedral approximations of the copositive cone'. Together they form a unique fingerprint.

Cite this