On the computation of $C^*$ certificates

Florian Jarre (jarreopt.uni-duesseldorf.de)
Katrin Schmallowsky (schmallowskyopt.uni-duesseldorf.de)

Abstract: 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.

Keywords: Completely positive matrices

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: Report, Mathematisches Institut, Universit\"at D\"usseldorf (2008)

Download: [PDF]

Entry Submitted: 05/04/2008
Entry Accepted: 05/05/2008
Entry Last Modified: 05/06/2008

Modify/Update this entry