Optimisation

Dans plusieurs problèmes, on doit maximiser (ou minimiser) une fonction. On peut aussi devoir résoudre une équation pour une inconnue. Prenons un problème tout simple d’optimisation

\[\max_x x (a - b x)\]

Bien sur la CPO de ce problème est

\[a-2bx = 0\]

et donc la solution est \(x^* = \frac{a}{2b}\). C’est la solution analytique. On peut la programmer directement:

def xstar(a,b):
    return a/2*b

xstar(10,1)

5.0

Parfois, la solution n’est pas disponible analytiquement. Alors on a le problème

\[\max_x g(x)\]

Et donc la CPO

\[g'_x(x^*) = 0\]

Comment résoudre ce problème?

Résoudre par la condition de premier ordre

D’abord, on peut résoudre la condition de premier ordre si celle-ci est disponible analytiquement. On utilise alors le module scipy et en particulier son sous-module optimize. Une algorithme simple qui permet de résoudre cette équation est la bisection (bisect):

from scipy.optimize import bisect

Utilisons l’exemple ici-haut, on a

def g(x,a,b):
    return a - 2*b*x

On utilise partial de functools pour concentrer les arguments

from functools import partial

f = partial(g,a=10,b=1)

Ne reste qu’à trouver le zéro de cette fonction avec bisect:

bisect(f,0,10)

5.0

On peut encapsuler tout ceci dans une fonction

def xstar(a,b):
    f = partial(g,a=a,b=b)
    return bisect(f,0,a)

xstar(10,1)

5.0

Optimiser directement

Le module scipy a des fonctions pour minimiser. Si on veut maximiser, on a qu’a minimiser le négatif d’une fonction,

\[\argmax_x f(x) = \argmin_x -f(x)\]

Alors, on utilise la fonction minimize_scalar:

from scipy.optimize import minimize_scalar

def g(x,a,b):
    return x*(a - b*x)

f = partial(g,a=10,b=1)

Pour changer le signe de la fonction, on en fait une nouvelle à l’aide de la commande pour créer des fonctions simples lambda:

fm = lambda x: -f(x)

La fonction minimize_scalar retourne un objet qui contient la solution et d’autres informations. La variable x contient la solution.

opt = minimize_scalar(fm,bracket=[0,10])
opt

     fun: -25.0
    nfev: 9
     nit: 5
 success: True
       x: 5.0

opt.x

5.0

Encapsulons:

def xstar(a,b):
    f = partial(g,a=10,b=1)
    fm = lambda x: -f(x)
    opt = minimize_scalar(fm,bracket=[0,a])
    return opt.x

xstar(10.0,1.0)

5.0

Les fonctions d’optimisation de scipy sont puissantes et nombreuses. La fonction minimize permet de trouver des optimums avec plusieurs variables. Il existe aussi des packages plus puissant, tel que nlopt, qui peuvent aider avec les problèmes plus complexes.