On the computation of $C^*$ certificates

The cone of completely positive matrices $C^*$ is the convex hull of all symmetric rank-1-matrices $xx^T$ with nonnegative entries. Determining whether a given matrix $B$ is completely positive is an $\cal NP$-complete problem. We examine a simple algorithm which -- for a given input $B$ -- either determines a certificate proving that $B\in C^*$ or converges to a matrix $\bar S$ in $C^*$ which in some sense is ``close'' to $B$. Numerical experiments on matrices $B$ of dimension up to 200 conclude the presentation.

Citation

Report, Mathematisches Institut, Universit\"at D\"usseldorf (2008) http://www.opt.uni-duesseldorf.de/en/forschung-fs.html