Programme d'optimisation

[invite31b5cbad]

Bonjour,

Je suis en train de faire des petits programmes d'optimisation sous Matlab.

J'ai fait un petit algo pour faire de l'optimisation non-linéaire, sans contraintes, par la méthode du gradient. Ca se passe bien

Par contre... maintenant j'aimerai faire la même chose, mais AVEC contraintes. Genre, le min de z=x²+y², avec comme contrainte x²<1 par exemple.

J'ai cherché sur le net, il existe tout un tas de techniques, mais je ne comprends pas bien.

J'ai notamment vu qu'on pouvait construire une nouvelle fonctionnelle z* sans contraintes, via des multiplicateurs de Lagrange. Mais entre les notations qui me paraissent obscures et le manque d'explications, ben je galère.

Un bon lien? Un algorithme tout près ?

Merci!
-----

[erff]

Bonjour, je connais une méthode simple à mettre en oeuvre : méthode avec pénalité.

- on veut min(f(x,y)) pour x²-1<0

il suffit de poser g(x,y)=f(x,y) + A*max(0,x²-1)
En choisissant A "tres grand"...

Ainsi, on cherche le min de g(x,y) par méthode du gradient classique sans contrainte, et comme A est tres grand, l'algorithme a tout intéret, à prendre max(0,x²-1)=0 donc x²<1....
J'avais essayé de programmer cela pour plusieurs pb, et ça marche assez bien...

[invite31b5cbad]

Merci!

J'ai vaguement saisi le concept, mais j'ai pas tout compris non plus.

max(0,x²-1) ça veut dire prendre le maximum entre 0 et x²-1?

Et puis, prendre le max d'une fonction, je peux le faire avec Matlab, avec une fonction toute faite, mais dans ce cas autant demander aussi directement à Matlab de minimiser ma fonction... non? J'ai l'impression d'utiliser ce que je cherche à créer...

Et si on prend x²-1=0, ça donne x=1... en quoi ça impose x<1?

Et puis tiens, d'ailleurs, si j'ai une contrainte d'égalité et non pas de supériorité/infériorité, je fais comment?

Merci!

[erff]

max(0,x²-1) ça veut dire prendre le maximum entre 0 et x²-1?

Oui
Ainsi, si x²>1, alors max(0,x²-1) est un reel strictement positif, et A*max(0,x²-1) est donc tres grand, la solution finale sera de telle sorte que A*max(0,x²-1) soit petit ou nul c à d que x²-1>0 (ou alors positif mais tres proche de 0, prends par exemple, A=10^5 dans cet exemple...mais dans les méthodes numériques, on peut tolérer ce genre d'erreur).

Et puis tiens, d'ailleurs, si j'ai une contrainte d'égalité et non pas de supériorité/infériorité, je fais comment?

Imaginons que la contrainte soit c(x,y)=0 (c est une fonction)
C'est simple, il suffit de poser g(x,y)=f(x,y) + A*c(x,y) et on fait une méthode des gradients sans contraintes, la solution du pb tendra naturellement à rendre tres petit A*c(x,y) (car A est tres grand, 10^5, 10^6...selon le pb) (voir nul) donc au final on aura satisfait (presque) la contrainte c(x,y)=0 et on aura le min de g donc le min de f...

J'ai déjà testé en cours cette méthode sur le problème de "Didon" (pas sûr de l'orthographe) en discrétisant dans un premier temps, puis en faisant cette méthode...ca marche bien, (on obtient une allure de parabole qui se superpose bien à la réponse théorique du pb)



EDIT : lorsque je dis max(0,x²-1), il suffit de renvoyer 0 si x²-1<0 et x²-1 sinon, donc ton programme évalue x²-1 et regarde son signe c'est tout, donc rien de compliqué à faire...

[A voir en vidéo sur Futura]

[invite31b5cbad]

Merci, je crois avoir compris, je vais tester ça se soir.

Par contre, je suppose que dans cette phrase:

"de telle sorte que A*max(0,x²-1) soit petit ou nul c à d que x²-1>0"

Il faut plutôt lire x²-1 INFERIEUR à 0... non?

[erff]

Oui, j'ai écrit trop vite

[invite31b5cbad]

Bon, j'ai commencé à programmer tout ça.

Ca marche, mais il y a un truc qui me gêne. Si je prends A vraiment grand, ça crée des "retours" en arrière ingérable: tant que la contrainte n'est pas violée, ça se passe bien, mais dès que la contrainte est violée, A se ramène et fout un grand coup de pied au cul à la solution, tellement qu'il faut tout recommencer voire pire puisque la pauvre solution est expédiée à l'autre bout de la galaxie.

Moralité: j'utilise un A petit (1) et un pas modéré. Ca permet de se stabiliser sur la contrainte, mais en gros il faut ajuster A.

Est-ce bien normal tout ça?

[erff]

Oui on en a parlé : ça peut mettre le bordel...Pour qu'une telle méthode numérique soit efficace, il faut ajuster A (je sais que souvent A=100 ou 1000 marche bien, pr les pb classiques, "les cas d'école").
Généralement on ne trouve la solution au pb qu'après avoir lancé plusieurs simulations en prenant des valeurs différentes pour A (des ordres de grandeurs)...Je me souviens avoir programmé un truc où la valeur de A=50 convenait très bien tandis que A=100 mettait le désordre...En fait, si la contrainte n'influence pas le résultat (parfois le fait d'ajouter une contrainte ne change pas bcp le minimum sur lequel on tomberait en travaillant sur IR) un A petit convient, si par contre cette contrainte fait que le minimum est tres différent du minimum qu'on aurait sans celle-ci, alors il faut que A soit "grand"...Bref, je n'ai eu aucune "vraie" théorie là dessus, juste des explications qualitatives.

[invite31b5cbad]

Ok, merci pour les infos.

Pour une contrainte d'inégalité, ça marche moyennant l'ajustement de A.

Pour une contrainte d'égalité, par contre, ça marche pas du tout...

[erff]

- Je me souviens l'avoir fait pour une contrainte d'égalité et ça avait bien marché...(bizzare)
- Je précise que pour un égalité, il faut prendre la valeur absolue de la contrainte=0 (ou son carré) car le but est de MINIMISER, sinon c(x,y)<0 est meilleur que c(x,y)=0 : ici on aura g(x,y)=f(x,y)+c(x,y)² (je n'ai pas précisé ce point dans mon ancien message, je m'en excuse, dans ma tête c(x,y) est positif...)

- Sinon, il y a d'autres méthodes qui permettent de traiter les problèmes avec contrainte : la méthode des gradients projetés (il n'est parfois pas évident du tout voire impossible de définir une projection sur un ensemble) qui consiste à prendre le projeté de x(n) lorsque celui ci ne vérifie plus la contrainte ; les méthodes stochastiques (genre algortihme génétique)...

Voilà.

[invite31b5cbad]

Bon, merci pour toutes ces idées, mes programmes fonctionnent bien, moyennant un calibrage pour A.