Minimiser fonction newton

Bonjour tous,

j'ai une fonction "G(x,y)" à deux variables "x" et "y" qui représente l'énergie d'un système et j'ai une fonction "f(x,y)" qui me donne le volume du système.

J'ai un algorithme qui me donne à chaque instant le volume de mon système et moi je dois minimiser la fonction "G(x,y)" en conservant le volume "f(x,y)=Vdonné".

Ce que je pensais faire c'est donc chercher le minimum du lagrangien "G(x,y)+lambda.(f(x,y)-Vdonné)"
avec lambda le multiplicateur de lagrange.

Pour ceci, je pensais calculer analytiquement la dérivée du lagrangien et ensuite annuler cette dérivée avec un schéma de Newton.

Par contre, je me pose trois questions
1) es ce que la méthode utilisée avec le lagrangien va bien m'assurer que le volume sera égal à "Vdonné" ? normalement oui puisque c'est le principe des multiplicateur de Lagrange non ?

2)
es ce que le schéma de Newton va forcement minimiser ma fonction car annuler la dérivée ça veut pouvoir dire également chercher un maximum et pas forcement un minimum ... ?

3) si je veux borner la valeur de "y" entre 1 et 1.2 es ce possible et si oui comment ?

je vous remercie pour toute l'aide que vous pourrez m'apporter.

Bonjour,

Ça commence à dater un peu, mais j'avais kiffé de faire ces trucs là, et je pense encore avoir de bons restes, donc voici mes remarques.

1) L'algo à la Lagrange avec contrainte linéaire pose problème lorsque l'on est dans une région où la fonction (fonction aussi de la contrainte) est concave vs la contrainte. Dans ce cas, on essaie de minimiser une fonction, mais en contraignant la fonction à remonter, ce qui est contradictoire.
Pour une idée sur les méthodes que je mettrais dans la famille Lagrange:
- Contrainte linéaire : on supprime la dépendance linéaire locale de la contrainte, de sorte que l'on soit sur un extremum. Pour une fonction convexe : le voisinage du lagrangien est au dessus du point désiré, donc on peut descendre vers le minima. Fonction concave : le voisinage de la contrainte est en dessous du point désiré... Difficile à minimiser en demandant qu'il reste en haut...
- Il existe aussi des contraintes quadratiques mu/2.(f-f0)^2. Elle permettent de traiter des cas concaves (la parabole va contrecarrer la concavité et rendre le lagrangien convexe), mais vu que le minimum de la contrainte n'est pas forcément le minimum du lagrangien, il y a un décalage entre la contrainte demandée et la contrainte effective. (edit: à moins de prendre mu -> infinity)
- Il existe enfin une méthode hybride, avec dépendance linéaire + dépendance quadratique (augmented lagrangian method) lambda.(f-f0)+mu/2.(f-f0)^2, méthode la plus mieux :D Algo de réajustement des contraintes simple : on commence avec lambda=0 et mu pas trop débile, et on update lambda = lambda - mu(fobtenu-f0). J'ai l'impression que wikipedia correspond à ce que j'ai en tête, donc cf wikipedia.

2) Je suppose que vous parlez d'une technique type steepest descent. Dans ce cas, elle devrait tomber sur un minimum, vu qu'on suit le sens de la pente. Le problème est plutôt de tomber sur un minimum local particulier non sur le vrai minimum minimorum. Avec un point de départ educated guess pas trop loin de ce qu'on pense être le minimum (en gros, dans la zone où suivre le sens de la pente nous fait tomber sur le vrai minimum), ça devrait être cool.
En dehors de ce problème dans les cas de minimas multiples, qu'il est difficile de résoudre sans exploration systématique ou au moins statistique, un autre danger réside dans la convergence du processus. On peut par exemple ne pas avoir de chance et tourner en rond autour du minimum (vraiment tourner en rond, ou avoir une convergence longue à cause d'un effet flip/flop -> dans ces cas, toute l'énergie qu'on met dans le gradient est pour détruire le mauvais guess du gradient du pas précédent, mais on revient au point de départ, et alors ça recommence...). Pour ça il y a la famille des algo type conjugated gradient qui sont plus performants, et qui gardent en mémoire les directions du gradient précédent (en y étant orthogonal) pour ne pas faire marche arrière.
Edit: référence qui m'est venue en tête sur le gradient conjugué qui m'avait paru sympa à l'époque ici. Il y en a plein sur les méthodes de minimisation en général, cf. google.

