Positive semidefinite approximations to the cone of copositive kernels

Olga Kuryatnikova, J. C. Vera

Research output: Working paperOther research output

Abstract

It has been shown that the maximum stable set problem in some infinite graphs, and the kissing number problem in particular, reduces to a minimization problem over the cone of copositive kernels. Optimizing over this infinite dimensional cone is not tractable, and approximations of this cone have been hardly considered in literature. We propose two convergent hierarchies of subsets of copositive kernels, in terms of non-negative and positive definite kernels. We use these hierarchies and representation theorems for invariant positive definite kernels on the sphere to construct new SDP-based bounds on the kissing number. This results in fast-to-compute upper bounds on the kissing number that lie between the currently existing LP and SDP bounds.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages29
Publication statusPublished - Dec 2018

Publication series

NamearXiv
Volume1812.00274

Fingerprint

Positive semidefinite
Positive Definite Kernels
Cone
kernel
Approximation
Infinite Graphs
Stable Set
Representation Theorem
Minimization Problem
Non-negative
Upper bound
Subset
Invariant
Hierarchy

Cite this

Kuryatnikova, O., & Vera, J. C. (2018). Positive semidefinite approximations to the cone of copositive kernels. (arXiv; Vol. 1812.00274). Ithaca: Cornell University Library.
Kuryatnikova, Olga ; Vera, J. C. / Positive semidefinite approximations to the cone of copositive kernels. Ithaca : Cornell University Library, 2018. (arXiv).
@techreport{2a83022b27cb4b8b87cda8c2e79e00cb,
title = "Positive semidefinite approximations to the cone of copositive kernels",
abstract = "It has been shown that the maximum stable set problem in some infinite graphs, and the kissing number problem in particular, reduces to a minimization problem over the cone of copositive kernels. Optimizing over this infinite dimensional cone is not tractable, and approximations of this cone have been hardly considered in literature. We propose two convergent hierarchies of subsets of copositive kernels, in terms of non-negative and positive definite kernels. We use these hierarchies and representation theorems for invariant positive definite kernels on the sphere to construct new SDP-based bounds on the kissing number. This results in fast-to-compute upper bounds on the kissing number that lie between the currently existing LP and SDP bounds.",
author = "Olga Kuryatnikova and Vera, {J. C.}",
year = "2018",
month = "12",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

Kuryatnikova, O & Vera, JC 2018 'Positive semidefinite approximations to the cone of copositive kernels' arXiv, vol. 1812.00274, Cornell University Library, Ithaca.

Positive semidefinite approximations to the cone of copositive kernels. / Kuryatnikova, Olga; Vera, J. C.

Ithaca : Cornell University Library, 2018. (arXiv; Vol. 1812.00274).

Research output: Working paperOther research output

TY - UNPB

T1 - Positive semidefinite approximations to the cone of copositive kernels

AU - Kuryatnikova, Olga

AU - Vera, J. C.

PY - 2018/12

Y1 - 2018/12

N2 - It has been shown that the maximum stable set problem in some infinite graphs, and the kissing number problem in particular, reduces to a minimization problem over the cone of copositive kernels. Optimizing over this infinite dimensional cone is not tractable, and approximations of this cone have been hardly considered in literature. We propose two convergent hierarchies of subsets of copositive kernels, in terms of non-negative and positive definite kernels. We use these hierarchies and representation theorems for invariant positive definite kernels on the sphere to construct new SDP-based bounds on the kissing number. This results in fast-to-compute upper bounds on the kissing number that lie between the currently existing LP and SDP bounds.

AB - It has been shown that the maximum stable set problem in some infinite graphs, and the kissing number problem in particular, reduces to a minimization problem over the cone of copositive kernels. Optimizing over this infinite dimensional cone is not tractable, and approximations of this cone have been hardly considered in literature. We propose two convergent hierarchies of subsets of copositive kernels, in terms of non-negative and positive definite kernels. We use these hierarchies and representation theorems for invariant positive definite kernels on the sphere to construct new SDP-based bounds on the kissing number. This results in fast-to-compute upper bounds on the kissing number that lie between the currently existing LP and SDP bounds.

M3 - Working paper

T3 - arXiv

BT - Positive semidefinite approximations to the cone of copositive kernels

PB - Cornell University Library

CY - Ithaca

ER -

Kuryatnikova O, Vera JC. Positive semidefinite approximations to the cone of copositive kernels. Ithaca: Cornell University Library. 2018 Dec. (arXiv).