Testing copositivity via mixed-integer linear programming

被引：11
作者：
Anstreicher, Kurt M. [1 ]
机构：
[1] Univ Iowa, Dept Business Analyt, Iowa City, IA 52242 USA
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2021年 / 609卷
关键词：
Copositive matrix; Copositive programming; Mixed-integer linear programming; STABILITY NUMBER; SEMIDEFINITE; ALGORITHM; GRAPH;
D O I：
10.1016/j.laa.2020.09.302
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. (C) 2020 Elsevier Inc. All rights reserved.
引用
收藏
页码：218 / 230
页数：13
相关论文
共 23 条
[1]  
BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056
[2]   Solving standard quadratic optimization problems via linear, semidefinite and copositive programming [J].
Bomze, IM ;
De Klerk, E .
JOURNAL OF GLOBAL OPTIMIZATION, 2002, 24 (02) :163-185
[3]   Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization [J].
Bomze, Immanuel M. ;
Schachinger, Werner ;
Uchida, Gabriele .
JOURNAL OF GLOBAL OPTIMIZATION, 2012, 52 (03) :423-445
[4]   Algorithmic copositivity detection by simplicial partition [J].
Bundfuss, Stefan ;
Duer, Mirjam .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) :1511-1523
[5]   A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations [J].
Burer, Samuel ;
Vandenbussche, Dieter .
MATHEMATICAL PROGRAMMING, 2008, 113 (02) :259-282
[6]   A gentle, geometric introduction to copositive optimization [J].
Burer, Samuel .
MATHEMATICAL PROGRAMMING, 2015, 151 (01) :89-116
[7]   On the copositive representation of binary and continuous nonconvex quadratic programs [J].
Burer, Samuel .
MATHEMATICAL PROGRAMMING, 2009, 120 (02) :479-495
[8]   Approximation of the stability number of a graph via copositive programming [J].
De Klerk, E ;
Pasechnik, DV .
SIAM JOURNAL ON OPTIMIZATION, 2002, 12 (04) :875-892
[9]   A new certificate for copositivity [J].
Dickinson, Peter J. C. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 569 :15-37
[10]   On the computational complexity of membership problems for the completely positive cone and its dual [J].
Dickinson, Peter J. C. ;
Gijben, Luuk .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2014, 57 (02) :403-415
123