A problem-dependent inner approximation of the completely positive cone
Description:
Motivated by the expressive power of completely positive programming and its dual, copositive programming, to encode hard optimization problems, many approximation schemes for the completely positive and copositive cones have been proposed and successfully used. For the completely positive cone, the most common approach is to build outer approximations, with the only inner approximations available being an LP method proposed by Bundfuss and Dur, and an SDP method proposed by Lasserre. We propose the use of the cone of nonnegative scaled diagonally dominant matrices as a natural inner approximation to the completely positive cone. Using projections of this cone we derive new graph-based second order cone approximation schemes for completely positive and copositive programming, leading to both uniform and problem dependent hierarchies. This offers a compromise between the expressive power of semidefinite programming and the speed of LP approaches. Furthermore the approach is versatile, and liable to be adapted in other contexts and schemes.