A bounded degree SOS hierarchy for polynomial optimization

We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem (P):f∗=min{f(x):x∈K} on a compact basic semi-algebraic set K⊂Rn. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine’s positivity certificate and some ad...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	JeanB. Lasserre, Kim-Chuan Toh, Shouguang Yang
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2017
Materias:	90C26 90C22 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/f7a832f91ebf494a86d3f951e8a7e8fe
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:f7a832f91ebf494a86d3f951e8a7e8fe
record_format	dspace
spelling	oai:doaj.org-article:f7a832f91ebf494a86d3f951e8a7e8fe2021-12-02T05:00:58ZA bounded degree SOS hierarchy for polynomial optimization2192-440610.1007/s13675-015-0050-yhttps://doaj.org/article/f7a832f91ebf494a86d3f951e8a7e8fe2017-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000757https://doaj.org/toc/2192-4406We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem (P):f∗=min{f(x):x∈K} on a compact basic semi-algebraic set K⊂Rn. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine’s positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) in contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user; (b) in contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems; and (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.JeanB. LasserreKim-Chuan TohShouguang YangElsevierarticle90C2690C22Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 5, Iss 1, Pp 87-117 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C26 90C22 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C26 90C22 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 JeanB. Lasserre Kim-Chuan Toh Shouguang Yang A bounded degree SOS hierarchy for polynomial optimization
description	We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem (P):f∗=min{f(x):x∈K} on a compact basic semi-algebraic set K⊂Rn. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine’s positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) in contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user; (b) in contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems; and (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.
format	article
author	JeanB. Lasserre Kim-Chuan Toh Shouguang Yang
author_facet	JeanB. Lasserre Kim-Chuan Toh Shouguang Yang
author_sort	JeanB. Lasserre
title	A bounded degree SOS hierarchy for polynomial optimization
title_short	A bounded degree SOS hierarchy for polynomial optimization
title_full	A bounded degree SOS hierarchy for polynomial optimization
title_fullStr	A bounded degree SOS hierarchy for polynomial optimization
title_full_unstemmed	A bounded degree SOS hierarchy for polynomial optimization
title_sort	bounded degree sos hierarchy for polynomial optimization
publisher	Elsevier
publishDate	2017
url	https://doaj.org/article/f7a832f91ebf494a86d3f951e8a7e8fe
work_keys_str_mv	AT jeanblasserre aboundeddegreesoshierarchyforpolynomialoptimization AT kimchuantoh aboundeddegreesoshierarchyforpolynomialoptimization AT shouguangyang aboundeddegreesoshierarchyforpolynomialoptimization AT jeanblasserre boundeddegreesoshierarchyforpolynomialoptimization AT kimchuantoh boundeddegreesoshierarchyforpolynomialoptimization AT shouguangyang boundeddegreesoshierarchyforpolynomialoptimization
_version_	1718400867137224704

A bounded degree SOS hierarchy for polynomial optimization

Ejemplares similares