Exploiting symmetry in copositive programs via semidefinite hierarchies

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable consequence of the intractability of the generic problems
that such approaches attempt to solve. To address such drawbacks, we develop customized solution approaches for highly symmetric copositive programs, which arise naturally in several contexts. For instance, symmetry
properties of combinatorial problems are typically inherited when they are addressed via copositive programming. As a result we are able to compute new bounds for crossing number instances in complete bipartite graphs.
Original languageEnglish
Pages (from-to)659-680
JournalMathematical Programming
Volume151
Issue number2
DOIs
Publication statusPublished - Jul 2015

Fingerprint

Semidefinite Program
Semidefinite Programming
Programming
Conic Programming
Symmetry
Crossing number
Complete Bipartite Graph
Combinatorial Problems
Cones
Cone
Optimization
Line
Approximation
Hierarchy
Context

Cite this

@article{e3ada044e6944a63909954cd7ff6d8cb,
title = "Exploiting symmetry in copositive programs via semidefinite hierarchies",
abstract = "Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable consequence of the intractability of the generic problemsthat such approaches attempt to solve. To address such drawbacks, we develop customized solution approaches for highly symmetric copositive programs, which arise naturally in several contexts. For instance, symmetryproperties of combinatorial problems are typically inherited when they are addressed via copositive programming. As a result we are able to compute new bounds for crossing number instances in complete bipartite graphs.",
author = "C. Dobre and {Vera Lizcano}, J.C.",
year = "2015",
month = "7",
doi = "10.1007/s10107-015-0879-0",
language = "English",
volume = "151",
pages = "659--680",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

Exploiting symmetry in copositive programs via semidefinite hierarchies. / Dobre, C.; Vera Lizcano, J.C.

In: Mathematical Programming, Vol. 151, No. 2, 07.2015, p. 659-680.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Exploiting symmetry in copositive programs via semidefinite hierarchies

AU - Dobre, C.

AU - Vera Lizcano, J.C.

PY - 2015/7

Y1 - 2015/7

N2 - Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable consequence of the intractability of the generic problemsthat such approaches attempt to solve. To address such drawbacks, we develop customized solution approaches for highly symmetric copositive programs, which arise naturally in several contexts. For instance, symmetryproperties of combinatorial problems are typically inherited when they are addressed via copositive programming. As a result we are able to compute new bounds for crossing number instances in complete bipartite graphs.

AB - Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable consequence of the intractability of the generic problemsthat such approaches attempt to solve. To address such drawbacks, we develop customized solution approaches for highly symmetric copositive programs, which arise naturally in several contexts. For instance, symmetryproperties of combinatorial problems are typically inherited when they are addressed via copositive programming. As a result we are able to compute new bounds for crossing number instances in complete bipartite graphs.

U2 - 10.1007/s10107-015-0879-0

DO - 10.1007/s10107-015-0879-0

M3 - Article

VL - 151

SP - 659

EP - 680

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -