La Descente de Gradient avec des contraintes (multiplicateurs de lagrange)

J'essaie de trouver le minimum d'une fonction à N paramètres à l'aide de la descente de gradient. Cependant je veux le faire tout en limitant la somme des valeurs absolues des paramètres à 1 (ou <= 1, n'a pas d'importance). Pour cette raison, je suis en utilisant la méthode des multiplicateurs de lagrange si ma fonction est f(x), je vais être de réduire f(x) + lambda * (g(x)-1) où g(x) est une approximation régulière pour la somme des valeurs absolues des paramètres.

Maintenant que je comprends, le gradient de cette fonction ne sera 0 lorsque g(x)=1, de sorte qu'une méthode pour trouver un minimum local doit trouver le minimum de ma fonction qui est à ma condition est également remplie. Le problème est que ce plus ma fonction illimitée, de sorte que la Descente de Gradient trouve tout simplement de plus en plus grande des lambdas avec de plus en plus grande des paramètres (en valeur absolue) et ne converge jamais.

Pour le moment je suis en utilisant python (scipy) la mise en œuvre de la CG donc je préfère vraiment les suggestions qui ne nécessitent pas de me re-écrire /modifier légèrement le code GE moi-même, mais l'utilisation d'une méthode existante.

InformationsquelleAutor nickb | 2012-09-05
  1. 23

    Le problème est que lors de l'utilisation des multiplicateurs de Lagrange, les points critiques de ne pas se produire à minima locaux de la Lagrange - ils se produisent à la selle points à la place. Puisque l'algorithme de descente de gradient est conçu pour trouver des minima locaux, il ne parvient pas à converger lorsque vous lui donnez un problème avec contraintes.

    Il y a en général trois solutions:

    • Utiliser une méthode numérique qui est capable de trouver des points de selle, par exemple, la méthode de Newton. Celles-ci exigent généralement des expressions analytiques pour le gradient et la Hessienne, cependant.
    • Utilisation de pénalité méthodes. Ici, vous ajoutez un supplément (lisse) terme à votre fonction de coût, qui est égale à zéro lorsque les contraintes sont satisfaites (ou presque satisfaits) et de très grande quand ils ne sont pas satisfaits. Vous pouvez ensuite exécuter la descente de gradient comme d'habitude. Cependant, cela a souvent mauvaise propriétés de convergence, comme elle fait beaucoup de petits ajustements pour assurer les paramètres de satisfaire les contraintes.
    • Au lieu de chercher les points critiques du Lagrangien, de minimiser le carré de la pente du Lagrangien. Évidemment, si tous les dérivés de la Lagrangien est égale à zéro, alors le carré de la pente sera de zéro, et depuis la place de quelque chose qui ne peut jamais être inférieure à zéro, vous trouverez les mêmes solutions que vous le feriez en extremizing le Lagrangien. Cependant, si vous souhaitez utiliser la descente de gradient alors vous avez besoin d'une expression du gradient de la place de la pente de la Lagrangien, qui pourrait ne pas être facile à trouver.

    Personnellement, j'irais avec la troisième approche, et de trouver le gradient de la place de la pente de la Lagrangien numériquement si c'est trop difficile d'obtenir une expression analytique pour elle.

    Aussi, vous n'avez pas assez clairement à votre question - êtes-vous à l'aide de la descente de gradient, ou CG (conjugué dégradés)?

    • Je suis à l'aide de gradients conjugués. Merci pour la réponse détaillée!
    • Entendez-vous place de la pente de la Lagrangien ou le gradient de la place de la Lagrangien? Quelle est la place d'un dégradé?
    • Pouvez-vous introduire une référence/papier/manuel pour votre réponse (surtout la troisième solution). Je suis coder en JS qui n'ont pas de bibliothèques de contrainte optimiseurs et besoin d'essayer une simple descente de gradient pour tester la faisabilité d'une approche.
    • Si il ressemble à ce livre présente des informations utiles mit.edu/~dimitrib/Contrainte-Opt.pdf
    • Merci Andrei
    • La troisième approche donnera juste un de potentiellement plusieurs points critiques de la Lagrangien, ne correspondant pas forcément le minimum de la fonction f. Par exemple, l'exemple 2 à partir de en.wikipedia.org/wiki/Lagrange_multiplier a autant de 6 points critiques. Comment trouvez-vous tous ces points avec la descente de gradient? Est-il un autre moyen que de simplement commencer à plusieurs reprises à partir de points aléatoires?
    • J'ai trouvé ceci pour être un utile addendum à la troisième méthode mentionnée ci-dessus: en.wikipedia.org/wiki/...

    InformationsquelleAutor Chris Taylor
  2. 5

    Probablement trop tard pour être utile à l'OP, mais peut être utile à d'autres personnes dans la même situation:

    Un problème avec l'absolu, la valeur des contraintes peuvent souvent être reformulé en un équivalent problème qui n'a que des contraintes linéaires, en ajoutant un peu de "l'aide" des variables.

    Par exemple, considérons le problème 1:

    Trouver (x1,x2) qui minimise f(x1,x2) sous réserve de la non linéaire de la contrainte |x1|+|x2|<=10.

    Il y a un linéaire de la contrainte version, le problème 2:

    Trouver (x1,x2,x3,x4) qui minimise f(x1,x2), à la suite de contraintes linéaires:

    1. x1<=x3
    2. -x1<=x3
    3. x2<=x4
    4. -x2<=x4
    5. x3+x4<=10

    Remarque:

    • Si (x1,x2,x3,x4) satisfait les contraintes pour le problème 2, alors (x1,x2) satisfait les contraintes pour le problème 1 (parce que x3 >= abs(x1), x4 >= abs(x2) )
    • Si (x1,x2) satisfait les contraintes pour le problème 1, alors on peut s'étendre à (x1,x2,x3,x4) satisfaisant les contraintes pour le problème 2 par la mise en x3=abs(x1), x4=abs(x2)
    • x3,x4 n'ont aucun effet sur la fonction cible

    Il s'ensuit que la recherche d'une meilleure solution pour le problème 2 vous donnera une optimale pour le problème 1, et vice versa.

    InformationsquelleAutor Geoffrey Brent