Il est clair que pour minimiser une fonction F non convexe un algorithme de type gradient peut donner de très mauvais résultats : si la fonction comporte beaucoup de minima locaux, on est à peu près certain de rester bloqué sur l'un d'eux. La stratégie des algorithmes de recuit consiste, en effectuant une exploration aléatoire de l'espace d'état, à favoriser les descentes, mais sans interdire tout à fait les remontées. Plus précisément, on se donne une chaine de Markov sur l'espace d'état, et on accepte ou on refuse une transition avec une probabilité 1 si F décroît, et une probabilité égale à
si F croît. Ici T est un paramètre, appelé température par analogie avec la mécanique statistique. Il est clair que plus la température est grande, plus seront facilitées les transitions ascendantes. En revanche, à la limite T=0, on obtient un algorithme de descente. Tout au long de l'algorithme, on va donc faire décroître T, ni trop vite pour ne pas rester bloqué autour d'un minimum local, ni trop lentement si on veut avoir un résultat en un temps raisonnable.