Programmation non linéaire

La programmation non linéaire optimise un objectif non linéaire lisse sous des contraintes non linéaires, couvrant à la fois la théorie de l'optimalité et les algorithmes qui calculent les solutions.

Definition

Un programme non linéaire minimise un objectif potentiellement non linéaire sur un ensemble réalisable défini par des contraintes d'égalité et d'inégalité non linéaires ; contrairement aux problèmes convexes, il peut posséder plusieurs optima locaux, de sorte que la plupart des méthodes recherchent des points satisfaisant aux conditions d'optimalité nécessaires.

Scope

Ce sujet couvre la minimisation sans contrainte, les stratégies de recherche linéaire et de région de confiance, les méthodes du gradient, de Newton et quasi-Newton, les conditions d'optimalité du premier et du second ordre, les conditions de Karush-Kuhn-Tucker et les qualifications de contrainte, ainsi que les méthodes avec contraintes telles que la pénalité, le Lagrangien augmenté et la programmation quadratique séquentielle.

Core questions

• Quelles conditions caractérisent un optimum local d'un problème non linéaire avec contraintes ?
• Comment les méthodes de descente trouvent-elles un point stationnaire d'un problème sans contrainte ?
• Comment les contraintes sont-elles incorporées dans les algorithmes itératifs ?
• Quand un optimum local calculé peut-il être considéré comme global ?

Key theories

Conditions d'optimalité

Les conditions de Karush-Kuhn-Tucker du premier ordre et les conditions de courbure du second ordre caractérisent les optima locaux des problèmes avec contraintes sous des qualifications de contrainte appropriées.

Méthodes de descente et de type Newton

Les méthodes du gradient, de Newton et quasi-Newton génèrent des directions de descente et utilisent des recherches linéaires ou des régions de confiance pour converger vers des points stationnaires, les mises à jour quasi-Newton approximant la courbure à moindre coût.

Algorithmes d'optimisation avec contraintes

Les méthodes de pénalité, de Lagrangien augmenté et de programmation quadratique séquentielle convertissent les problèmes avec contraintes en séquences de problèmes plus simples, gérant systématiquement les contraintes d'égalité et d'inégalité.

Clinical relevance

La programmation non linéaire est utilisée partout où les objectifs ou les contraintes ne sont pas linéaires, y compris l'ajustement de modèles et l'entraînement de modèles statistiques et d'apprentissage automatique, la conception en ingénierie, le contrôle optimal et l'estimation de paramètres dans diverses disciplines scientifiques.

History

Les conditions de Karush-Kuhn-Tucker, établies en 1951 et anticipées par Karush en 1939, ont généralisé les multiplicateurs de Lagrange aux contraintes d'inégalité et ont fondé la théorie non linéaire avec contraintes. Les méthodes quasi-Newton, les Lagrangiens augmentés et la programmation quadratique séquentielle se sont développés au cours de la seconde moitié du XXe siècle pour devenir la boîte à outils computationnelle standard.

Key figures

• Harold Kuhn
• Albert Tucker
• Isaac Newton
• Magnus Hestenes

Seminal works

• nocedal2006
• bertsekas1999

Frequently asked questions

Pourquoi la programmation non linéaire est-elle plus difficile que la programmation linéaire ?

Les problèmes non linéaires peuvent avoir des régions réalisables courbées et plusieurs optima locaux, de sorte qu'il n'y a généralement aucune garantie qu'une solution calculée soit globalement la meilleure, et les optima n'ont pas nécessairement à se situer aux sommets. Les algorithmes doivent s'appuyer sur des informations locales telles que les gradients et la courbure.

Qu'est-ce qu'une méthode quasi-Newton ?

C'est une méthode itérative qui approxime le pas de Newton sans calculer la matrice complète des dérivées secondes, en accumulant des informations de courbure à partir de gradients successifs. Des méthodes telles que BFGS atteignent une convergence rapide à un coût bien inférieur à celui des pas de Newton exacts.