Polynomial optimization: Error analysis and applications

Zhao Sun

Research output: ThesisDoctoral ThesisScientific

385 Downloads (Pure)

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.
Original languageEnglish
QualificationDoctor of Philosophy
Supervisors/Advisors
  • Laurent, Monique, Promotor
  • de Klerk, Etienne, Promotor
Award date29 Jun 2015
Place of PublicationTilburg
Publisher
Print ISBNs9789056684402
Publication statusPublished - 2015

Fingerprint

Error Analysis
Polynomial
Optimization
Upper bound
Convergence Rate
Multinomial Distribution
Graph in graph theory
Stability number
Hypergeometric Distribution
Rational Points
Denominator
Global Optimum
Representation Theorem
Polynomial function
Inequality Constraints
Minimizer
Convergence Analysis
Compact Set
Structural Properties
Hierarchy

Cite this

Sun, Z. (2015). Polynomial optimization: Error analysis and applications. Tilburg: CentER, Center for Economic Research.
Sun, Zhao. / Polynomial optimization : Error analysis and applications. Tilburg : CentER, Center for Economic Research, 2015. 189 p.
@phdthesis{445eb51050934b9c800718160bb14a84,
title = "Polynomial optimization: Error analysis and applications",
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.",
author = "Zhao Sun",
year = "2015",
language = "English",
isbn = "9789056684402",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",

}

Sun, Z 2015, 'Polynomial optimization: Error analysis and applications', Doctor of Philosophy, Tilburg.

Polynomial optimization : Error analysis and applications. / Sun, Zhao.

Tilburg : CentER, Center for Economic Research, 2015. 189 p.

Research output: ThesisDoctoral ThesisScientific

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 -

Sun Z. Polynomial optimization: Error analysis and applications. Tilburg: CentER, Center for Economic Research, 2015. 189 p. (CentER Dissertation Series).