Optimization over polynomials

Selected topics

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Minimizing a polynomial function over a region defined by polynomial inequalities
models broad classes of hard problems from combinatorics, geometry and optimization.
New algorithmic approaches have emerged recently for computing the global
minimum, by combining tools from real algebra (sums of squares of polynomials) and functional
analysis (moments of measures) with semidefinite optimization. Sums of squares
are used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies to
some combinatorial graph problems, and discuss links with other relaxation methods.
Original languageEnglish
Title of host publicationProceedings of the International Congress of Mathematicians 2014 (ICM 2014)
EditorsSun Young Jang, Young Rock Kim, Dae-Woong Lee, Ikkwon Yie
Place of PublicationSeoul
PublisherKyung Moon SA Co. Ltd.
Pages843-869
ISBN (Print)9788961058070
Publication statusPublished - 2014
EventInternational Congress of Mathematicians 2014 - Seoul, Korea, Republic of
Duration: 13 Aug 201421 Aug 2014

Conference

ConferenceInternational Congress of Mathematicians 2014
Abbreviated titleICM 2014
CountryKorea, Republic of
CitySeoul
Period13/08/1421/08/14

Fingerprint

Semidefinite Optimization
Positive Polynomials
Semidefinite Relaxation
Global Minimizer
Polynomial
Optimization
Moment Problem
Relaxation Method
Sum of squares
Polynomial function
Combinatorics
Hilbert
Optimality
Moment
Algebra
Methodology
Computing
Graph in graph theory
Review
Class

Cite this

Laurent, M. (2014). Optimization over polynomials: Selected topics. In S. Y. Jang, Y. R. Kim, D-W. Lee, & I. Yie (Eds.), Proceedings of the International Congress of Mathematicians 2014 (ICM 2014) (pp. 843-869). Seoul: Kyung Moon SA Co. Ltd..
Laurent, M. / Optimization over polynomials : Selected topics. Proceedings of the International Congress of Mathematicians 2014 (ICM 2014). editor / Sun Young Jang ; Young Rock Kim ; Dae-Woong Lee ; Ikkwon Yie. Seoul : Kyung Moon SA Co. Ltd., 2014. pp. 843-869
@inproceedings{b06ad040f6c544909417231cefc0343d,
title = "Optimization over polynomials: Selected topics",
abstract = "Minimizing a polynomial function over a region defined by polynomial inequalitiesmodels broad classes of hard problems from combinatorics, geometry and optimization.New algorithmic approaches have emerged recently for computing the globalminimum, by combining tools from real algebra (sums of squares of polynomials) and functionalanalysis (moments of measures) with semidefinite optimization. Sums of squaresare used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies tosome combinatorial graph problems, and discuss links with other relaxation methods.",
author = "M. Laurent",
year = "2014",
language = "English",
isbn = "9788961058070",
pages = "843--869",
editor = "Jang, {Sun Young} and Kim, {Young Rock} and Dae-Woong Lee and Ikkwon Yie",
booktitle = "Proceedings of the International Congress of Mathematicians 2014 (ICM 2014)",
publisher = "Kyung Moon SA Co. Ltd.",

}

Laurent, M 2014, Optimization over polynomials: Selected topics. in SY Jang, YR Kim, D-W Lee & I Yie (eds), Proceedings of the International Congress of Mathematicians 2014 (ICM 2014). Kyung Moon SA Co. Ltd., Seoul, pp. 843-869, International Congress of Mathematicians 2014, Seoul, Korea, Republic of, 13/08/14.

Optimization over polynomials : Selected topics. / Laurent, M.

Proceedings of the International Congress of Mathematicians 2014 (ICM 2014). ed. / Sun Young Jang; Young Rock Kim; Dae-Woong Lee; Ikkwon Yie. Seoul : Kyung Moon SA Co. Ltd., 2014. p. 843-869.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

TY - GEN

T1 - Optimization over polynomials

T2 - Selected topics

AU - Laurent, M.

PY - 2014

Y1 - 2014

N2 - Minimizing a polynomial function over a region defined by polynomial inequalitiesmodels broad classes of hard problems from combinatorics, geometry and optimization.New algorithmic approaches have emerged recently for computing the globalminimum, by combining tools from real algebra (sums of squares of polynomials) and functionalanalysis (moments of measures) with semidefinite optimization. Sums of squaresare used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies tosome combinatorial graph problems, and discuss links with other relaxation methods.

AB - Minimizing a polynomial function over a region defined by polynomial inequalitiesmodels broad classes of hard problems from combinatorics, geometry and optimization.New algorithmic approaches have emerged recently for computing the globalminimum, by combining tools from real algebra (sums of squares of polynomials) and functionalanalysis (moments of measures) with semidefinite optimization. Sums of squaresare used to certify positive polynomials, combining an old idea of Hilbert with the recent algorithmic insight that they can be checked efficiently with semidefinite optimization. The dual approach revisits the classical moment problem and leads to algorithmic methods for checking optimality of semidefinite relaxations and extracting global minimizers. We review some selected features of this general methodology, illustrate how it applies tosome combinatorial graph problems, and discuss links with other relaxation methods.

M3 - Conference contribution

SN - 9788961058070

SP - 843

EP - 869

BT - Proceedings of the International Congress of Mathematicians 2014 (ICM 2014)

A2 - Jang, Sun Young

A2 - Kim, Young Rock

A2 - Lee, Dae-Woong

A2 - Yie, Ikkwon

PB - Kyung Moon SA Co. Ltd.

CY - Seoul

ER -

Laurent M. Optimization over polynomials: Selected topics. In Jang SY, Kim YR, Lee D-W, Yie I, editors, Proceedings of the International Congress of Mathematicians 2014 (ICM 2014). Seoul: Kyung Moon SA Co. Ltd. 2014. p. 843-869