Minimisation de fonctions non convexes

On définit les problèmes continus comme des problèmes dont leur fonction objectif est continue. Leur difficulté réside surtout dans l'espace de définition qui est infini. Cependant, on peut se restreindre à un espace borné afin de pouvoir minimiser certaines fonctions.

Algorithme du gradient stochastique : Le gradient d’une fonction différentiable de score est égal à la somme des gradients des fonctions élémentaires qui la composent[2].

Par exemple, dans l'étude cinétique chimique, une telle optimisation peut être mise en place.

Méthode de Nelder-Mead[3] : il s’agit d'utiliser un simplexe polytope sur lequel on effectue des transformations pour que les sommets se rapprochent d’un minimal. Cette méthode simple assure une décroissance de la solution trouvée.

Attention toutefois, l’algorithme peut être inefficace dans le cas où le problème est défini dans l’ensemble complexe, ou lorsque le nombre de dimensions augmente.

Lorsque le problème est une variable régionalisée, par exemple la topographie d'une ville, Krigeage[4] s'avère extrêmement efficace car cette technique permet une estimation de la fonction avec une très faible variance.

La particularité des problèmes discrets est la garantie qu’il existe une ou plusieurs solutions optimales globales. Il est alors possible d’utiliser des algorithmes de recherche qui garantissent une solution optimale, et d’autres qui garantissent un temps de recherche convenable en contrepartie d'une solution approchée. Les méthodes de recherches exactes ne peuvent pas être applicables en temps raisonnable sur des problèmes de grande taille. On parle alors d'explosion combinatoire.

La majorité des méthodes de résolution exactes se base sur de la programmation dynamique. Les méthodes les plus utilisées sont :

• Séparation et évaluation (Branch-and-Bound) : Cette méthode représente les solutions sous forme d’un arbre. L’algorithme estime les bornes minimales et maximales de l’ensemble des solutions du sous-arbre afin de ne pas les parcourir s’il est garanti que la solution optimale n’y est pas.
• Branch-and-cut[5] : Cet algorithme ajoute au Branch-and-Bound la méthode Cutting-plane afin de déterminer les régions faisables via programmation linéaire.

Les heuristiques sont spécifiques aux problèmes, elles nécessitent donc une bonne connaissance de ces derniers. Beaucoup d'entre elles reposent sur les algorithmes gloutons.

Voici quelques heuristiques pour des problèmes connus : TSP[6], Knapsack[7].

Les méta-heuristiques fournissent un framework pour résoudre différents types de problèmes. Cependant, il est nécessaire d’adapter certaines fonctions (parcours du voisinage, opérateur d'enjambement, mutation, etc.) au problème à résoudre.

Les méta-heuristiques peuvent être classifiées selon divers critères : population, mémoire, parcours, etc.[8] - [9]

Les méta-heuristiques reposent sur le principe de diversification-intensification : les différentes méthodes doivent combiner ces deux aspects afin d'explorer efficacement l'espace de recherche tout en se rapprochant des solutions optimales.

Même si l’efficacité des heuristiques dépend fortement des problèmes et des instances, des efforts sont faits pour tenter de les comparer[10] : AMALGAM[11] ou CMA-ES semble donner de bon résultat sur des instances de grande taille.

À la différence des méta-heuristiques, les hyper-heuristiques (en) travaillent sur l'espace de recherche des heuristiques au lieu de travailler sur l'espace des solutions. Les hyper-heuristiques permettent d'automatiser le réglage des méta-heuristiques utilisées.