Méthode du nombre d'or

La méthode du nombre d'or est un algorithme d'optimisation, c'est-à-dire de recherche de l'extremum d'une fonction, dans le cas d'une fonction unimodale, c'est-à-dire dans lequel l'extremum global recherché est le seul extremum local. S'il existe plusieurs extrema locaux, l'algorithme donne un extremum local, sans qu'il soit garanti que ce soit l'extremum absolu. Cet algorithme, ainsi que la méthode de Fibonacci, ont été mis au point par le statisticien Kiefer^[1],[2].

Principe de base

Principe de base de la méthode.

Considérons une fonction réelle ƒ. On a calculé sa valeur en trois points, x₁, x₂ et x₃, avec x₁ < x₂ < x₃ ; ceci est représenté sur le dessin ci-contre, avec y = ƒ(x).

Supposons que l'on ait ƒ(x₂) < ƒ(x₁) et ƒ(x₂) < ƒ(x₃) ; comme la fonction est unimodale, on sait que le minimum est dans l'intervalle ]x₁ ; x₃[. On « sonde » la fonction en prenant un point x₄ dans cet intervalle, afin de réduire l'intervalle de recherche.

On peut prendre x₄ dans ]x₁ ; x₂[ ou bien dans ]x₂ ; x₃[ ; il est plus « rentable » de le prendre dans l'intervalle le plus grand, ici ]x₂ ; x₃[. Selon la valeur de ƒ(x₄), alors :

• cas a : ƒ(x_4a) > ƒ(x₂), on sait que le minimum se trouve dans ]x₁ ; x₄[ ;
• cas b : ƒ(x_4b) < ƒ(x₂), on sait que le minimum se trouve dans ]x₂ ; x₃[.

On procède ensuite de manière récursive. L'algorithme n'est pas très différent d'une recherche dichotomique, mais le choix des points utilise le nombre d'or plutôt que le nombre 2.

La mise en œuvre de la méthode doit prévoir le cas où ƒ(x₄) = ƒ(x₂), et notamment le cas extrême où la fonction est uniforme sur ]x₁ ; x₃[ ; ce n'est pas un cas unimodal, donc hors des hypothèses de l'algorithme, mais la recherche est en général lancée sans connaître le nombre de modes de la fonction.

Choix de la sonde

La particularité de la méthode est de choisir la sonde x₄ telle que les deux segments possibles, ]x₁ ; x₄[ ou ]x₂ ; x₃[, aient la même longueur. Sinon, on pourrait par « malchance » avoir une convergence lente. On choisit donc

x₄ - x₁ = x₃ - x₂

soit

x₄ = x₁ + (x₃ - x₂).

Si l'on désire toujours garder la même proportion entre la largeur du segment à l'étape i et celle à l'étape i + 1, alors dans le cas a, il faut

${\displaystyle {\frac {x_{4}-x_{2}}{x_{2}-x_{1}}}={\frac {x_{2}-x_{1}}{x_{3}-x_{2}}}}$

ou, avec les notations introduites sur la figure :

${\displaystyle {\frac {c}{a}}={\frac {a}{b}}}$

et dans le cas b :

${\displaystyle {\frac {c}{b-c}}={\frac {a}{b}}}$

En éliminant c dans ces équations, on obtient

${\displaystyle \left({\frac {b}{a}}\right)^{2}={\frac {b}{a}}+1}$

ce qui donne le nombre d'or φ :

${\displaystyle {\frac {b}{a}}=\varphi }$

Si l'intervalle de départ est [x₁ ; x₃], alors la première sonde est prise en

${\displaystyle x_{2}=x_{1}+{\frac {x_{3}-x_{1}}{1+\varphi }}}$.

Algorithme

Il est possible de coder la méthode du nombre d'or de façon itérative ou récursive.

Voici un exemple de code écrit en python qui utilise la manière itérative

# Golden-section search
# Algorithme permettant de trouver le minimum d'une fonction continue sur un intervalle donné

import math 

phi = (1 + math.sqrt(5)) / 2  # Nombre d'or

def f(x): # On met une fonction dont on cherche le minimum
    return 0.2*x**3 - 6*x + 8

def methode_du_nombre_dor(a, b, epsilon): # a et b borne de l'intervalle dans le sens croissant, epsilon la précision de l'intervalle

    if a >= b: # Verification de l'intervalle
        return "L'intervalle doit être dans le sens croissant."
    
    # Initialisation des points intérieurs
    c = b + (a - b) / phi
    d = a + (b - a) / phi
    
    while abs(b - a) > epsilon: # Tant que la precision n'est pas atteinte :
        
        if f(c) < f(d): # Si f(x) est plus petit que f(d), d devient le nouveau b
            b = d
        else: # Sinon c devient le nouveau a
            a = c
        
        # On met ensuite à jour les points c et d
        c = b - (b - a) / phi
        d = a + (b - a) / phi
    
    return (a + b) / 2  # On retourne le millieu de l'intervalle final

# Test de la fonction
# Ps : Après étude, on sait que cette fonction n'admet qu'un minimum sur l'intervalle [0, 5]
print(methode_du_nombre_dor(0, 5, 0.001))  # On cherche le minimum de f(x) sur l'intervalle [0, 5] avec une précision de 0.001
# On obtient environ 3.16, ce qui effictivement le mininum de la fonction f sur cet intervalle