A new certificate for copositivity

Peter James Clair Dickinson

Research output: Contribution to journalArticleAcademicpeer-review

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 a copositive matrix. In the final section of this paper we introduce a set of newly discovered extremal copositive matrices.
LanguageEnglish
Pages15-37
Number of pages23
JournalLinear algebra and its applications
Volume569
DOIs
Publication statusPublished - 15 May 2019

Fingerprint

Certificate
Farkas Lemma
Positive semidefinite
Linear systems
Cones
Half line
Linear Inequalities
Extremes
Cone
Linear Systems
Non-negative
Zero
Theorem

Keywords

  • Copositive matrix
  • NP-hard
  • Certificate
  • Minimal zeros
  • Extreme ray

Cite this

Dickinson, Peter James Clair. / A new certificate for copositivity. In: Linear algebra and its applications. 2019 ; Vol. 569. pp. 15-37.
@article{c467d28f77ae4858846a5e2de1b22e18,
title = "A new certificate for copositivity",
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 a copositive matrix. In the final section of this paper we introduce a set of newly discovered extremal copositive matrices.",
keywords = "Copositive matrix, NP-hard, Certificate, Minimal zeros, Extreme ray",
author = "Dickinson, {Peter James Clair}",
year = "2019",
month = "5",
day = "15",
doi = "10.1016/j.laa.2018.12.025",
language = "English",
volume = "569",
pages = "15--37",
journal = "Linear algebra and its applications",
issn = "0024-3795",
publisher = "Elsevier",

}

A new certificate for copositivity. / Dickinson, Peter James Clair.

In: Linear algebra and its applications, Vol. 569, 15.05.2019, p. 15-37.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A new certificate for copositivity

AU - Dickinson, Peter James Clair

PY - 2019/5/15

Y1 - 2019/5/15

N2 - 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 a copositive matrix. In the final section of this paper we introduce a set of newly discovered extremal copositive matrices.

AB - 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 a copositive matrix. In the final section of this paper we introduce a set of newly discovered extremal copositive matrices.

KW - Copositive matrix

KW - NP-hard

KW - Certificate

KW - Minimal zeros

KW - Extreme ray

U2 - 10.1016/j.laa.2018.12.025

DO - 10.1016/j.laa.2018.12.025

M3 - Article

VL - 569

SP - 15

EP - 37

JO - Linear algebra and its applications

T2 - Linear algebra and its applications

JF - Linear algebra and its applications

SN - 0024-3795

ER -