  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\"obner basis
algorithms are efficient to compute such points. Therefore, recent software
based on the so-called Critical Point Method are built on Gr\"obner 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\"obner 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\"obner basis computation is
polynomial in the number of variables $n$ and exponential in $p$. We also give
experimental evidence supporting these theoretical results.