3) Alors ça, je ne sais pas. J'ai déjà contraint des paramètres à ne pas être zéro pour éviter des points de bifurcation. La manière dont je procédais initialement était d'espérer que ça ne sorte pas, et d'allumer la contrainte si ça sortait, mais c'était pas top selon mes souvenirs (un peu trop à gauche, la contrainte allumée, un peu trop à droite, contrainte éteinte... bref facile de faire du flip/flop). Donc j'avais fait un workaround qui, une fois que selon mon educated guess de la question, je jugeais que c'était sûr qu'on était sorti de la plage désirée, je recommençais juste avant de sortir de la plage avec une contrainte sur le bord de la plage autorisée. Mais bon, c'était plutôt un workaround artisanal hein...

J'espère vous avoir été utile.

salut xflr6 et merci beaucoup d'avoir pros le temps de répondre

Citation:

---

Envoyé par xflr6

1) L'algo à la Lagrange avec contrainte linéaire pose problème lorsque l'on est dans une région où la fonction (fonction aussi de la contrainte) est concave vs la contrainte. Dans ce cas, on essaie de minimiser une fonction, mais en contraignant la fonction à remonter, ce qui est contradictoire.
Pour une idée sur les méthodes que je mettrais dans la famille Lagrange:
- Contrainte linéaire : on supprime la dépendance linéaire locale de la contrainte, de sorte que l'on soit sur un extremum. Pour une fonction convexe : le voisinage du lagrangien est au dessus du point désiré, donc on peut descendre vers le minima. Fonction concave : le voisinage de la contrainte est en dessous du point désiré... Difficile à minimiser en demandant qu'il reste en haut...

---

pour les multiplicateurs de Lagrange avec contraite linéaire je connais l'utilisation mais je ne connais pas les conséquences. Je ne comprends pas ce que tu veux dire par exemple avec ces histoires de concativités convexités et les conséquences que ça engendre.....
Pourrais tu m'en dire plus? ( éventuellement un schéma :oops: ? )
Me détailler un peu plus en faisant l'hypothèse que je n'ai jamais entendu parlé de ceci... ? merci et désolé du dérangement

Citation:

---

Envoyé par xflr6

- Il existe aussi des contraintes quadratiques mu/2.(f-f0)^2. .....contrecarrer la concavité

---

je ne connaissais pas mais je comprends un peu. l'idée, est d'avoir un lagragien le plus convexe possible pour éviter les minimums locaux....
mais ça doit être vraiment dépendant de la fonction et des amplitudes respectivent entre contraite et fonction...
A priori je ne pense pas que ça doit améliorer grand chose à part dans des cas particuliers mais peut être que je me trompe car je n'ai pas compris ta réponse à la question précédente.

Citation:

---

Envoyé par xflr6

- Il existe enfin une méthode hybride, ....

---

là je n'ai pas du tout compris mais ça vient du fait que je n'ai pas compris tes explications précédentes.... je pense que si j'ai compris ce que tu disais avant je comprendrais la méthode hybride

Citation:

---

Envoyé par xflr6

2) ... technique type steepest descent. ... ça devrait être cool.
En dehors de ce problème dans les cas de minimas multiples, ...tourner en rond ....

---

oui, je vois ce que tu veux dire par rapport aux minimas multiples. Par contre le fait d'introduire des multiplicateurs de Lagrange ça peut rajouter des minimuns locaux ?

Citation:

---

Envoyé par xflr6

... conjugated gradient ... ici. ....

---

je ne savais pas que l'on pouvais utiliser la méthode du gradient conjugué pour minimiser une fonction, si je me rappel bien cet algo permet de résoudre une système linéaire et ici on essai de résoudre donc l'annulation des dérivées ce qui est bien un problème d'optimisation (encore faut il connaitre les dérivées de ce que l'on cherche à minimiser). j'ai compris l'histoire des directions orthogonales ça à l'air très intéressant! et le cours que tu m'as envoyé à l'air super!!!!! :ccool: (dommage pas en fr...)
je pense que c'est le meilleur algorithme de minimisation classique de type descente, non ?

Citation:

---

Envoyé par xflr6

3) .... contraint des paramètres ... une contrainte sur le bord de la plage autorisée. Mais bon, c'était plutôt un workaround artisanal hein...

---

ok, je vois, c'est un peu ce que j'avais en tête mais ça me parait pas super propre. Pour commencer c'est pas mal mais je pense qu'ensuite il faut essayer d'évoluer vers des contraintes d'inégalités de type KKT.
J'ai regardé pas mal sur le net mais je n'ai pas compris comment programmer ces contraintes d'inégalités.

Citation:

---

Envoyé par xflr6

J'espère vous avoir été utile.

---

beaucoup et je t'en remercie énormement :ccool:
par contre, je t'avous que si tu pouvais répondre aux nouvelles questions que j'ai posé ça serait vraiment super :oops:
A bientôt,
merci

Bonjour,

