  Motivated by the expressive power of completely positive programming to
encode hard optimization problems, many approximation schemes for the
completely positive cone have been proposed and successfully used. Most schemes
are based on outer approximations, with the only inner approximations available
being linear programming based methods proposed by Bundfuss and D\"ur and also
Y{\i}ld{\i}r{\i}m, and a semidefinite programming based method proposed by
Lasserre. In this paper, 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 programming,
leading to both uniform and problem-dependent hierarchies. This offers a
compromise between the expressive power of semidefinite programming and the
speed of linear programming based approaches. Numerical results on random
problems, standard quadratic programs and the stable set problem are presented
to illustrate the effectiveness of our approach.
