Focused polynomials, random projections and approximation algorithms for polynomial optimization over the sphere

In this thesis, we study approximation algorithms for polynomial optimization over the sphere, concentrating on classes of polynomials whose optimum on the sphere can be efficiently approximated to a factor that only depends on the degree of the polynomial, and not on the dimension of the problem. We extend and generalize an existing class of polynomials known as focused polynomials which exhibit this property. These polynomials can be well approximated by a random projection, reducing the problem to optimization over a sphere of a much smaller dimension. We then introduce polynomials generated from a focused cone, which generalizes focused polynomials, and show that the dimension required for the projection is related to a geometrical property of the focused cone, its Gaussian width. Next we study the behavior of the maximum of quadratic polynomials under a random projection, and show that if the dimension of the random projection is at least the stable rank of the matrix representation of this polynomial, its maximum over the sphere is preserved within a constant factor. We then show that the stable rank of matrices representing quadratic focused polynomials is also small, and how some properties of focused polynomials generalizes statements about matrices. Finally we apply sum of squares optimization to focused polynomials, and show that given a polynomial generated from a focused cone one can devise a rounding algorithm that finds a vector close to this cone, which gives a good approximation to the optimum.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Yuan, Chenyang

Advisor dc:contributor.advisor

• Pablo A. Parrilo.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/120396

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/120396