OK, alors pour avoir un aperçu avec les mains (enfin, surtout avec les schémas, tout en gardant à l'esprit que je ne suis pas un théoricien de l'optimisation sous contrainte...) sur les problèmes de minimisation sous contrainte qui ont été évoqués, je propose de regarder le document en PJ sur lequel j'ai tracé une dizaine de figures brutes que je propose d'expliquer une à une ici.

Tout d'abord, il faut se représenter l'(hyper)-surface du problème à plusieurs variables comme une fonction simple de la contrainte. On cache toute la difficulté du problème bien sûr, et en vrai c'est plus compliqué qu'au pays des gummies, mais c'est utile de faire cette abstraction pour appréhender la philosophie de l'approche.

On va prendre un exemple d'une fonction g0 qui dépend d'une contrainte q (et de plein d'autres variables qu'on cache et dont q dépend...), avec deux minimas et des parties concaves, convexes etc... pour illustrer le propos.

- page 1 : La fonction choisie : q^4 - 6 q^2 - q
Avec deux minimas, c'est un cas pas trop simple mais pas compliqué non plus qui va permettre d'illustrer notre propos.

- page 2 : Illustration de la concavité et de la convexité.
Région concave dans un voisinage de point : la courbe est au dessous de ses tangentes sur ce voisinage
Région convexe dans un voisinage de point : la courbe est au dessus de ses tangentes sur ce voisinage
Chaque région est séparée par des points d'inflexion.

- page 3 : Minimiser sous contrainte dans une région convexe avec contrainte linéaire
On voit qu'au voisinage du point considéré, on est bien au dessus de la tangente. la tangente est l'idéal de la partie linéaire qui intervient dans le lagrangien à minimiser lorsqu'on applique les multiplicateurs de Lagrange.

- page 4 : ...Le Lagrangien à minimiser dans un tel cas est, idéalement, la fonction moins sa tangente au point de contrainte, de sorte qu'on mappe le problème sur un problème de minimisation, où le minimum est à la valeur q=q0 contrainte. Et à cette valeur, la contribution de la contrainte au lagrangien est nul. Bref, c'est exactement ce qu'on aime. Il reste à minimiser. C'est un minimum local, mais tant qu'on prend un point de départ à la louche supérieur à 0.33, on va toujours tomber dedans avec des méthodes de descente.

- page 5 : Maintenant, on passe au cas compliqué: région concave. Dans ce cas, la tangent est au dessus. Le lagrangien contraint qu'on doit minimiser est représenté en page 6.

- page 6 : Et on voit, que si on on veut rester au point q0 et qu'on minimise, dans cette région, le sens de la pente va tirer vers le bas alors que la contrainte va vouloir nous faire remonter. Donc on va avoir du mal, il y a contradiction... Imaginons qu'on est sur la courbe des minimas, mais juste à droite de q0 : un algo de minimisation va dire d'aller toujours plus à droite, alors que la contrainte est à gauche du point de départ... Ça ne va pas aller dans la bonne direction...

- page 7 : Pour contrer ça, il y a les contraintes quadratiques en (q-q0)^2... Comme Lagrange, le principe est de minimiser un lagrangien qui contient la fonction moins la contrainte quadratique, c'est à dire la courbe de la figure suivante... L'idée de la contrainte quadratique est de la choisir assez grande pour qu'elle fonctionne dans les régions concaves en plus des régions convexes.

