×

CopositiveAnalyticCenter.jl

swMATH ID: 42602
Software Authors: Badenbroek, Riley; de Klerk, Etienne
Description: An analytic center cutting plane method to determine complete positivity of a matrix. We propose an analytic center cutting plane method to determine whether a matrix is completely positive and return a cut that separates it from the completely positive cone if not. This was stated as an open (computational) problem by A. Berman et al. [Electron. J. Linear Algebra 29, 46–58 (2015; Zbl 1326.15048)]. Our method optimizes over the intersection of a ball and the copositive cone, where membership is determined by solving a mixed-integer linear program suggested by W. Xia et al. [INFORMS J. Comput. 32, No. 1, 40–56 (2020; Zbl 07284452)]. Thus, our algorithm can, more generally, be used to solve any copositive optimization problem, provided one knows the radius of a ball containing an optimal solution. Numerical experiments show that the number of oracle calls (matrix copositivity checks) for our implementation scales well with the matrix size, growing roughly like O(d2) for d×d matrices. The method is implemented in Julia and available at https://github.com/rileybadenbroek/CopositiveAnalyticCenter.jl (opens in new tab). Summary of contribution: Completely positive matrices play an important role in operations research. They allow many NP-hard problems to be formulated as optimization problems over a proper cone, which enables them to benefit from the duality theory of convex programming. We propose an analytic center cutting plane method to determine whether a matrix is completely positive by solving an optimization problem over the copositive cone. In fact, we can use our method to solve any copositive optimization problem, provided we know the radius of a ball containing an optimal solution. We emphasize numerical performance and stability in developing this method. A software implementation in Julia is provided.
Homepage: https://docs.juliahub.com/CopositiveAnalyticCenter/
Source Code:  https://github.com/rileybadenbroek/CopositiveAnalyticCenter.jl
Dependencies: Julia
Related Software: quadprogIP; GitHub
Cited in: 1 Document

Citations by Year