Global optimization of polynomials restricted to a smooth variety using sums of squares

4 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let $f_1,\dots,f_p$ be in $\Q[\bfX]$, where $\bfX=(X_1,\dots,X_n)^t$, that generate a radical ideal and let $V$ be their complex zero-set. Assume that $V$ is smooth and equidimensional. Given $f\in\Q[\bfX]$ bounded below, consider the optimization problem of computing $f^\star=\inf_{x\in V\cap\R^n} f(x)$. For $\bfA\in GL_n(\C)$, we denote by $f^\bfA$ the polynomial $f(\bfA\bfX)$ and by $V^\bfA$ the complex zero-set of $f_1^\bfA,\ldots,f_p^\bfA$. We construct families of polynomials ${\sf M}^\bfA_0, \ldots, {\sf M}^\bfA_d$ in $\Q[\bfX]$: each ${\sf M}_i^\bfA$ is related to the section of a linear subspace with the critical locus of a linear projection. We prove that there exists a non-empty Zariski-open set $\mathscr{O}\subset GL_n(\C)$ such that for all $\bfA\in \mathscr{O}\cap GL_n(\Q)$, $f(x)$ is non-negative for all $x\in V\cap\R^n$ if, and only if, $f^\bfA$ can be expressed as a sum of squares of polynomials on the truncated variety generated by the ideal $\langle {\sf M}^\bfA_i\rangle$, for $0\leq i \leq d$. Hence, we can obtain algebraic certificates for lower bounds on $f^\star$ using semidefinite programs. Some numerical experiments are given. We also discuss how to decrease the number of polynomials in ${\sf M}^\bfA_i$.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2012, 47 (5), pp.503-518. <10.1016/j.jsc.2011.12.003>
Domaine :

https://hal.inria.fr/hal-00778239
Contributeur : Mohab Safey El Din <>
Soumis le : samedi 19 janvier 2013 - 09:28:34
Dernière modification le : mardi 13 juin 2017 - 17:01:46
Document(s) archivé(s) le : samedi 20 avril 2013 - 03:53:22

Fichier

sos_vcg_final.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Aurélien Greuet, Feng Guo, Mohab Safey El Din, Lihong Zhi. Global optimization of polynomials restricted to a smooth variety using sums of squares. Journal of Symbolic Computation, Elsevier, 2012, 47 (5), pp.503-518. <10.1016/j.jsc.2011.12.003>. <hal-00778239>

Consultations de
la notice

208

Téléchargements du document