Optimization Online


On the Accuracy of Uniform Polyhedral Approximations of the Copositive Cone

E. Alper Yildirim(yildirim***at***bilkent.edu.tr)

Abstract: We consider linear optimization problems over the cone of copositive matrices. Such conic optimization problems, called {\em 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.

Category 1: Linear, Cone and Semidefinite Programming

Citation: Technical Report, Bilkent University Department of Industrial Engineering

Download: [PDF]

Entry Submitted: 07/18/2009
Entry Accepted: 07/18/2009
Entry Last Modified: 07/18/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society