Aller au contenu
Optimisation 2 · L3

Leçon 4 sur 5

Méthodes de gradient, de Newton et de pénalisation

Je sais construire une méthode de descente avec recherche linéaire d'Armijo, analyser la vitesse de la méthode du gradient et de la méthode de Newton, et ramener un problème contraint à une suite de problèmes sans contrainte par pénalisation ou barrière.

  • 1 h 30
  • 6 exercices corrigés
  • QCM de 7 questions

À la fin de la leçon, vous saurez :

  • Définir une direction de descente et choisir un pas par la règle d'Armijo
  • Appliquer la méthode du gradient et relier sa vitesse au conditionnement
  • Appliquer la méthode de Newton et expliquer sa convergence quadratique et ses limites
  • Résoudre un problème contraint par pénalisation extérieure ou barrière logarithmique et en déduire une estimation du multiplicateur
  • Programmer une méthode de descente en Python

Avant de commencer : Optimisation 1 (gradient et Newton, première approche) ; leçons 1 et 2 (KKT, multiplicateurs).

1Je découvre

Kindia Jus veut désormais planifier sa production semaine par semaine sur toute la saison des mangues, pour ses quinze produits, en tenant compte des coûts de stockage, de l'usure des machines et des prix qui varient sur les marchés de Madina et de Kindia. Le modèle n'est plus linéaire : les coûts sont quadratiques, certains rendements suivent des courbes en logarithme. Il compte plusieurs centaines de variables.

On ne peut plus résoudre les conditions KKT à la main, ni par le simplexe. Il faut des algorithmes itératifs : partir d'un point, l'améliorer pas à pas, et s'arrêter quand le gradient est presque nul. En Optimisation 1, vous avez vu le principe du gradient et de Newton sans contrainte. Il reste à choisir le pas de façon fiable, à comprendre pourquoi certaines méthodes « rampent », et surtout à traiter les contraintes.

Comment construire des algorithmes de descente fiables et rapides, et comment les adapter aux problèmes avec contraintes ?

La suite se lit avec votre compte Kharandi Université

La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.

Voir toutes les leçons de Optimisation 2

Signaler une erreur dans cette leçon

Toutes les leçons de Optimisation 2

Pose ta question à Karamö