Minimum d'une "fonction très oscillante"

Scientifix · March 2021

REGARDER A PARTIR DU 4EME MESSAGE

Bonjour à tous
Je suis confronté au problème d'analyse/analyse numérique suivant.

Je cherche le minimum d'une fonction qui oscille énormément sur de tout petits intervalles (variations de forte fréquence et de forte amplitude - du simple au centuple - sur un intervalle de largeur 10^(-5)).

N'ayant pas de moyen d'estimer facilement où pourrait se situer ce minimum, je dois commencer ma recherche sur un intervalle dont la largeur a pour ordre de grandeur 10^(-2) ...

J'utilise pour le moment un genre de dichotomie à pas dégressif (on commence sur un intervalle large avec un pas de l'ordre de 10^(-4) puis on affine l'intervalle et le pas successivement) mais cela est loin d'être optimal (lent/coûteux en calculs, possible de louper le min...).
L'un d'entre vous aurait-il une stratégie ou connaîtrait-il un algorithme adapté pour ce genre de situations ?
Merci beaucoup d'avance,
Scientifix

AlainLyon · March 2021

Bonjour, as-tu essayé une transformée en ondelettes ?

Scientifix · March 2021

Bonjour,
Merci pour l'idée !! Je vais regarder comment utiliser ça.
Ma seule crainte est que la fonction que je veux minimiser soit trop chaotique et qu'il n'y a pas vraiment de séparation entre "tendance générale" et "bruit".

Pour être un peu plus précis voici ce qui se passe en arrière plan :

1/ Je choisis une condition initiale $f(0)$ pour une equa diff ($f'(0)$ a une forme imposée et découle du choix de $f(0)$)
2/ Après résolution sur un interval donné, les valeurs finales de la solution (fonction et sa dérivée) sont utilisées comme conditions initiales pour une autre equa diff sur l'intervalle suivant, etc... Le processus est répété $n$ fois.
3/ La valeur de la condition finale sur la dérivée en fin de parcours est donnée par la physique du problème. Je compare alors la dérivée finale que j'ai calculée et celle qui est attendue. Si l'écart est trop grand, on change $f(0)$ en début de parcours.

La fonction que je veux minimiser est la fonction qui me donne l'écart entre la valeur finale de dérivé attendue et calculée pour une condition initiale $f(0)$.

Comme expliqué plus haut cette fonction est assez chaotique et une méthode de minimisation "à la Newton" ne fonctionne pas bien car se fait piéger dans des oscillations de haute fréquence et amplitude...

Désolé pour le long post expliqué "avec les mains" et sans trop de formalisme...

Scientifix · April 2021

ICI

Bonjour à tous,

J'ai réussi à modifier mon problème afin de me ramener à la situation plus simple :

La fonction dont je dois trouver le minimum est maintenant constante partout sauf "en un puit très profond et très étroit" (imaginer $f$ définie sur $I=[a,b]$ avec $x_0\in]a,b[$ tel que $\forall x\in I\setminus \{x_0\}, \;f(x)=10$ et $f(x_0)=0$ par exemple).

J'utilise pour le moment la méthode très simple suivante (l'expression de la fonction n'est pas connue) :

- partir de $\alpha_0 = b$ avec un pas $\gamma$
- si $f(\alpha_{i+1}) - f(\alpha_{i}) \leq 0$, $\alpha_{i+2} = \alpha_{i+1} - \gamma$
- sinon $\gamma = \gamma/2$ et $\alpha_{i+2} = \alpha_{i+1} + \gamma$

Méthode peu pratique au niveau du choix du pas... je vais tester un pas adaptatif pondéré par la variation de la dérivée et autres méthodes de descente classiques ;-).
Des idées de méthodes plus évoluées ?

Merci !!

gerard0 · April 2021

Dans ton exemple, aucune méthode ne trouvera la minimum sauf par hasard. Par exemple avec a=0, b=10 et $x_0=\pi$, tout travail avec des valeurs approchées décimales (ou binaires) passera à côté du minimum.

Plus gênant, si tu as des minimums relatifs avec des variations moins brusques, ce sont eux qui risquent d'être détectés. C'est un grand classique des algorithmes de recherche de minimums (d'où les méthodes de "recuit simulé").
A une époque, la mode a été aussi aux "algorithmes génétiques".

Cordialement.

Scientifix · April 2021

Bonsoir et merci pour la réponse !

Oui l'exemple que j'ai donné plus haut est un cas trop limite. L'exemple suivant est plus réaliste :
$f_n$ définie sur $I=[a,b]$ avec $x_0\in]a,b[$ tel que $\forall x\in [a,x_0[, \;f_n(x)=10$, $\forall x\in [x_0,x_0+\frac{1}{n}[, \;f_n(x)=10n(x-x_0)$ et $\forall x\in [x_0+\frac{1}{n},b], \;f_n(x)=10$ par exemple.

La fonction que je cherche à minimiser n'a pas de minima locaux, elle est quasi identique à l'exemple ci-dessus à la linéarité près. C'est pourquoi je pensais pondérer mon pas par la dérivée : quand on arrive dans le "creux" on peut diviser le pas par $10n$ par exemple et ralentir la descente... mais pas fameux

D'autres idées de méthodes (Transformée de Fourier, etc...) ?

Héhéhé · April 2021

Qu'est-ce que tu connais exactement sur ta fonction $f$ ? Vu que son expression n'est pas connue, je ne vois pas tellement comment utiliser des méthodes style Fourier (comment faire pour calculer ses coefficients de Fourier par exemple ? et si on veut le faire numériquement, on retombe sur le même problème quand on discrétise pour évaluer numériquement des intégrales...).

Scientifix · April 2021

Merci pour la réponse !
C'est bien le problème... le processus qui génère mes valeurs est extrêmement compliqué (succession d'équations différentielles qui se passent des conditions limites de proche en proche) ce qui rend toutes méthodes nécessitant de connaitre l'expression de $f$ caduques :-(
La seule chose que je sais, c'est que ma fonction est strictement croissante sur $]x_0,x_0+1/n]$, constante sur $[x_0+1/n,b]$ et a son minimum en $x_0$.
D'où mon idée de partir depuis $b$ et de descendre en réduisant mon pas au fur et à mesure que la pente de mon "puit" augmente.

Dreamer · April 2021

Bonjour.

Je crois comprendre que la fonction en question est un pur produit d'Analyse Numérique.

Scientifix, as-tu évalué le conditionnement de cette fonction ?

Tu parles d'un système d'équations différentielles, s'il est mal conditionné l'erreur d'évaluation peut vite avoir un comportement chaotique comme tu le décris.

Cordialement.

Héhéhé · April 2021

Dans ce cas là, je ne vois guère que des méthodes empiriques qui peuvent marcher...

Minimum d'une "fonction très oscillante"

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 31