Polynomial optimization: Error analysis and applications
Additional contact information
Zhao Sun: Tilburg University, School of Economics and Management
Other publications TiSEM from Tilburg University, School of Economics and Management
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.
References: View complete reference list from CitEc
Citations Track citations by RSS feed
Downloads: (external link)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: http://EconPapers.repec.org/RePEc:tiu:tiutis:445eb510-5093-4b9c-8007-18160bb14a84
Access Statistics for this paper
More papers in Other publications TiSEM from Tilburg University, School of Economics and Management
Series data maintained by Richard Broekman ().