- page 8 : Sauf que... le minimum du Lagrangien g0 - mu/2 (q-q0)^2 n'est pas forcément au point de la contrainte. Sur la courbe, on voit clairement que au point de la contrainte, la tangent n'est pas nulle... (c'est la même que pour la courbe :-()
Aussi, si on minimise... on ne va pas tomber sur ce qu'on espérait. Deux solutions peuvent pallier ce problème : prendre un mu si grand que le minimum est imposé par la contrainte. Ce n'est pas vraiment satisfaisant. Ou alors, si on a minimisé avec q0 et qu'on tombe un peu trop à gauche, on minimise à nouveau, mais pas en contraignant avec q0, mais en y ajoutant un offset d'une valeur (le penalty) à déterminer pour se rapprocher de la vrai valeur de contrainte effective, qui nécessite d'itérer en raisonnant type "trial & error"/dichotomie/autre.

- page 9 : Heureusement, il y a le augmented Lagrangian Method... La méthode consiste à minimiser un lagrangien avec une contrainte linéaire et une contrainte quadratique.

- page 10 : Pour la partie linéaire à la Lagrange classique, on retire encore le comportement linéaire. On a ainsi au point de contrainte un extremum local, soit minimum (convexe) soit maximum (concave). Mais en plus de la partie linéaire, on ajoute aussi une partie quadratique d'intensité suffisante pour forcer la convexité :D. Sur la figure ou mu est d'intensité suffisante, on est dans une région concave, mais la courbe est au dessus de sa tangente. On a alors vraiment un beau problème de minimisation qui va converger vers le point de contrainte et dont la contribution au lagrangien au point de contrainte est nul. Tout ce qu'on voulait :ccool:

Par ailleurs, la procédure de réajustement du lamba pour trouver la tangente est très simple : on part avec mu donné et lambda nul, et on change le lambda de manière à compenser l'écart de q obtenu avec ce qu'on avait demandé (c'est en fait une manière de trouver le penalty évoqué lors de la méthode quadratique...).
Bref la méthode est très simple à mettre en œuvre et très efficace.

Citation:

---

Par contre le fait d'introduire des multiplicateurs de Lagrange ça peut rajouter des minimas locaux ?

---

Non (en tous cas je ne pense pas). Le problème est plutôt qu'il peut y avoir plusieurs minima locaux pour une même valeur de contrainte... Alors, si le point de départ est trop loin de la valeur réelle (l'état initial plus proche d'un autre minimum ou une contrainte mal choisie qui va nous faire changer de minimum), un algo "qui suit le sens de la pente", basé sur les gradients, va tomber dans le minimum local "le plus proche" (en tous cas celui vers lequel les gradients vont le guider) qui n'est pas forcément celui désiré.

Citation:

---

je ne savais pas que l'on pouvais utiliser la méthode du gradient conjugué pour minimiser une fonction, si je me rappel bien cet algo permet de résoudre une système linéaire et ici on essai de résoudre donc l'annulation des dérivées ce qui est bien un problème d'optimisation (encore faut il connaître les dérivées de ce que l'on cherche à minimiser).

---

Je ne pense pas que le gradient conjugué vienne des systèmes linéaires, c'est même plutôt l'inverse : on mappe un problème de système linéaire sur une fonction quadratique à minimiser :-).

Citation:

---

j'ai compris l'histoire des directions orthogonales ça à l'air très intéressant!

---

OK, mais j'aurais du dire directions conjuguées... Il faut voir avec des références pédagogiques, c'est assez loin pour moi. Il y a aussi sans doute un chapitre dans les numerical recipes qui pourrait éclaircir sur les algo de minimisation, et donc à coups sûr sur le CG.

Citation:

---

je pense que c'est le meilleur algorithme de minimisation classique de type descente, non ?

---

Quand on peut l'appliquer, il est très efficace. En plus il est simple à implémenter. Mais je ne peux pas répondre à cette question.

Citation:

---

ok, je vois, c'est un peu ce que j'avais en tête mais ça me parait pas super propre. Pour commencer c'est pas mal mais je pense qu'ensuite il faut essayer d'évoluer vers des contraintes d'inégalités de type KKT.
J'ai regardé pas mal sur le net mais je n'ai pas compris comment programmer ces contraintes d'inégalités.

---

Comme j'ai dit, c'était artisanal, et le but n'était pas la contrainte, mais de checker quelque chose d'autre dans les programmes. C'est peut-être une solution valide/valable, mais OUI, il faut en effet creuser plus pour trouver quelque chose de plus propre, et être sûr de la méthode employée !

Voilà, j'espère avoir éclairci certains points. J'espère en tous cas ne pas avoir obscurci la discussion !

purée! elles sont supers tes explications!

Maintenant, la seule chose que je n'ai pas compris c'est la gestion de lambda et mu exactement et leur sens.

je reprends petit à petit en raisonnant sur ton graph 1D

#1#
Lorsqu'on cherche une minimisation sans contrainte on a une courbe que l'on parcours jusqu'a descendre "jusqu'en bas", et il s'agit du minimum.
#2#
la méthode du multiplicateur de lagrange permet (dans le cas convexe) que notre minimisation tombe sur une solution qui respecte notre contrainte en supprimant les solutions plus "basses" en additionannant une terme "-lambda.contrainte"
Par contre comment est déterminé lambda pourquoi ne pas prendre égale à 1 ça ne marcherait pas?
ce que je comprends pas c'est que dans la méthode des multiplicateur de Lagrange Lambda est une inconnue mais comment la détermine t on? à quoi est elle égale ?
#3#
comme le cas concave ne fonctionne pas on utilise une méthode de pénalisation. J'ai bien compris ton explication, si on prend mu=infinie on sera donc certain de tomber sur une solution qui respecte la contrainte mais ce n'est pas très rigoureux car mu ne peut jamais être infini....
Utiliser cette methode ne nous permet pas de s'affranchir de minimums locaux de la fonction car on additionne une courbe convexe (x^2) avec quelque chosr pas forcement convexe (notre fonction)...?
Le seul interet et de ne pas trop s'eloigner de la solution ds le cas concave comme ça pourrait etre le cas avec lagragien mais ca ne resout pas le problem des minimas locaux?
#4#
Une question preliminaire: quel est le signe de lambda et mu dans la definition de wikipedia? Moi j'aurais dit tout les deux positifs mais si je regarde comment ils mettent a jour lambda alors celui ci va devenir negatif?
- Avec le lagragien augmenté on part avec "mu" grand et "lambda" nul. ça nous permet de contourner le problème de concavité (exactement cas n°2)
- ensuite on fait évolue "lambda" pour qu'il devienne de plus en plus positif (il est négatif sur wikipedia mais c'est juste une convention de signe?) et donc pour introduire petit à petit la contraite linéaire qui nous permet de tomber sur une solution proche du cas n°1 mais pas tout à fait la même puisque mu n'est pas nul...)

