Méthode du nombre d'or

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 }}}$.

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 milieu 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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Golden section search » (voir la liste des auteurs).

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting

• Portail des mathématiques