Sparse sum-of-squares certificates on finite abelian groups

Hamza Fawzi, James Saunderson, Pablo A. Parrilo

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Sums-of-squares techniques have played an important role in optimization and control. One question that has attracted a lot of attention is to exploit sparsity in order to reduce the size of sum-of-squares programs. In this paper we consider the problem of finding sparse sum-of-squares certificates for functions defined on a finite abelian group G. In this setting the natural basis over which to measure sparsity is the Fourier basis of G (also called the basis of characters of G). We establish combinatorial conditions on subsets S and T of Fourier basis elements under which nonnegative functions with Fourier support S are sums of squares of functions with Fourier support T. Our combinatorial condition involves constructing a chordal cover of a graph related to G and S with maximal cliques related to T. These techniques allow us to show that any nonnegative quadratic function in binary variables is a sum of squares of functions of degree at most [n/2], resolving a conjecture of Laurent [11]. They also allow us to show that any nonnegative function of degree d on G = ZN has a sum-of-squares certificate supported on at most 3d log(N/d) Fourier basis elements. By duality this construction yields the first explicit family of polytopes in increasing dimensions that have a semidefinite programming description that is vanishingly smaller than any linear programming description.

Original languageEnglish
Title of host publication2015 IEEE 54th Annual Conference on Decision and Control (CDC)
EditorsMitsuji Sampei
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages5909-5914
Number of pages6
ISBN (Electronic)9781479978861, 9781479978847, 9781479978854
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventIEEE Conference on Decision and Control 2015 - Osaka, Japan
Duration: 15 Dec 201518 Dec 2015
Conference number: 54th

Conference

ConferenceIEEE Conference on Decision and Control 2015
Abbreviated titleCDC
CountryJapan
CityOsaka
Period15/12/1518/12/15

Keywords

  • Discrete Fourier transforms
  • Hypercubes
  • Linear programming
  • Optimization
  • Programming
  • Symmetric matrices
  • Three-dimensional displays

Cite this

Fawzi, H., Saunderson, J., & Parrilo, P. A. (2015). Sparse sum-of-squares certificates on finite abelian groups. In M. Sampei (Ed.), 2015 IEEE 54th Annual Conference on Decision and Control (CDC) (pp. 5909-5914). [7403148] IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/CDC.2015.7403148