Optimization Online


A factorization method for completely positive matrices

Patrick Groetzner(groetzner***at***uni-trier.de)
Mirjam Dür(mirjam.duer***at***math.uni-augsburg.de)

Abstract: A matrix A is called completely positive, if there exists an entrywise nonnegative matrix B such that A = BB^T. These matrices play a major role in combinatorial and quadratic optimization. In this paper, we develop a factorization algorithm which, for a given completely positive matrix A, computes the nonnegative factorization BB^T. We formulate this factorization problem as a nonconvex feasibility problem and develop a solution method based on alternating projections. A local convergence result can be shown for this algorithm. We also provide a heuristic extension which improves the numerical performance of the algorithm. Extensive numerical tests show that the factorization method is very fast in most instances.

Keywords: completely positive matrices, matrix factorization, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming

Citation: P. Groetzner, M. Dür: A factorization method for completely positive matrices. Preprint, 2018.

Download: [PDF]

Entry Submitted: 03/07/2018
Entry Accepted: 03/07/2018
Entry Last Modified: 03/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society