Optimization Online


Generating irreducible copositive matrices using the stable set problem

Peter J.C. Dickinson (peter.jc.dickinson***at***gmail.com)
Reinier de Zeeuw (reinier.dezeeuw***at***gmail.com)

Abstract: In this paper it is considered how graphs can be used to generate copositive matrices, and necessary and sufficient conditions are given for these generated matrices to then be irreducible with respect to the set of positive semidefinite plus nonnegative matrices. This is done through combining the well known copositive formulation of the stable set problem with recent results on necessary and sufficient conditions for a copositive matrix to be irreducible. By applying this result, tens of thousands of new irreducible copositive matrices of order less than or equal to thirteen were found. These matrices were then tested for being extreme copositive matrices, and it was found that in all but three cases this was indeed the case. It is also demonstrated in this paper that these matrices provide difficult instances to test approximations of the copositive cone against.

Keywords: alpha-critical, Copositive, Extreme, Irreducible, Stablity number

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Linear, Cone and Semidefinite Programming (Other )


Download: [PDF]

Entry Submitted: 12/16/2018
Entry Accepted: 12/16/2018
Entry Last Modified: 01/28/2019

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