License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.78
URN: urn:nbn:de:0030-drops-63368
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6336/
Kurpisz, Adam ;
Leppänen, Samuli ;
Mastrolilli, Monaldo
Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems
Abstract
We give two results concerning the power of the Sum-Of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree 2d and an odd number of variables n, we prove that (n+2d-1)/2 levels of the SoS/Lasserre hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito.
Additionally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull, and conjectured that the SoS/Lasserre rank for the same problem is n-1. We disprove this conjecture and derive lower and upper bounds for the rank.
BibTeX - Entry
@InProceedings{kurpisz_et_al:LIPIcs:2016:6336,
author = {Adam Kurpisz and Samuli Lepp{\"a}nen and Monaldo Mastrolilli},
title = {{Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {78:1--78:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6336},
URN = {urn:nbn:de:0030-drops-63368},
doi = {10.4230/LIPIcs.ICALP.2016.78},
annote = {Keywords: SoS/Lasserre hierarchy, lift and project methods, binary polynomial optimization}
}
Keywords: |
|
SoS/Lasserre hierarchy, lift and project methods, binary polynomial optimization |
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
23.08.2016 |