Minimisation de fonctions non convexes

Beaucoup de problèmes complexes peuvent être modélisés à l'aide de fonctions non convexes. Par exemple, une tournée de distribution de colis par un livreur peut se modéliser par le Problème du voyageur de commerce qui est une modélisation courante de ce type de problème. Le Problème SAT est un autre exemple de problème ne pouvant pas être résolu en utilisant une fonction convexe.

Une fonction non convexe est une fonction qui admet un optimal global ainsi que des optimaux locaux. Ce type de fonction pose problème lorsqu’il s’agit de les minimiser car les algorithmes traditionnels ont tendance à tomber dans ces optimaux locaux, et donc d’autres techniques doivent être mises en place afin de leur échapper et de trouver l’optimal global. Cependant, une résolution mathématique n’est souvent pas possible car ces fonctions ne sont pas dérivables.

Dans le cas d’une fonction discrète relativement petite, il est possible de faire une recherche totale du minimal, simplement en parcourant l’ensemble des solutions. Par exemple le Problème du sac à dos utilise la Programmation dynamique pour trouver des solutions.

Pour les problèmes plus complexes, il est nécessaire d’utiliser des approches non exhaustives.

Mesurer la qualité d’un algorithme dans le cas général est très difficile . Comme les performances des heuristiques dépendent directement du problème, il est difficile de réaliser des expériences avec un nombre limité de problèmes qui soit représentatif du cas général.

Sans a priori sur le problème que l’on souhaite résoudre, les résultats obtenus par différents algorithmes seront les mêmes (voir No Free Lunch Theorem (en)^[1])

C’est pourquoi le choix d’un algorithme est directement lié aux caractéristiques du problème : domaine de définition, problème discret ou continu, dimension, modélisation.

On définit les problèmes continus comme des problèmes dont la 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.

• Portail des mathématiques
• Portail de l’informatique