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
Bien sur la CPO de ce problème est
et donc la solution est \(x^* = \frac{a}{2b}\). C’est la solution analytique. On peut la programmer directement:
[1]:
def xstar(a,b):
return a/2*b
xstar(10,1)
[1]:
5.0
Parfois, la solution n’est pas disponible analytiquement. Alors on a le problème
Et donc la CPO
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
):
[2]:
from scipy.optimize import bisect
Utilisons l’exemple ici-haut, on a
[3]:
def g(x,a,b):
return a - 2*b*x
On utilise partial
de functools pour concentrer les arguments
[4]:
from functools import partial
f = partial(g,a=10,b=1)
Ne reste qu’à trouver le zéro de cette fonction avec bisect:
[5]:
bisect(f,0,10)
[5]:
5.0
On peut encapsuler tout ceci dans une fonction
[7]:
def xstar(a,b):
f = partial(g,a=a,b=b)
return bisect(f,0,a)
xstar(10,1)
[7]:
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,
Alors, on utilise la fonction minimize_scalar
:
[14]:
from scipy.optimize import minimize_scalar
[15]:
def g(x,a,b):
return x*(a - b*x)
[16]:
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
:
[17]:
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.
[20]:
opt = minimize_scalar(fm,bracket=[0,10])
opt
[20]:
fun: -25.0
nfev: 9
nit: 5
success: True
x: 5.0
[21]:
opt.x
[21]:
5.0
Encapsulons:
[22]:
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
[23]:
xstar(10.0,1.0)
[23]:
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.