Cet article ne cite pas suffisamment ses sources (octobre 2025).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Les algorithmes d’optimisation cherchent à déterminer le jeu de paramètres d’entrée d’une fonction donnant à cette fonction la valeur maximale ou minimale. On cherchera, par exemple, la découpe optimale d’une tôle pour en fabriquer le plus grand nombre de boîtes de conserve possible (ou d’un tissu pour en faire le plus grand nombre de chemises possibles, etc.). Cette optimisation peut se faire sans contrainte ou sous contrainte, le second cas se ramenant au premier dans le cas des fonctions dérivables par la méthode du multiplicateur de Lagrange (et des fonctions non-dérivables par l’algorithme d’Everett).

Le problème est insoluble en tant que tel si l’on ne connaît rien de la fonction (il existe peut-être une combinaison très particulière de valeurs d’entrées lui donnant ponctuellement une valeur extrêmement haute ou basse, qui pourrait échapper à l’algorithme. Aussi existe-t-il plusieurs classes d’algorithmes liés aux différentes connaissances qu’on peut avoir sur la fonction. Si celle-ci est dérivable, l’une des plus performantes est celle du gradient conjugué.

Aucune méthode connue en 2004 (à part l’énumération exhaustive ou l’analyse algébrique) ne permet de trouver avec certitude un extremum global d’une fonction. Les extrema déterminables sont toujours locaux à un domaine, et demandent souvent même en ce cas quelques caractéristiques à la fonction, par exemple dans certains cas la continuité.

Les métaheuristiques sont une classe d’algorithmes d’optimisation qui tentent d’obtenir une valeur approchée de l’optimum global dans le cas de problèmes d’optimisation difficile. Elles ne donnent cependant aucune garantie sur la fiabilité du résultat.

• Soit A l’algorithme du problème d’optimisation associé au problème de décision P.
• ${\displaystyle Opt(i)}$ est la solution optimale pour l’instance i du problème P.
• ${\displaystyle Cout(i)}$ est la valeur k' de la solution j.
• A est polynomial et on a :
• A : ${\displaystyle I(P)\rightarrow S:i\rightarrow j\in s(i)}$, tel que ${\displaystyle C_{P}(i,j)=oui}$.
• ${\displaystyle \exists }$ c, constante ne dépendant pas de i, telle que:

${\displaystyle \forall i\in I(P),{\frac {Cout(A(i))}{Opt(i)}}\leq c}$

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

• (en) X. S. Yang, « Optimization Algorithms », dans Slawomir Koziel, Computational Optimization, Methods and Algorithms. Studies in Computational Intelligence, vol. 356, Berlin, Springer Berlin Heidelberg, 2011 (DOI 10.1007/978-3-642-20859-1_2), p. 13-31.

v · m Optimisation : théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting

• Portail de l'informatique théorique