Minimisation d'une fonction à plusieurs variables en C++ : algo Line-search, Newton Raphson, Gradient Conjugué

[doky87]

Je demandais comment écrire l'algorithme de la méthode de LINE-SEARCH,de NEWTON RAPHSON, et l'algorithme des GRADIENT CONJUGUES pour la minimisation d'une fonction à plusieurs variables en C++.Si vous pouvez m'expliquer avec plus de détaille l'inverse de la matrice Hessienne définie par la dérivée seconde de la fonction à plusieurs variables.
Cordialement,

[Aleph69]

Bonjour,

la manière dont on programme ce type de méthode dépend fortement du type de données. De quelles données disposes-tu? Dans quel contexte souhaites-tu utiliser ces algorithmes? Il faudra également préciser ce que tu entends par la méthode "line search" car il en existe plusieurs. Précise également ce qui te pose problème avec l'inverse de la matrice hessienne.

[doky87]

Envoyé par Aleph69

Bonjour,

la manière dont on programme ce type de méthode dépend fortement du type de données. De quelles données disposes-tu? Dans quel contexte souhaites-tu utiliser ces algorithmes? Il faudra également préciser ce que tu entends par la méthode "line search" car il en existe plusieurs. Précise également ce qui te pose problème avec l'inverse de la matrice hessienne.

Bonjour,
On cherche à minimiser la fonction f(x,y)=x*x+x+y*y+xy,avec comme point de départ {x0,y0}={-3,1} par la méthode des gradients conjugués(cette methode utilise dans un premier temps la direction fournie par le gradient de la fonction que l'on cherche à minimiser,dans un deuxiéme temps la direction conjuguée),aussi par la methode de "line-search qui utilise aussi la direction fourni par le gradient de la fonction que l'on cherche à minimiser et par la méthode de Newton Raphson.
La matrice Hessienne est définie par la dérivée seconde de la fonction f(x,y)).
Cordiale,

[Aleph69]

Bonjour,

Envoyé par doky87

Bonjour,
On cherche à minimiser la fonction f(x,y)=x*x+x+y*y+xy,avec comme point de départ {x0,y0}={-3,1} par la méthode des gradients conjugués(cette methode utilise dans un premier temps la direction fournie par le gradient de la fonction que l'on cherche à minimiser,dans un deuxiéme temps la direction conjuguée),aussi par la methode de "line-search qui utilise aussi la direction fourni par le gradient de la fonction que l'on cherche à minimiser et par la méthode de Newton Raphson.

LA méthode de "line search" n'existe pas; il y en a plusieurs, chacune porte un nom. Laquelle souhaites-tu utiliser?

Au niveau de l'implémentation de ces méthodes, quelle(s) difficulté(s) vois-tu?

Envoyé par doky87

La matrice Hessienne est définie par la dérivée seconde de la fonction f(x,y)).

La matrice hessienne étant connue explicitement, tu peux soit calculer son inverse à la main et la fournir en entrée de ton algorithme, soit résoudre numériquement les systèmes linéaires faisant intervenant la matrice hessienne en calculant la factorisation LU de cette dernière au point d'évaluation courant.

[doky87]

Envoyé par Aleph69

Bonjour,



LA méthode de "line search" n'existe pas; il y en a plusieurs, chacune porte un nom. Laquelle souhaites-tu utiliser?

Au niveau de l'implémentation de ces méthodes, quelle(s) difficulté(s) vois-tu?



La matrice hessienne étant connue explicitement, tu peux soit calculer son inverse à la main et la fournir en entrée de ton algorithme, soit résoudre numériquement les systèmes linéaires faisant intervenant la matrice hessienne en calculant la factorisation LU de cette dernière au point d'évaluation courant.

Bonjour,
Si je dispose de l algorithme des gradients conjugues je pourrai traiter l algorithme de la methode de line search.
Mais jai vraiment bsion de l algorithme de Newton Raphson en Cpp pour laminimisation d une fonction.
Cordialement,

[Aleph69]

Envoyé par doky87

Mais jai vraiment bsion de l algorithme de Newton Raphson en Cpp pour laminimisation d une fonction.

D'accord. Partons du principe que tu donnes en entrée de ton algorithme la fonction à minimiser et l'inverse de sa matrice jacobienne. Qu'est-ce qui te pose problème dans l'implémentation en C++?

[Alexis.M]

Je n'ai pas bien compris si tu devais utiliser la méthode appelée "line search Newton-CG", ou si tu voulais tester plusieurs méthodes dont 1) le gradient conjugué, 2) line search (mais dans ce cas comment choisis-tu la direction de descente ?) 3) la méthode de Newton.

la méthode "line search Newton-Gradient descent" étant une implémentation possible de la méthode de Newton, je dirais que c'est sans doute cette méthode que tu cherches à implémenter ?

Dans tous les cas je te conseilles la lecture de "Numerical Optimization" de Nocedal Chapitre 3 (line search) Chapitre 5 (conjugate gradient) et Chapitre 6 (Practical Newton methods).

Pour faire lien avec ce que tu as sans doute vu, il est utile de mettre ta fonction en notation matricielle:

f(x,y) = z' A z + b'z

avec z = [x , y]'

A = [1 1/2]
[ 1/2 1]
b = [1 0]