Spectral bounds for unconstrained (-1,1)-quadratic optimization problems

Walid Ben-Ameur; José Neto

doi:10.1016/j.ejor.2010.02.042

Spectral bounds for unconstrained (-1,1)-quadratic optimization problems

Research output: Contribution to journal › Article › peer-review

Abstract

Given an unconstrained quadratic optimization problem in the following form:(QP) min {x^t Qx | x ∈ {- 1, 1}ⁿ},with Q ∈ R^{n × n}, we present different methods for computing bounds on its optimal objective value. Some of the lower bounds introduced are shown to generally improve over the one given by a classical semidefinite relaxation. We report on theoretical results on these new bounds and provide preliminary computational experiments on small instances of the maximum cut problem illustrating their performance.

Original language	English
Pages (from-to)	15-24
Number of pages	10
Journal	European Journal of Operational Research
Volume	207
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2010.02.042
Publication status	Published - 16 Nov 2010

Keywords

Maximum cut problem
Semidefinite programming
Unconstrained quadratic programming

Access to Document

10.1016/j.ejor.2010.02.042

Cite this

@article{2e7fe10ee2bf44299e487f3338e8c7a2,

title = "Spectral bounds for unconstrained (-1,1)-quadratic optimization problems",

abstract = "Given an unconstrained quadratic optimization problem in the following form:(QP) min \{xt Qx | x ∈ \{- 1, 1\}n\},with Q ∈ Rn × n, we present different methods for computing bounds on its optimal objective value. Some of the lower bounds introduced are shown to generally improve over the one given by a classical semidefinite relaxation. We report on theoretical results on these new bounds and provide preliminary computational experiments on small instances of the maximum cut problem illustrating their performance.",

keywords = "Maximum cut problem, Semidefinite programming, Unconstrained quadratic programming",

author = "Walid Ben-Ameur and Jos{\'e} Neto",

year = "2010",

month = nov,

day = "16",

doi = "10.1016/j.ejor.2010.02.042",

language = "English",

volume = "207",

pages = "15--24",

journal = "European Journal of Operational Research",

issn = "0377-2217",

number = "1",

}

TY - JOUR

T1 - Spectral bounds for unconstrained (-1,1)-quadratic optimization problems

AU - Ben-Ameur, Walid

AU - Neto, José

PY - 2010/11/16

Y1 - 2010/11/16

N2 - Given an unconstrained quadratic optimization problem in the following form:(QP) min {xt Qx | x ∈ {- 1, 1}n},with Q ∈ Rn × n, we present different methods for computing bounds on its optimal objective value. Some of the lower bounds introduced are shown to generally improve over the one given by a classical semidefinite relaxation. We report on theoretical results on these new bounds and provide preliminary computational experiments on small instances of the maximum cut problem illustrating their performance.

AB - Given an unconstrained quadratic optimization problem in the following form:(QP) min {xt Qx | x ∈ {- 1, 1}n},with Q ∈ Rn × n, we present different methods for computing bounds on its optimal objective value. Some of the lower bounds introduced are shown to generally improve over the one given by a classical semidefinite relaxation. We report on theoretical results on these new bounds and provide preliminary computational experiments on small instances of the maximum cut problem illustrating their performance.

KW - Maximum cut problem

KW - Semidefinite programming

KW - Unconstrained quadratic programming

U2 - 10.1016/j.ejor.2010.02.042

DO - 10.1016/j.ejor.2010.02.042

M3 - Article

AN - SCOPUS:77953870590

SN - 0377-2217

VL - 207

SP - 15

EP - 24

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

Spectral bounds for unconstrained (-1,1)-quadratic optimization problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this