- par contre, mu est toujours fixe? sous wikipedia on dirait que non il est sous entendu qu'il est "updated", mais comment et pourquoi ?
moi j'aurai tendance à le laisser fixe....

#questions entre le point 4 et le point 1#
- ensuite, je ne comprends toujours pas la mise à jour "lambda=lambda-mu.(f-f0)". Si "mu" est constant, plus on se rapproche de la contrainte moins lambda évolue, mais qui nous dit que lambda va atteindre la valeur qui lui permet de retomber sur le cas n°1 qui lui permet de trouver le minimum qui respect la contrainte ?

- Pour mon problème de minimisation avec augmented lagrangien, si j'utilise un algo qui a besoin de 2 itérations pour trouver la solution je vais obtenir un lambda1 qui aura par exemple la valeur 2. Par contre, si je prend un algo qui a besoin de 4 itérations pour trouver la solution il va me trouver un lambda2 qui sera égal à 8 par exemple.... ??
or lambda ne devrai pas être unique ?
(ça rejoinds ma question numéro 1...)

####
j'espère que tu auras un peu de temps pour répondre à ces dernières questions, j'ai quasiment tout compris à présent, il y a juste ces quelques petits détails qui me gênent encore....

merci pour ton aide!!!!

Citation:

---

Envoyé par membreComplexe12

#1#
Lorsqu'on cherche une minimisation sans contrainte on a une courbe que l'on parcours jusqu'a descendre "jusqu'en bas", et il s'agit du minimum.

---

Ca ne prend pas forcément le chemin de la courbe.
La courbe, c'est les minima à q donné. Il peut avoir à q donné d'autres solutions non minimales. N'oublions pas qu'on a sur-simplifié la représentation du problème (multivarié) en ne représentant que les minima en fonction de q. Mais bon je suppose que l'esprit est là.

Citation:

---

Envoyé par membreComplexe12

#2#
la méthode du multiplicateur de lagrange permet (dans le cas convexe) que notre minimisation tombe sur une solution qui respecte notre contrainte en supprimant les solutions plus "basses" en additionannant une terme "-lambda.contrainte"

---

Lagrange ne supprime rien : il reformule un problème de minimisation contrainte en un nouveau problème de minimisation non contrainte (mais bon c'est pas du tout cuit non plus, encore faut-il ajuster (et réajuster) le lambda quand on y a pas accès analytiquement).

Citation:

---

Envoyé par membreComplexe12

Par contre comment est déterminé lambda pourquoi ne pas prendre égale à 1 ça ne marcherait pas?
ce que je comprends pas c'est que dans la méthode des multiplicateur de Lagrange Lambda est une inconnue mais comment la détermine t on? à quoi est elle égale ?

---

Ça devient compliqué. Sans Lagrange, si on prend la méthode du gradient, il faut annuler le gradient. On doit donc résoudre un système d'équations. Ajouter une contrainte revient à ajouter une inconnue : lambda, mais aussi une équation : f(x,y)=Vdonne dans ton cas.
Je ne sais pas si ça marche à tous les coups. Je ne l'ai fait qu'une fois dans un problème très simple (à beaucoup de variable, mais simple).
\begin{edit}
Je ne sais pas si d'autres méthodes sont employées (je peux bien imaginer qu'il y a des méthodes trial & error pour ajuster le lambda, mais n'y ai jamais réfléchi). Dans les problèmes auxquels je me suis confronté, je n'ai de fait utilisé que du lagrangien augmenté car c'est de ça que j'avais besoin.
\end{edit}

Citation:

---

Envoyé par membreComplexe12

#3#
comme le cas concave ne fonctionne pas on utilise une méthode de pénalisation. J'ai bien compris ton explication, si on prend mu=infinie on sera donc certain de tomber sur une solution qui respecte la contrainte mais ce n'est pas très rigoureux car mu ne peut jamais être infini....
Utiliser cette methode ne nous permet pas de s'affranchir de minimums locaux de la fonction car on additionne une courbe convexe (x^2) avec quelque chosr pas forcement convexe (notre fonction)...?
Le seul interet et de ne pas trop s'eloigner de la solution ds le cas concave comme ça pourrait etre le cas avec lagragien mais ca ne resout pas le problem des minimas locaux?

---

Si les minimas locaux te préoccupent tant, c'est peut-être que les méthodes de type lagrange ne sont pas adaptée... On y reviendra plus tard.
Mais oui, avoir une partie quadratique est souvent nécessaire, mais quadratique uniquement n'est pas génial. Jouer sur un mu grand n'est pas génial. Et décaler la contrainte d'un offset (q-q0-offset)^2 pour tomber sur un bon résultat, ok, mais ça revient au lagrangien augmenté à peu de choses près (le offset, c'est une partie linéaire + une constante) .

