La «recherche ternaire» est-elle un terme approprié pour l'algorithme qui optimise une fonction unimodale sur un intervalle réel?

8

Supposons que je veuille optimiser une fonction unimodale définie sur un certain intervalle réel. Je peux utiliser l'algorithme bien connu décrit dans Wikipedia sous le nom de recherche ternaire .

Dans le cas de l'algorithme qui divise de façon répétée les intervalles par deux, il est courant de réserver le terme recherche binaire pour des problèmes discrets et d'utiliser le terme méthode de bissection autrement. En extrapolant cette convention, je soupçonne que le terme méthode de trisection pourrait s'appliquer à l'algorithme qui résout mon problème.

Ma question est de savoir s'il est courant parmi les universitaires et qu'il est sûr de l'utiliser dans, par exemple, des thèses supérieures, pour appliquer le terme recherche ternaire même si l'algorithme est appliqué à un problème continu. J'ai besoin d'une source fiable pour cela. Je suis également intéressé de savoir si le terme méthode de trisection existe réellement.

Pteromys
la source
1
Je ne connais pas la terminologie, mais pourquoi feriez-vous cela? Il n'y a pas beaucoup de temps à gagner en trisectant.
Raphael
4
Je ne m'en inquiéterais pas. Si Wikipédia l'appelle "recherche ternaire", c'est probablement le nom le plus courant, alors utilisez-le. Le pire qui puisse arriver est que votre examinateur vous recommande de le changer en "trisection" tout au long, comme une correction mineure.
David Richerby
@DavidRicherby Je veux en fait utiliser la "trisection" car elle est cohérente avec le cas binaire. Pour ce faire, je dois savoir que le terme est vraiment utilisé.
Pteromys
@Raphael Le problème qui me préoccupe est l'optimisation, et non la recherche de zéros, des fonctions.
Pteromys
2
@Pteromys Il est plus important d'être cohérent avec une utilisation standard qu'avec un autre cas. À moins que quelqu'un ne confirme que la «trisection» est utilisée, respectez la «recherche ternaire» car c'est le seul terme pour lequel vous avez des preuves. (Et, oui, Google n'aide pas parce que vous obtenez un million de visites pour les personnes qui essaient de subdiviser les angles.) "Trisection" peut être un nom avec une meilleure justification, mais vous n'êtes pas en mesure d'inventer de nouveaux noms pour les concepts existants. Vous pourriez ajouter une remarque entre parenthèses mais je n'irais pas plus loin que cela sans preuve d'utilisation.
David Richerby

Réponses:

0

Le mot «recherche bitonique» peut probablement faire référence à ce concept. Voir ce livre et ces notes de cours par exemple.

Hoda
la source
Je ne connaissais pas le mot, mais d'après les sources que vous avez fournies, je peux seulement savoir que le terme est utilisé comme problèmes d'un domaine discret.
Pteromys
2
Tu as raison je n'avais pas remarqué l'accent mis sur la continuité. Alors que diriez-vous de Golden Section Search ?
Hoda
Merci. Le terme «recherche de section d'or» semble explicitement représenter le cas continu. Elle est cependant réservée à un mode particulier de division des intervalles. Je voudrais diviser les intervalles d'une autre manière.
Pteromys
2
@Pteromys, il peut être montré (voir Avriel et Wilde, "Preuve d'optimalité pour la technique de recherche symétrique de Fibonacci", Fibonacci Quarterly 4: 4, 265-269 (octobre 1966)) que la recherche de Fibonacci (étroitement liée à la recherche de la section d'or ) est optimal si vous ne comparez que les valeurs pour plus / moins.
vonbrand
0

Consultez la recherche de Fibonacci et la recherche de section dorée (l'article sur la recherche de Fibonacci parle d'un tableau, mais la technique est vraiment applicable tout comme la recherche de section dorée aux fonctions continues). La recherche de Fibonacci est un tout petit peu plus rapide. L'astuce est que vous pouvez réutiliser les points d'une itération à l'autre. Pour Fibonacci, vous devrez déterminer au préalable le nombre d'itérations. Pas grand-chose, vous savez quand même la précision recherchée.

Il peut être démontré que si vous comparez simplement les valeurs des fonctions pour l'ordre relatif, la recherche de Fibonacci est la plus rapide possible. Si vous considérez les valeurs réelles, une forme de quasi-Newton est plus rapide.

vonbrand
la source