Le programme OBOE

OBOE est un logiciel libre qui permet une mise en oeuvre efficace d'une méthode d'optimisation par oracle.

Cette méthode est particulièrement adaptée à la décomposition des problèmes de grandes tailles et à l'optimisation convexe non différentiable.

Il utilise un code informatique (l'oracle) écrit par l'utilisateur qui lui fournit une information du premier ordre des éléments clés du problème (le support de l'ensemble de réalisabilité et le support de la fonction objectif). OBOE exploite ces informations pour construire le fameux ensemble de localisation qui est une approximation polyhédrique de l'ensemble de solutions réalisables.

Pour implémenter OBOE sur un problème d'optimisation convexe du type "min {f(x) | x in X}", l'utilisateur doit implémenter un oracle avec les spécificités suivantes :

  • donnée d'entrée pour l'oracle : un point d'appel x donné par OBOE.
  • données en sortie de l'oracle :
    • Si x est réalisable, l'oracle retourne la valeur de f(x) et un élément du sousgradient de f en x.
    • Si x n'est pas réalisable, l'oracle retourne un hyperplan séparant x de l'ensemble de réalisabilité X.

Les phases d'optimisation d'OBOE altèrnent avec les phases de calcul de l'oracle jusqu'à ce que le saut d'optimalité relatif soit inférieur à la limite fixée initialement. L'utilisateur peut implémenter d'autres règles d'arrêt de l'algorithme.

Le nouveau point d'appel x choisi par OBOE est le centre analytique. Ce point minimise la fonction barrière logarithmique sur l'ensemble polyhédrique auquel on ajoute un terme additionnel appelé "proximal term". OBOE est une implémentation d'ACCPM, méthode liant plan coupant et centre analytique (Analytic Center Cutting Plane Method).

Vous pouvez téléchargez gratuitement les sources d'OBOE sur le site coin-or.org.