A factorization method for completely positive matrices
A factorization method for completely positive matrices
复制标题
DOI：
10.1016/j.laa.2019.12.024
复制
发表时间：
2020-04-15
影响因子：
1.1
通讯作者：
Duer, Mirjam
中科院分区：
文献类型：
--
作者：
Groetzner, Patrick;Duer, Mirjam
如果存在一个逐项非负矩阵 B 使得 A = BBT，则矩阵 A 称为完全正矩阵。这些矩阵在组合和二次优化中发挥着重要作用。在本文中，我们研究了寻找给定完全正矩阵 A 的非负因式分解 BBT 的问题。我们将此因式分解问题表述为非凸可行性问题，并开发了一种基于交替投影的解决方法。可以显示该算法的局部收敛结果。我们还提供了启发式扩展，可以提高算法的数值性能。大量的数值测试表明，分解方法在大多数测试实例中都非常快，并且比现有算法表现得更好。 (C) 2019 Elsevier Inc. 保留所有权利。
A matrix A is called completely positive, if there exists an entrywise nonnegative matrix B such that A = BBT. These matrices play a major role in combinatorial and quadratic optimization. In this paper, we study the problem of finding a nonnegative factorization BBT of a given completely positive matrix A. 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 of the test instances and performs better than existing algorithms. (C) 2019 Elsevier Inc. All rights reserved.