Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Supervisors/Advisors 

Award date  29 Jun 2015 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  9789056684402 
Publication status  Published  2015 
Fingerprint
Cite this
}
Polynomial optimization : Error analysis and applications. / Sun, Zhao.
Tilburg : CentER, Center for Economic Research, 2015. 189 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  Polynomial optimization
T2  Error analysis and applications
AU  Sun, Zhao
PY  2015
Y1  2015
N2  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.
AB  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.
M3  Doctoral Thesis
SN  9789056684402
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 