Programmation non linéaire

La programmation non linéaire (PNL) est une branche de la programmation mathématique et de la recherche opérationnelle qui traite des problèmes d'optimisation où la fonction objectif et/ou au moins une des contraintes sont des fonctions non linéaires des variables de décision.

La PNL est une généralisation de la programmation linéaire et permet de modéliser une classe plus large de systèmes et de processus réels, où les dépendances entre les variables ne sont pas strictement proportionnelles (c'est-à-dire qu'elles sont décrites par des courbes plutôt que par des lignes droites).

Objet et finalité

La programmation non linéaire est utilisée pour trouver des solutions optimales dans des situations où :

• La dépendance de l'indicateur cible (profit, coûts, efficacité, etc.) par rapport aux paramètres de contrôle est non linéaire (par exemple, des rendements d'échelle décroissants, des coûts quadratiques).
• Les contraintes sur les ressources ou les processus technologiques sont décrites par des relations non linéaires (par exemple, des réactions chimiques, des lois physiques, des dépendances économiques).

Les problèmes de PNL se posent dans de nombreux domaines :

• Ingénierie (optimisation de conceptions, de processus).
• Économie et finance (optimisation de portefeuille en tenant compte du risque, modélisation de marché).
• Génie chimique (optimisation des régimes de réacteurs).
• Apprentissage automatique (entraînement de réseaux de neurones, méthode des machines à vecteurs de support).
• Gestion des processus de production. Logistique (en tenant compte des coûts non linéaires).

Formulation mathématique du problème de PNL

Le problème général de la programmation non linéaire est formulé comme suit :

Il s'agit de trouver un ensemble de valeurs pour les variables de décision qui maximise ou minimise une fonction objectif non linéaire. Les valeurs de ces variables doivent satisfaire un système de contraintes, qui peuvent être exprimées sous forme d' inégalités (par exemple, "la quantité A doit être inférieure ou égale à B") ou d' égalités (par exemple, "la quantité C doit être exactement égale à D"). Il est essentiel qu'au moins une des fonctions décrivant l'objectif ou les contraintes soit non linéaire. Souvent, des conditions de non-négativité sont ajoutées pour les variables, exigeant que leurs valeurs soient supérieures ou égales à zéro.

L'ensemble de toutes les combinaisons de valeurs des variables qui satisfont les contraintes forme l' ensemble des solutions admissibles (ESA).

Différences avec la programmation linéaire

La programmation non linéaire diffère considérablement de la programmation linéaire (PL) :

• Non-linéarité : La fonction objectif ou les contraintes (ou les deux) contiennent des dépendances non linéaires.
• Propriétés de l'ESA : L'ensemble des solutions admissibles en PNL peut être non convexe (contrairement à la PL, où l'ESA est toujours un polyèdre convexe).
• Propriétés de l'optimum : En PNL, la solution optimale ne se trouve pas nécessairement à un sommet de l'ESA ; elle peut se situer sur une frontière ou à l'intérieur de l'ensemble. La PNL peut présenter des optimums locaux qui ne sont pas des optimums globaux.
• Complexité de la résolution : Les problèmes de PNL sont généralement beaucoup plus difficiles à résoudre que les problèmes de PL. Il n'existe pas d'algorithme universel unique, analogue à la méthode du simplexe, pour tous les problèmes de PNL.

Principales difficultés et défis de la PNL

La résolution des problèmes de programmation non linéaire présente plusieurs difficultés :

• Présence d'extremums locaux : La plupart des méthodes de PNL ne garantissent que la découverte d'un optimum local (une solution qui est la meilleure dans un certain voisinage). La recherche de l'optimum global (la meilleure solution dans tout l'ESA) est une tâche complexe, en particulier pour les problèmes non convexes.
• Non-convexité : Si le problème n'est pas convexe (la fonction objectif ou l'ESA est non convexe), il peut exister de multiples optimums locaux, et les méthodes de gradient standard peuvent rester "bloquées" dans l'un d'eux.
• Complexité computationnelle : Les algorithmes de résolution de la PNL requièrent souvent des ressources de calcul beaucoup plus importantes que ceux de la PL.

Classes importantes de problèmes de PNL

Malgré la complexité générale, il existe des sous-classes importantes de problèmes de PNL pour lesquelles des méthodes de résolution efficaces ont été développées :

• Programmation convexe : Problème de minimisation d'une fonction convexe sur un ensemble de solutions admissibles convexe (ou de maximisation d'une fonction concave). Propriété clé : tout minimum local est également un minimum global. Cela simplifie considérablement la recherche de la solution optimale.
• Programmation quadratique : La fonction objectif est quadratique, et toutes les contraintes sont linéaires.
• Programmation séparable : La fonction objectif et les contraintes peuvent être représentées comme des sommes de fonctions, chacune ne dépendant que d'une seule variable.

Méthodes de résolution des problèmes de PNL

I. Méthodes d'optimisation sans contraintes :

• Méthodes de gradient (méthode de la plus forte pente, méthode des gradients conjugués) ;
• Méthode de Newton et méthodes quasi-newtoniennes (par exemple, BFGS) ;
• Méthodes utilisant une approximation de la hessienne.

II. Méthodes d'optimisation avec contraintes :

• Méthodes de transformation :
  • Méthode des fonctions de pénalité (penalty methods) ;
  • Méthode des fonctions barrières (barrier methods).
• Méthodes de recherche directe de directions :
  • Méthode des directions réalisables.
• Méthodes basées sur les conditions d'optimalité :
  • Conditions de Karush-Kuhn-Tucker (conditions KKT) ;
  • Méthode des multiplicateurs de Lagrange.
• Méthodes itératives :
  • Programmation quadratique séquentielle (SQP) ;
  • Méthodes de points intérieurs.

III. Méthodes d'optimisation globale :

• Méthodes heuristiques et métaheuristiques :
  • Algorithmes génétiques ;
  • Recuit simulé ;
  • Recherche tabou (tabu search).
• Méthodes déterministes :
  • Séparation et évaluation (branch and bound) ;
  • Algorithmes d'optimisation globale pour les problèmes à structure particulière.

Bibliographie

• Bazaraa, Mokhtar S.; Shetty, C. M. Nonlinear Programming: Theory and Algorithms. — Wiley, 1979.
• Fiacco, Anthony V.; McCormick, Garth P. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. — Wiley, 1968.
• Himmelblau, David M. Applied Nonlinear Programming. — McGraw-Hill, 1972.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — 2nd ed. — Springer, 2006.

Voir aussi

• Recherche opérationnelle
• Optimisation
• Programmation linéaire
• Programmation convexe
• Fonction objectif
• Contraintes
• Ensemble des solutions admissibles