Optimization Online


A New Certificate For Copositivity

Peter J.C. Dickinson (p.j.c.dickinson***at***utwente.nl)

Abstract: In this article we introduce a new method of certifying any copositive matrix to be copositive. This is done through the use of a theorem by Hadeler and the Farkas Lemma. For a given copositive matrix this certificate is constructed by solving finitely many linear systems, and can be subsequently checked by checking finitely many linear inequalities. In some cases this certificate can be relatively small, even when the matrix generates an extreme ray of the copositive cone which is not positive semidefinite plus nonnegative. This certificate can also be used to generate the set of minimal zeros of copositive matrix. In the final section of this paper we introduce a matrix which we show to be a newly discovered extremal copositive matrix.

Keywords: Copositive Matrix; NP-hard; Certificate; Minimal zeros; Extreme ray

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


Download: [PDF]

Entry Submitted: 07/28/2017
Entry Accepted: 07/28/2017
Entry Last Modified: 03/02/2018

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