Economics at your fingertips  

Polynomial optimization: Error analysis and applications

Zhao Sun
Additional contact information
Zhao Sun: Tilburg University, School of Economics and Management

Other publications TiSEM from Tilburg University, School of Economics and Management

Abstract: 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.

Date: 2015
Note: Dissertation
References: View complete reference list from CitEc
Citations: Track citations by RSS feed


Downloads: (external link) (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this paper

More papers in Other publications TiSEM from Tilburg University, School of Economics and Management
Bibliographic data for series maintained by Richard Broekman ().

Page updated 2019-09-17
Handle: RePEc:tiu:tiutis:445eb510-5093-4b9c-8007-18160bb14a84