### 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* = **Z**_{N} has a sum-of-squares certificate supported on at most 3*d* 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 language | English |
---|---|

Title of host publication | 2015 IEEE 54th Annual Conference on Decision and Control (CDC) |

Editors | Mitsuji Sampei |

Place of Publication | Piscataway NJ USA |

Publisher | IEEE, Institute of Electrical and Electronics Engineers |

Pages | 5909-5914 |

Number of pages | 6 |

ISBN (Electronic) | 9781479978861, 9781479978847, 9781479978854 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

Event | IEEE Conference on Decision and Control 2015 - Osaka, Japan Duration: 15 Dec 2015 → 18 Dec 2015 Conference number: 54th |

### Conference

Conference | IEEE Conference on Decision and Control 2015 |
---|---|

Abbreviated title | CDC |

Country | Japan |

City | Osaka |

Period | 15/12/15 → 18/12/15 |

### Keywords

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

## Cite this

*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