On strong duality in linear semidefinite and copositive programming

Abstract

Copositive programming deals with optimization over the convex cone of so-called copositive matrices (i.e. matrices which are positive semi-defined on the non-negative orthant). Copositive problems form a special class of conic optimization problems and have many important applications, including NP -hard problems. Given a linear copositive prog-ramming problem, we derive for it a new extended dual problem which satisfies the strong duality relations and does not require any additional regularity assumptions.The extended dual problem is based on the recently introduced concept of the set of normalized immobile indices, but neither the immobile indices themselves nor the information about the vertices of the convex hull of these indices is explicitly used. The obtained strong duality formulations for linear copositive problems have similar structure and properties as that proposed in the works by M. Ramana, L. Tuncel, and H. Wolkowicz, for semide_nite programming.