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...
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | article |
| Langue: | EN |
| Publié: |
Elsevier
2017
|
| Sujets: | |
| Accès en ligne: | https://doaj.org/article/f7a832f91ebf494a86d3f951e8a7e8fe |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| Résumé: | 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. |
|---|