On the accuracy of uniform polyhedral approximations of the copositive cone

E Alper Yıldırım - Optimization methods and software, 2012 - Taylor & Francis
Optimization methods and software, 2012Taylor & Francis
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 …
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.
Taylor & Francis Online
以上显示的是最相近的搜索结果。 查看全部搜索结果