Programmation non linéaire
- Introduite par
- Jorge Nocedal & Stephen Wright
- Année
- 2006
- Type
- Continuous mathematical optimization
- Famille
- Mathematical programming
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La programmation non linéaire (PNL) est une branche de l'optimisation mathématique qui traite des problèmes dans lesquels la fonction objectif ou au moins une contrainte est non linéaire.
Formalisée de manière exhaustive par Jorge Nocedal et Stephen Wright dans leur ouvrage de référence de 2006, la PNL englobe les algorithmes basés sur le gradient — y compris la programmation quadratique séquentielle (SQP), les méthodes de points intérieurs et les approches quasi-newtoniennes — pour trouver des solutions localement ou globalement optimales à des problèmes de décision continus apparaissant en ingénierie, en économie et dans les sciences physiques.
L’intuition derrière la méthode
Imaginez descendre un paysage vallonné et brumeux tout en restant à l'intérieur d'une zone clôturée. Vous ne pouvez pas voir tout le terrain, vous sentez donc la pente sous vos pieds (gradient), ajustez la direction de votre pas pour descendre, et vérifiez à chaque mouvement que vous n'avez pas franchi la clôture (contraintes). Si la clôture est courbée ou si les collines se chevauchent, les chemins rectilignes simples ne suffiront pas — vous devrez courber votre trajectoire. La programmation non linéaire formalise exactement ce processus, remplaçant la marche intuitive sur les collines par des règles mathématiquement rigoureuses de taille de pas et de direction.
Histoire
Les fondements théoriques de la programmation non linéaire remontent aux conditions KKT dérivées par Karush (1939) et Kuhn et Tucker (1951). Les algorithmes pratiques se sont accélérés durant les années 1960-1980 avec le développement des méthodes SQP, des approches Lagrangien augmentées, et des mises à jour quasi-newtoniennes incluant BFGS (1970). La deuxième édition de Numerical Optimization par Nocedal et Wright en 2006 est devenue une référence définitive, synthétisant la théorie de convergence, les cadres de recherche de ligne et de région de confiance, et les méthodes de points intérieurs dans un traitement moderne cohérent.
Quand l’utiliser
Utilisez la programmation non linéaire lorsque l'objectif ou les contraintes ne peuvent être linéarisés sans perte matérielle de précision et que les variables de décision sont continues. Les contextes typiques incluent la conception d'ingénierie avec des contraintes de lois physiques, l'optimisation de portefeuille avec des mesures de risque non linéaires, et la régression avec des formes de modèles non linéaires. Les hypothèses clés sont que f et c sont au moins deux fois continûment différentiables (pour les solveurs basés sur le gradient) et que les qualifications de contrainte sont satisfaites. Lorsque les variables sont à valeurs entières, des extensions de programmation non linéaire en nombres entiers mixtes (MINLP) s'appliquent. Pour les problèmes convexes, les méthodes de points intérieurs garantissent l'optimalité globale ; pour les problèmes non convexes, seules des garanties locales existent.
Limites et points d’attention
- Les problèmes non convexes n'offrent que des garanties d'optimalité locale ; les solutions globales nécessitent des stratégies de recherche globale supplémentaires.
- Exige que l'objectif et les contraintes soient lisses (au moins différentiables) ; les problèmes non lisses nécessitent des méthodes de sous-différentiels spécialisées.
- Le coût de calcul augmente considérablement avec la taille du problème lorsque l'évaluation exacte du Hessien est requise.
- Les qualifications de contrainte peuvent échouer (par exemple, aux points réalisables dégénérés), faisant perdre leur fondement théorique aux conditions KKT.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Gère une large classe de problèmes du monde réel où les approximations linéaires ou quadratiques sont insuffisantes.
- Théorie algorithmique mature avec des garanties de convergence bien étudiées pour les cas convexes.
- Des solveurs efficaces basés sur le gradient (SQP, points intérieurs) s'adaptent en pratique à des milliers de variables.
- Le cadre Lagrangien unifié accueille naturellement les contraintes mixtes d'égalité et d'inégalité.
Applications
- Ingénierie structurelle et aérospatiale : minimisation du poids sous contraintes de contrainte et de déflexion.
- Gestion de portefeuille : maximisation du rendement attendu sous un budget de variance (risque) non linéaire.
- Conception de procédés chimiques : optimisation du rendement du réacteur sous contraintes thermodynamiques et de sécurité.
- Apprentissage automatique : entraînement de réseaux neuronaux et de modèles à noyau via des solveurs PNL non contraints ou contraints.
- Systèmes énergétiques : problèmes de flux de puissance optimaux dans la répartition de réseaux électriques avec contraintes physiques non linéaires.
Comment ça marche
Comment ça marche
L'analyste définit une fonction scalaire objectif f(x) à minimiser ou maximiser sur des variables de décision x dans R^n, ainsi que des contraintes d'égalité c_i(x) = 0 et des contraintes d'inégalité c_j(x) >= 0. Identifier quelles contraintes sont actives à une solution candidate et si les conditions de régularité (qualifications de contrainte) sont remplies est critique à ce stade et détermine quelle théorie d'optimalité s'applique.
Formule
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}Les conditions de Karush-Kuhn-Tucker (KKT) fournissent des conditions nécessaires du premier ordre pour un optimum local. Elles exigent la stationnarité du Lagrangien, le relâchement complémentaire pour les multiplicateurs d'inégalité (lambda_j c_j = 0), la faisabilité duale (lambda_j >= 0) et la faisabilité primale. Les algorithmes construisent itérativement des itérés qui satisfont ces conditions de manière de plus en plus stricte, les conditions de suffisance du second ordre confirmant qu'un point stationnaire est bien un minimum local.
Formule
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}À chaque itération k, un algorithme calcule une direction de recherche p_k — typiquement via une approximation quasi-newtonienne B_k du Hessien (par exemple, BFGS) ou un système exact de dérivées secondes — et une longueur de pas alpha_k satisfaisant les conditions de Wolfe ou d'Armijo. Les méthodes SQP résolvent un sous-problème quadratique pour p_k, tandis que les méthodes de points intérieurs ajoutent des termes barrières pour gérer les contraintes d'inégalité et diriger les itérés vers l'intérieur réalisable.
Formule
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)La terminaison se produit lorsque la norme du gradient du Lagrangien et la violation maximale de contrainte tombent en dessous des tolérances prescrites (epsilon et delta). Parce que la PNL est généralement non convexe, les algorithmes peuvent converger vers des optima locaux ; des redémarrages multiples à partir de points de départ différents ou des stratégies de recherche globale (ramification et bornage, multistart) sont recommandés lorsque l'optimalité globale est requise.
Formule
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaPièges courants
- Ignorer les qualifications de contrainte et appliquer aveuglément les conditions KKT aux points dégénérés ou non réalisables conduit à des solutions fallacieuses.
- L'utilisation de variables mal mises à l'échelle provoque des approximations de Hessien mal conditionnées et une convergence lente ou échouée.
- Accepter le premier minimum local trouvé sans redémarrages multiples dans des contextes non convexes peut manquer significativement l'optimum global.
- Les approximations de gradient par différences finies introduisent des erreurs numériques ; la différentiation analytique ou automatique est fortement préférée.
Questions fréquentes
Est-ce que tout programme linéaire est aussi un programme non linéaire ?
Oui. La programmation linéaire est un cas particulier de PNL où l'objectif et toutes les contraintes sont affines. Cependant, la PL admet les algorithmes du simplexe et des points intérieurs qui exploitent la linéarité et sont beaucoup plus efficaces que les solveurs PNL généraux ; utiliser un solveur PNL général pour une PL est un gaspillage mais mathématiquement valide.
Quand puis-je être sûr qu'un point KKT est un minimum global ?
Lorsque la PNL est convexe — c'est-à-dire que f est convexe et l'ensemble réalisable est un ensemble convexe — tout point KKT est un minimum global. Pour les problèmes non convexes, cette garantie ne tient pas, et un point KKT n'est qu'un minimum local (sous conditions de suffisance du second ordre). Des méthodes d'optimisation globale telles que la branche et bornage ou les relaxations convexes sont nécessaires autrement.
Quelle est la différence entre les méthodes SQP et les méthodes de points intérieurs ?
SQP résout itérativement des sous-problèmes de programmation quadratique qui approximent localement la PNL et est souvent préférée pour les problèmes de petite à moyenne taille avec de nombreuses contraintes actives. Les méthodes de points intérieurs (barrières) restent strictement à l'intérieur de la région réalisable et ont tendance à mieux s'adapter aux grands problèmes épars. Les deux convergent superlinéairement sous des conditions de régularité appropriées.
Méthodes associées
Sources
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN : 978-0-387-30303-1Copié.