Citation:

---

Envoyé par membreComplexe12

#4#
Une question preliminaire: quel est le signe de lambda et mu dans la definition de wikipedia? Moi j'aurais dit tout les deux positifs mais si je regarde comment ils mettent a jour lambda alors celui ci va devenir negatif?

---

mu toujours positif +mu/2 (q-q0)^2 sinon, on risque de ne plus être convexe même dans les cas où on l'était initialement !
Pour le lambda, bonne question, ça dépend de... la courbe des minimas en fonction de q... positif quand ça monte, négatif quand ça descend ;-)

Citation:

---

Envoyé par membreComplexe12

- Avec le lagragien augmenté on part avec "mu" grand et "lambda" nul. ça nous permet de contourner le problème de concavité (exactement cas n°2)

---

il est possible de partir avec lambda nul et mu assez grand pour être sûr d'être convexe. C'est en général comme ça qu'on part pour attaquer un nouveau problème. Si on part d'une solution qu'on a évoluée et qu'on veu recontraindre par exemple, en supposant que le point n'est pas trop éloigné, autant partir avec les paramètres lambda utilisés pour ce point. Il y a fort à parier que l'ordre de grandeur des paramètres sera le bon, donc autant partir avec). On sera d'autant plus proche de re-contraindre correctement et rapidement.
En plus de gérer les cas concaves, ça permet aussi d'avoir une méthode d'ajustement pour lambda straitforward.

Citation:

---

Envoyé par membreComplexe12

- ensuite on fait évolue "lambda" pour qu'il devienne de plus en plus positif (il est négatif sur wikipedia mais c'est juste une convention de signe?) et donc pour introduire petit à petit la contraite linéaire qui nous permet de tomber sur une solution proche du cas n°1 mais pas tout à fait la même puisque mu n'est pas nul...)

---

dans la formule, mettre "- lambda ( q - q0 )" est conventionnel et intuitif, car ça veut dire que tu enlèves la tangente au point. Ca fait du sens quand tu regardes les dessins que j'ai fait. Après, lambda peut être plein de chose. Si tu essaie de contraindre sur un extremum, lambda sera nul, et prendra un signe +/- si ça monte/descend...

Citation:

---

Envoyé par membreComplexe12

- par contre, mu est toujours fixe? sous wikipedia on dirait que non il est sous entendu qu'il est "updated", mais comment et pourquoi ?
moi j'aurai tendance à le laisser fixe....

---

Dans tous les cas que j'ai traité, je l'ai laissé fixe. Je m'assurais cependant avant que la contribution de la contrainte était assez petite devant la valeur de la fonction (qques pourcents) sinon ça pouvait détruire la convergence dans le meilleur des cas, ou trouver une solution dans des configurations très loin de ce que je voulais dans les cas problématiques.

Mais si la courbe des minimas fonction de q (la courbe que tu as une fois que tu sais faire les contraintes, je sais la vie est dure) a des variations très dures et très molles à certains endroits, ça peut nécessiter d'augmenter le mu ou le diminuer pour qu'il soit adapté au problème. Je n'ai pas été confronté à cette nécessité.

Citation:

---

Envoyé par membreComplexe12

#questions entre le point 4 et le point 1#
- ensuite, je ne comprends toujours pas la mise à jour "lambda=lambda-mu.(f-f0)". Si "mu" est constant, plus on se rapproche de la contrainte moins lambda évolue, mais qui nous dit que lambda va atteindre la valeur qui lui permet de retomber sur le cas n°1 qui lui permet de trouver le minimum qui respect la contrainte ?

---

La convergence par exemple ;-)

Citation:

---

Envoyé par membreComplexe12

- Pour mon problème de minimisation avec augmented lagrangien, si j'utilise un algo qui a besoin de 2 itérations pour trouver la solution je vais obtenir un lambda1 qui aura par exemple la valeur 2. Par contre, si je prend un algo qui a besoin de 4 itérations pour trouver la solution il va me trouver un lambda2 qui sera égal à 8 par exemple.... ??
or lambda ne devrai pas être unique ?
(ça rejoinds ma question numéro 1...)

---

