The cone $\nnd$ of matrices that have a nonnegative decomposition is defined as the set of matrices $X=X_1+X_2$ with $X_1$ positive semidefinite and $X_2$ componentwise nonnegative. The problem of determining whether or not a given matrix $\bar X$ lies in $\nnd$ has gained practical importance by recent publications such as Arima et. al. who show that for a rather general class of nonconvex mixed binary quadratic optimization problems the optimal value can be obtained from an optimization problem over the copositive cone with a single variable. This optimization problem can be relaxed to a problem over $\nnd$, and the relaxation can be solved by bisection if an efficient code is available for determining whether or not a given matrix $\bar X$ lies in $\nnd$. This problem can be reduced to a semidefinite program with sign-constraints, and thus, standard interior-point solvers are applicable. Here, the special structure of the problem shall be exploited to derive a new algorithm for generating a certificate for the question ``$\bar X\in \nnd$?''. As a by-product, a new algorithm is presented for solving a variant of the Loavsz-Shrijver relaxation of the max-stable-set problem.