In this thesis, we shall rely on the so-called critical point method to compute an exact representation of the infimum of a polynomial restricted to an algebraic set. Firstly, we demonstrate an improvement in the complexity of computing the critical values by a close study of Gröbner bases computations. Using these techniques, we lay out a methodology to study many related problems, including some that arise in the popular sums of squares (SOS) approach to polynomial optimisation. Then, the framework allowing one to handle non-compact domains relies on generalised critical values which give a generalisation of Ehresmann’s fibration theorem to non-proper situations. Following the works of Kurdyka, Orro and Simon, we design efficient algorithms for computing said values within time singly exponential in the dimension of the ambient space. Finally, we give the first steps towards an understanding of the algebraic structure of SOS decompositions of polynomials.