Lambda est lambda, qu'il y ai besoin d'une, 4 ou 666 itérations. (Il n'est pas unique pour des raisons autres, dues aux multiples variables, et à la topologie des contraintes et de la fonction à minimiser... qui peuvent présenter donc plusieurs solutions à q donné.)

### Minimas ###
Je voulais enfin éclaircir qque chose : Les méthodes type Lagrange ne suppriment par les minimas. Elle permettent de contraindre, c'est tout. Elles permettent de connaître la topologie d'une courbe de minimas contraints lorsqu'on résoud le pb contraint sur tout l'espace des phases... Mais ça, ça peut coûter cher.

Lorsque le problème est d'essayer de trouver un minimum global dans une surface avec plein d'extrema "loosy" qui se ressemblent, il faut soit explorer systématiquement, ce qui peut coûter ultra cher, soit [peut-être autre chose], soit reposer sur des méthodes méta-heuristiques (jamais utilisé, donc j'ai pas l'niveau pour expliquer) qui permettent d'échantillonner l'espace et d'auto-apprendre sur la topologie sans se taper tout le taf d'une exploration systématique. Mais c'est une autre histoire.
Pour un problème de physique en 2D smooth, méthode type gradient + méthode type lagrange should be ok.

Bonne continuation !

Merci beaucoup pour ton aide ça m'aide énormément :ccool:

un extrait de cours bien que j'ai trouvé :ccool:

Pour la démonstration de l'origine du multiplicateur de Lagrange j'ai trouvé un document très intéressant, je l'ai mis en PJ. La seule chose que je n'avais pas compris c'était d'où sort l'eq. 3 dans ce document mais à présent je crois avoir compris, B représente le gradient de la contrainte et donc la condition 3 est une condition qui impose de rester sur la contrainte lors de notre recherche de minimum (puisque le gradient est perpendiculaire à la surface de la contrainte). Si ce que je dis n'est pas faux alors j'ai à présent bien compris l'origine des multiplicateurs de Lagrange, mais....

Il me reste une questions :oops:

ma question porte sur une figure que tu as fais précédemment., celle de la page 3.
Pourquoi tu as pris la tangente à la courbe dans ton schéma pour la quantité "lambda.(q-q0)" ?

Pour moi l'équation de la tangente est y=g'(q0)(q-q0)+g(q0) donc la quantité "lambda.(q-q0)" ne peut être égale à la tangente que si lambda est égale à "g'(q0)" et si g(q0)=0 mais pourquoi ça serait le cas ?

Citation:

---

Envoyé par membreComplexe12

ma question porte sur une figure que tu as fais précédemment., celle de la page 3.
Pourquoi tu as pris la tangente à la courbe dans ton schéma pour la quantité "lambda.(q-q0)" ?

Pour moi l'équation de la tangente est y=g'(q0)(q-q0)+g(q0) donc la quantité "lambda.(q-q0)" ne peut être égale à la tangente que si lambda est égale à "g'(q0)" et si g(q0)=0 mais pourquoi ça serait le cas ?

---

A la fin, tu dois avoir lambda qui est la pente, donc lambda=g'(q0) effectivement... la dérivée par rapport à q bien sûr.
En effet, tu dois être sur un minimum du lagrangien. C'est pour ça que tu as ajouté les multiplicateurs de Lagrange, ce serait dommage que ce ne soit pas le cas...

Pour g(q0), on ne le met en effet pas dans la contrainte. J'ai réalisé les figures avec un script gnuplot vite fait (qui explique pourquoi elle apparaît à chaque fois), et je n'ai pas été assez vigilent. Bref, tu as tout à fait raison de relever ce point !
A la présentation des problèmes, je voulais mettre la tangente à la courbe pour dire qu'on se mettait dans le référentiel où l'axe était la tangente, ce qui revient à enlever lambda ( q-q0) uniquement... Le cas des multilplicateurs de Lagrange quoi.
Donc c'est vrai, il ne faut pas raisonner en terme de tangente ni de pente de tangente, mais en termes de "composante du premier ordre du développement limité au voisinage de q0".
Ça ne change pas vraiment la philosophie de l'approche (dans le sens pourquoi on fait ça), mais c'est très dommage d'avoir fait cette erreur alors que j'ai essayé d'être pédagogique le plus possible... Et que c'aurait été plus parlant sans.
Bien vu :ccool:
Et désolé.

merci beaucoup pour tout c'est très gentil pour ton aide !!!!

Citation:

---

Envoyé par xflr6

Et désolé.

---

ne t'excuse surtout pas ;) tu m'as tellement aidé :ccool:

merci A+

salut xflr6,

j'ai remis tout en place dans ma tête :roll: et il y a un truc que je ne comprends pas sur le fond de tes explications.

Je reprends depuis le départ :

1) Cas classique
On a une fonction "f(x)" que l'on veut minimiser sous la contrainte "q(x)=q0". Ce problème revient à trouver le minimum de "f(x)" par rapport à "x" tout en respectant l'équation "q(x)=q0".

