HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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

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$.
Document type :
Journal articles
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download

https://hal.inria.fr/hal-00778239
Contributor : Mohab Safey El Din Connect in order to contact the contributor
Submitted on : Saturday, January 19, 2013 - 9:28:34 AM
Last modification on : Friday, January 21, 2022 - 3:15:41 AM
Long-term archiving on: : Saturday, April 20, 2013 - 3:53:22 AM

File

sos_vcg_final.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

386

Files downloads

173