TY - UNPB

T1 - An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix

AU - Badenbroek, Riley

AU - de Klerk, Etienne

PY - 2020

Y1 - 2020

N2 - We propose an analytic center cutting plane method to determine if 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 Berman, Dür, and Shaked-Monderer [Electronic Journal of Linear Algebra, 2015]. 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 Xia, Vera, and Zuluaga [INFORMS Journal on Computing, 2018]. 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.

AB - We propose an analytic center cutting plane method to determine if 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 Berman, Dür, and Shaked-Monderer [Electronic Journal of Linear Algebra, 2015]. 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 Xia, Vera, and Zuluaga [INFORMS Journal on Computing, 2018]. 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.

KW - copositive optimization

KW - analytic center cutting plane method

KW - completely positive matrices

M3 - Working paper

T3 - arXiv

BT - An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix

PB - Cornell University Library

CY - Ithaca

ER -