Critical Points and Gröbner Bases: the Unmixed Case

Jean-Charles Faugère 1, 2 Mohab Safey El Din 1, 2 Pierre-Jean Spaenlehauer 1, 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...). Critical points also play a central role in recent algorithms of effective real algebraic geometry. Experimentally, it has been observed that Gröbner basis algorithms are efficient to compute such points. Therefore, recent software based on the so-called Critical Point Method are built on Gröbner bases engines. Let $f_1,..., f_p$ be polynomials in $ \Q[x_1,..., x_n]$ of degree $D$, $V\subset\C^n$ be their complex variety and $\pi_1$ be the projection map $(x_1,.., x_n)\mapsto x_1$. The critical points of the restriction of $\pi_1$ to $V$ are defined by the vanishing of $f_1,..., f_p$ and some maximal minors of the Jacobian matrix associated to $f_1,..., f_p$. Such a system is algebraically structured: the ideal it generates is the sum of a determinantal ideal and the ideal generated by $f_1,..., f_p$. We provide the first complexity estimates on the computation of Gröbner bases of such systems defining critical points. We prove that under genericity assumptions on $f_1,..., f_p$, the complexity is polynomial in the generic number of critical points, i.e. $D^p(D-1)^{n-p}{{n-1}\choose{p-1}}$. More particularly, in the quadratic case D=2, the complexity of such a Gröbner basis computation is polynomial in the number of variables $n$ and exponential in $p$. We also give experimental evidence supporting these theoretical results.
Type de document :
Communication dans un congrès
ISSAC 2012 - International Symposium on Symbolic and Algebraic Computation - 2012, Jul 2012, Grenoble, France. ACM, pp.162-169, 2012, 〈10.1145/2442829.2442855〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00667494
Contributeur : Pierre-Jean Spaenlehauer <>
Soumis le : mardi 7 février 2012 - 17:23:05
Dernière modification le : vendredi 25 mai 2018 - 12:02:06

Lien texte intégral

Identifiants

Collections

Citation

Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer. Critical Points and Gröbner Bases: the Unmixed Case. ISSAC 2012 - International Symposium on Symbolic and Algebraic Computation - 2012, Jul 2012, Grenoble, France. ACM, pp.162-169, 2012, 〈10.1145/2442829.2442855〉. 〈hal-00667494〉

Partager

Métriques

Consultations de la notice

194