Classer les méthodes d’optimisation suppose d’abord de fixer un critère de tri. Selon qu’on raisonne par nature du problème, par usage du gradient, par présence de contraintes ou par structure de l’espace de recherche, le nombre de familles varie. Aucune taxonomie ne fait consensus absolu, mais la littérature académique distingue au minimum une dizaine de grandes catégories opérationnelles, chacune ramifiée en variantes algorithmiques.
Méthodes d’optimisation sans contraintes : le socle algorithmique
La distinction la plus structurante sépare les problèmes sans contraintes des problèmes sous contraintes. En l’absence de contraintes, la recherche du minimum d’une fonction repose sur l’exploitation de ses propriétés différentielles.
Lire également : Quel est le salaire d'un testeur ?
Les algorithmes de descente forment le noyau de cette famille. Le principe est itératif : à chaque pas, on choisit une direction de descente et un pas de déplacement. La méthode du gradient (ou steepest descent) utilise l’opposé du gradient comme direction. Sa convergence est linéaire, ce qui la rend lente sur les problèmes mal conditionnés.
Le gradient conjugué améliore cette convergence en construisant des directions conjuguées par rapport à la matrice hessienne, sans la stocker explicitement. Pour les problèmes de grande dimension, c’est un compromis efficace entre coût mémoire et vitesse.
A voir aussi : Comment fonctionne l'optimisation des données ?
La méthode de Newton exploite la hessienne elle-même pour obtenir une convergence quadratique au voisinage de la solution. Son coût par itération est élevé (inversion ou factorisation d’une matrice), ce qui a motivé les méthodes quasi-Newton (BFGS, L-BFGS) qui approchent la hessienne sans la calculer exactement.
Méthodes sans dérivée
Quand la fonction objectif n’est pas différentiable ou que son gradient est inaccessible (boîte noire, simulation coûteuse), on recourt aux méthodes d’optimisation directe. La méthode de Nelder-Mead (simplexe) et les recherches par motifs (pattern search) explorent l’espace sans information de dérivée. Leur convergence est plus lente, mais elles restent applicables là où les méthodes à gradient échouent.
Optimisation sous contraintes : multiplicateurs et pénalisation
La présence de contraintes (égalité, inégalité, ou les deux) change radicalement la structure du problème. Les conditions de Karush-Kuhn-Tucker (KKT) généralisent les conditions d’optimalité au cas contraint.
Deux grandes approches coexistent pour résoudre ces problèmes numériquement :
- Les méthodes de pénalisation transforment le problème contraint en une suite de problèmes sans contraintes, en ajoutant un terme de pénalité à la fonction objectif. Méthodes de pénalité extérieure, intérieure (barrière), et lagrangien augmenté relèvent de cette logique.
- Les méthodes de programmation quadratique séquentielle (SQP) résolvent à chaque itération un sous-problème quadratique local, combinant information du gradient et des contraintes. Elles sont considérées parmi les plus efficaces pour l’optimisation non linéaire sous contraintes.
- Les méthodes de points intérieurs, initialement développées pour la programmation linéaire, s’étendent au cas non linéaire. Elles parcourent l’intérieur de la région admissible en suivant un chemin central.
Programmation linéaire et algorithme du simplexe
Lorsque la fonction objectif et les contraintes sont toutes linéaires, le problème relève de la programmation linéaire. L’algorithme du simplexe, malgré une complexité théorique exponentielle dans le pire cas, reste performant en pratique sur la grande majorité des instances.
Les méthodes de points intérieurs (Karmarkar et ses dérivées) offrent une complexité polynomiale garantie. Nous observons dans la pratique industrielle que le choix entre simplexe et points intérieurs dépend de la taille et de la structure creuse du problème, pas d’une supériorité absolue de l’un sur l’autre.
Extensions : programmation en nombres entiers et optimisation combinatoire
Dès que certaines variables sont entières ou binaires, on bascule dans la programmation en nombres entiers (MILP). Les méthodes exactes (branch-and-bound, branch-and-cut, plans de coupe de Gomory) garantissent l’optimalité mais avec un coût exponentiel dans le pire cas.
L’optimisation combinatoire traite les problèmes à espace de recherche discret et fini, comme le voyageur de commerce ou l’affectation. Les heuristiques et métaheuristiques prennent le relais quand la taille du problème rend les méthodes exactes impraticables.
Métaheuristiques et algorithmes stochastiques
Les métaheuristiques constituent une famille à part. Elles ne garantissent pas l’optimalité globale mais explorent efficacement des espaces de recherche vastes et non convexes.
- Les algorithmes génétiques s’inspirent de la sélection naturelle : population de solutions, croisement, mutation, sélection.
- Le recuit simulé emprunte à la thermodynamique : une température décroissante contrôle la probabilité d’accepter une solution dégradante, ce qui permet d’échapper aux minima locaux.
- L’optimisation par essaim particulaire (PSO) modélise le déplacement collectif d’un groupe de solutions candidates.
- Les algorithmes de colonies de fourmis exploitent un mécanisme de phéromones pour guider la recherche sur des graphes.
Ces méthodes partagent un trait commun : elles introduisent de l’aléatoire pour éviter le piège des minima locaux, au prix d’un paramétrage souvent délicat.
Optimisation convexe : pourquoi cette catégorie structure tout le reste
La convexité n’est pas une méthode, mais elle détermine la difficulté du problème. En optimisation convexe, tout minimum local est global, ce qui simplifie radicalement la résolution. Les méthodes de gradient, de points intérieurs et de sous-gradient convergent vers la solution avec des garanties théoriques solides.
La programmation linéaire est un cas particulier d’optimisation convexe. La programmation semi-définie (SDP) et la programmation conique en sont des extensions. Nous utilisons régulièrement des relaxations convexes pour approcher des problèmes non convexes, en obtenant des bornes inférieures sur la valeur adaptée.
Quand le problème n’est pas convexe, aucune méthode locale ne garantit de trouver le minimum global. C’est précisément ce qui justifie l’existence des métaheuristiques et des méthodes de type branch-and-bound.
Compter les méthodes : un exercice de taxonomie, pas d’arithmétique
Il n’existe pas de nombre fini et arrêté de méthodes d’optimisation. Chaque grande famille (descente, pénalisation, programmation linéaire, combinatoire, métaheuristiques, optimisation convexe) regroupe des dizaines de variantes. Les hybridations entre familles multiplient encore les possibilités.
Le choix d’une méthode dépend de la structure du problème : dimension, convexité, différentiabilité, nature des contraintes, taille de l’espace de recherche. Un problème linéaire à variables continues appelle le simplexe ou un point intérieur. Un problème non convexe en grande dimension avec des variables mixtes relèvera d’une métaheuristique couplée à une relaxation. La question pertinente n’est pas combien de méthodes existent, mais laquelle convient au problème posé.