Une manière de faire ceci est donc de minimiser le lagrangien suivant
"L(x,lambda)=f(x)-lambda(q(x)-q0)"
par rapport à "x" et "lambda".

2) Ton explication
Dans ton explications tu dis (si j'ai bien compris) que "f" dépend de "x" mais que "x" peut être écrit en fonction de "q" et donc que l'on peut écrire le lagragien en fonction de "q" seulement
"L(q,lambda)=g(q)-lambda(q(x)-q0)"

Ensuite, tu dis que lambda est égale à la dérivée en q0 par rapport à "q", ce qui me parait correct car la condition "dL(q,lambda)/dlambda=0" nous donne "q=q0" et que la condition "dL(q,lambda)/dq=0" nous donne "lambda=dg(q)/dq" et donc ces deux conditions réunies nous donne bien "lambda=dg(q0)/dq".

et donc je comprends ton raisonnement avec la tangente :ccool:

3) le soucis
Le soucis est que "lambda" est égal à "lambda=dg(q0)/dq" si et seulement si on cherche à minimiser "L(q,lambda)" par rapport à "q" :roll:

or, dans le problème de départ on ne cherche pas à minimiser L(x,lambda) par rapport à "q" mais par rapport à "x". A la limite je comprends que tu veuille écrit le lagrangien en fonction de "q" L(q,lambda) mais on ne doit pas annuler la dérivée par rapport à "q" mais par rapport à "x" :cry:

Du coup, il y a pas de raison pour que "lambda=dg(q0)/dq" puisque ceci se démontre que lorsqu'on essai d'annuler le lagragien L(q,lambda) par rapport à "q" :calim2:

conclusion

du coup, je ne suis pas certain que le raisonnement que tu as mis dans le PDF soit correct, ou alors il y a encore un truc que je n'ai pas saisi :oops:

ps->au fait, aurais tu un livre ou cours à me conseiller qui aborde tous ces choses de manière assez simple (pour débutant quoi ;) ) ? ça m'intéresserait bien pour bien tout saisir et aller plus loin également (inégalités....)

En fait, pour etre un peu plus clair, ma question pourrait se poser ainsi :

1) j'ai cette derivee "df(x)/dx" a annuler pour trouver est l'abscisses "x" du minimum.

2) maintenant, pour une raison quelconque, je decide d'ecrire la fonction non plus en fonction de la variable "x" mais d'une autre variable "q" (qui elle meme dependant de x).

3) maintenant si j'annule "dg(q)/dq" es ce que l'abscisses "q" du minimum de la fonction g(q) est la meme que pr la question 1) ?
Autrement dis, trouver le minimum en "q" est il equivalent a trouver le minimum en "x" ??

Merci pour votre aide

Bonsoir,

J'espère que tu as trouvé tes réponses depuis le temps. Sinon, pour la validité du raisonnement avec les mains que j'avais entrepris, il ne faut pas oublier :

Citation:

---

Tout d'abord, il faut se représenter l'(hyper)-surface du problème à plusieurs variables comme une fonction simple de la contrainte. On cache toute la difficulté du problème bien sûr, et en vrai c'est plus compliqué qu'au pays des gummies, mais c'est utile de faire cette abstraction pour appréhender la philosophie de l'approche.

---

Donc en gros, je suppose qu'on a le minimum en fonction de q. Dans ce cas, qu'ai-je besoin d'ajouter à la fonctionnelle pour minimiser une fonction en tombant sur la bonne contrainte ? -> C'est ce que j'essaie d'expliquer, cf les versions contraintes linéaires, quadratiques et augmentée à la lagrange.

Quand au pb de q/x,y... Si on est au minimum à q donné, la valeur x,y doit correspondre au bon résultat (oui bon je n'ai pas compris l'objection...).
Les trucs (paramètres, multiplicateurs, contraintes...) de lagrange, c'est ce qu'on ajoute à la fonctionnelle à minimiser pour contraindre sur q, mais le problème de minimisation, c'est toujours selon les x_i.

salut et merci de prendre le temps de répondre encore une fois

Citation:

---

Envoyé par xflr6

Quand au pb de q/x,y... Si on est au minimum à q donné, la valeur x,y doit correspondre au bon résultat (oui bon je n'ai pas compris l'objection...).

---

c'est ça que je n'ai pas compris après coup :aie:

on a cette equivalence car on a "dg/dq=dg/dx.dx/dq=0"
et on considère que "dx/dq" n'est jamais nul donc "dg/dq=0" est quivalenet à "dg/dx=0" ?