Strong duality in Lasserre’s hierarchy for polynomial optimization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00237256" target="_blank" >RIV/68407700:21230/16:00237256 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s11590-015-0868-5" target="_blank" >http://dx.doi.org/10.1007/s11590-015-0868-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11590-015-0868-5" target="_blank" >10.1007/s11590-015-0868-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Strong duality in Lasserre’s hierarchy for polynomial optimization

Popis výsledku v původním jazyce

A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $$K$$K described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J. B. Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, we show that there is no duality gap between each primal and dual SDP problem in Lasserre’s hierarchy, provided one of the constraints in the description of set $$K$$K is a ball constraint. Our proof uses elementary results on SDP duality, and it does not assume that $$K$$K has a strictly feasible point.

Název v anglickém jazyce

Strong duality in Lasserre’s hierarchy for polynomial optimization

Popis výsledku anglicky

A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $$K$$K described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J. B. Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, we show that there is no duality gap between each primal and dual SDP problem in Lasserre’s hierarchy, provided one of the constraints in the description of set $$K$$K is a ball constraint. Our proof uses elementary results on SDP duality, and it does not assume that $$K$$K has a strictly feasible point.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Optimization Letters

ISSN

1862-4472

e-ISSN

—

Svazek periodika

10

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

8

Strana od-do

3-10

Kód UT WoS článku

000367895900002

EID výsledku v databázi Scopus

2-s2.0-84953836305