Polynomial optimization: Error analysis and applications

Zhao Sun

Research output: ThesisDoctoral Thesis

542 Downloads (Pure)


Polynomial optimization is the problem of minimizing a polynomial function subject to polynomial inequality constraints. In this thesis we investigate several hierarchies of relaxations for polynomial optimization problems. Our main interest lies in understanding their performance, in particular how fast they converge to the global optimum. In Chapters 2, 3 and 4, we consider polynomial optimization over the simplex. We focus on a hierarchy of upper bounds obtained by minimizing over the rational points with given denominators. In Chapter 2, we give a much simplified analysis for its known convergence rate, using the multinomial distribution. In Chapter 3, assuming the existence of rational minimizers, we show a new refined convergence rate, by replacing the multinomial distribution with the hypergeometric distribution. In Chapter 4, we consider this hierarchy of upper bounds, together with a hierarchy of lower bounds based on Polya's representation theorem. We study their relation and give refined convergence analysis for their difference. In Chapter 5, we consider the more general problem of minimizing a polynomial over a general compact set. We study a hierarchy of upper bounds proposed by Lasserre, and show its convergence rate. In Chapter 6, we study Handelman’s hierarchy of upper bounds for the stability number in graphs. We relate the Handelman rank with structural properties of graphs and compute the Handelman rank for several classes of graphs.
Original languageEnglish
QualificationDoctor of Philosophy
  • Laurent, Monique, Promotor
  • de Klerk, Etienne, Promotor
Award date29 Jun 2015
Place of PublicationTilburg
Print ISBNs9789056684402
Publication statusPublished - 2015


Dive into the research topics of 'Polynomial optimization: Error analysis and applications'. Together they form a unique fingerprint.

Cite this