Algorithme

[ice456]

Bonjour,

je ne comprends pas trop un algorithme de recherche de minimum...

Voici l'algorithme en question :

http://en.wikipedia.org/wiki/Golden_section_search

Dans l'exemple donné je ne vois pas trop comment choisir les points x2 et x4..

Merci pour votre aide

[alavacommejetepousse]

bonjour

c'est explicitement écrit

x1 et x3 sont initialement les extrémités de l'intervalle sur lequel on fait la recherche et x2 est choisi avec " the golden ratio"
b/a = phi

[ice456]

Donc si je comprends bien , au départ on a un intervalle [x1,x3] et il faut choisir le point x2 de tel manière que la distance entre x1 et x2 soit proportienelle à la distance qui sépare x2 et x3... avec comme facteur proportienelle le golden ratio ?

Donc on aurait c'est ça?

[alavacommejetepousse]

absolument

[ice456]

Ok merci beaucoup j'ai compris le principe :we:

[alavacommejetepousse]

moi aussi j'ai compris le principe ( je le croyais du moins) mais me vient une interrogation et si au point x2 imposé f prend un valeur supéreure à
f(x1) ou f(x2) ?

[ice456]

Tu veux dire que si f(x2) est supérieur a f(x1) et f(x3)?

Dans ce cas là alors le minimum se trouve au bord enfin du moins je pense

[ice456]

J'ai une petite question concernant la recherche du tout premier x2.

On a donc l'interval [x1,x3] de départ dans lequelle il faut trouver un minimum.

L'hypothèse si je comprends bien pour qu'il y est un minimum dans ]x1,x3[ c'est qu'on peut trouver un x2 ]x1,x3[ tel que f(x2) f(x1) et f(x2) f(x3).

Si x2 ne peut pas être trouver alors le minimum est minimum{f(x1),f(x3)}.

Ma question est comment trouver ce premier x2?

Au départ je prenais mon tout premier x2 tel que mais ce choix n'est pas toujours valable.

En effet il se peut que si on aurait prits la moitié de l'interval [x1,x3] on aurait trouver un x2 qui marchait....

J'espère avoir été assez claire.

Pourriez-vous m'aidé sur cette algorithme?

Merci beaucoup

[ice456]

J'ai une autre question concernant les combinaisons convexes :

on choisit de chercher x4 dans le plus grand des intervals [x1,x2] ou [x2,x3].

Dans le cas où c'est [x2,x3], on veut x4 tel que
Il faut montrer que x4 détermine bien une combinaison convexe (1-)x1 + x3.

J'isole donc x4 dans l'égalité donnée et j'obtien = 0,618.

Ensuite il nous est demandé de donner x4 comme combinaison convexe de x1 et x3 dans le cas où c'est l'intervalle [x1,x2] qui est le plus grand.

Je ne suis pas sur de ma réponse : j'aurais répondu (1-)x3 + x1 et donc
Est-ce correct?

MErci

[ice456]

J'ai une autre question concernant les combinaisons convexes :

on choisit de chercher x4 dans le plus grand des intervals [x1,x2] ou [x2,x3].

Dans le cas où c'est [x2,x3], on veut x4 tel que \frac{|x4-x1|}{|x4-x3|} = \frac{1+\sqrt{5}}{2}.

Il faut montrer que x4 détermine bien une combinaison convexe (1-)x1 + x3.

J'isole donc x4 dans l'égalité donnée et j'obtien = 0,618.

Ensuite il nous est demandé de donner x4 comme combinaison convexe de x1 et x3 dans le cas où c'est l'intervalle [x1,x2] qui est le plus grand.

Je ne suis pas sur de ma réponse : j'aurais répondu (1-)x3 + x1 et donc
Est-ce correct?

MErci

[ice456]

J'ai une autre question concernant les combinaisons convexes :

on choisit de chercher x4 dans le plus grand des intervals [x1,x2] ou [x2,x3].

Dans le cas où c'est [x2,x3], on veut x4 tel que
Il faut montrer que x4 détermine bien une combinaison convexe (1-)x1 + x3.

J'isole donc x4 dans l'égalité donnée et j'obtien = 0,618.

Ensuite il nous est demandé de donner x4 comme combinaison convexe de x1 et x3 dans le cas où c'est l'intervalle [x1,x2] qui est le plus grand.

Je ne suis pas sur de ma réponse : j'aurais répondu (1-)x3 + x1 et donc
Est-ce correct?

MErci

[ice456]

J'ai une autre question concernant les combinaisons convexes :

on choisit de chercher x4 dans le plus grand des intervals [x1,x2] ou [x2,x3].

Dans le cas où c'est [x2,x3], on veut x4 tel que
Il faut montrer que x4 détermine bien une combinaison convexe (1-)x1 + x3.

J'isole donc x4 dans l'égalité donnée et j'obtien = 0,618.

Ensuite il nous est demandé de donner x4 comme combinaison convexe de x1 et x3 dans le cas où c'est l'intervalle [x1,x2] qui est le plus grand.

Je ne suis pas sur de ma réponse : j'aurais répondu (1-)x3 + x1 et donc
Est-ce correct?

MErci

[ice456]

J'ai une autre question concernant les combinaisons convexes :

on choisit de chercher x4 dans le plus grand des intervals [x1,x2] ou [x2,x3].

Dans le cas où c'est [x2,x3], on veut x4 tel que
Il faut montrer que x4 détermine bien une combinaison convexe (1-)x1 + x3.

J'isole donc x4 dans l'égalité donnée et j'obtien = 0,618.

Ensuite il nous est demandé de donner x4 comme combinaison convexe de x1 et x3 dans le cas où c'est l'intervalle [x1,x2] qui est le plus grand.

Je ne suis pas sur de ma réponse : j'aurais répondu (1-)x3 + x1 et donc
Est-ce correct?

MErci

[ice456]

Personne ne peut m'aider sur cette algorithme?

[ice456]

Personne ne peut m'aider sur cette algorithme?

[ice456]

Bonsoir,

j'aimerai comprendre le critère d'arrêt de l'algorithme qui nous a été donné.

Le voici :

pour un interval [an,bn],

|an - bn| (|an|+|bn|) avec >0.

Je ne vois pas trop l'interet de cette conditon d'arret.

En quoi la distance de la borne |an - bn| étant inférieur à un facteur à la somme des bornes permet-elle de dire qu'on est proche d'un minimum?

Merci d'avance pour vos explications

[ice456]

Bonsoir,

j'aimerai comprendre le critère d'arrêt de l'algorithme qui nous a été donné.

Le voici :

pour un interval [an,bn],

|an - bn| (|an|+|bn|) avec >0.

Je ne vois pas trop l'interet de cette conditon d'arret.

En quoi la distance de la borne |an - bn| étant inférieur à un facteur à la somme des bornes permet-elle de dire qu'on est proche d'un minimum?

Merci d'avance pour vos explications