Programmation non linéaire - Nonlinear programming

En mathématiques , la programmation non linéaire ( PNL ) est le processus de résolution d'un problème d' optimisation où certaines des contraintes ou la fonction objectif sont non linéaires . Un problème d'optimisation est un problème de calcul des extrema (maxima, minima ou points stationnaires) d'une fonction objectif sur un ensemble de variables réelles inconnues et conditionnelles à la satisfaction d'un système d' égalités et d' inégalités , collectivement appelés contraintes . C'est le sous-domaine de l'optimisation mathématique qui traite des problèmes qui ne sont pas linéaires.

Applicabilité

Un problème non convexe typique est celui de l'optimisation des coûts de transport en choisissant parmi un ensemble de méthodes de transport, dont une ou plusieurs présentent des économies d'échelle , avec diverses connectivités et contraintes de capacité. Un exemple serait le transport de produits pétroliers étant donné une sélection ou une combinaison d'un pipeline, d'un camion-citerne, d'un camion-citerne, d'une barge fluviale ou d'un navire-citerne côtier. En raison de la taille économique des lots, les fonctions de coût peuvent présenter des discontinuités en plus des changements progressifs.

En science expérimentale, certaines analyses de données simples (telles que l'ajustement d'un spectre avec une somme de pics d'emplacement et de forme connus mais de magnitude inconnue) peuvent être effectuées avec des méthodes linéaires, mais en général, ces problèmes sont également non linéaires. Typiquement, on a un modèle théorique du système à l'étude avec des paramètres variables et un modèle de l'expérience ou des expériences, qui peuvent également avoir des paramètres inconnus. On essaie de trouver un meilleur ajustement numériquement. Dans ce cas, on veut souvent une mesure de la précision du résultat, ainsi que le meilleur ajustement lui-même.

Définition

Soient n , m et p des entiers positifs. Soit X un sous - ensemble de R n , laisser f , g i , et h j être des fonctions à valeurs réelles sur X pour chaque i dans { 1 , ..., m } et chaque j dans { 1 , ..., p }, avec au au moins l'un de f , g i et h j étant non linéaire.

Un problème de minimisation non linéaire est un problème d'optimisation de la forme

Un problème de maximisation non linéaire est défini de manière similaire.

Types de jeu de contraintes possibles

Il existe plusieurs possibilités pour la nature de l'ensemble de contraintes, également appelé ensemble réalisable ou région réalisable .

Un problème infaisable est un problème pour lequel aucun ensemble de valeurs pour les variables de choix ne satisfait toutes les contraintes. C'est-à-dire que les contraintes sont mutuellement contradictoires et qu'aucune solution n'existe ; l'ensemble réalisable est l' ensemble vide .

Un problème réalisable est un problème pour lequel il existe au moins un ensemble de valeurs pour les variables de choix satisfaisant toutes les contraintes.

Un problème non borné est un problème réalisable pour lequel la fonction objectif peut être rendue meilleure que n'importe quelle valeur finie donnée. Ainsi, il n'y a pas de solution optimale, car il existe toujours une solution réalisable qui donne une meilleure valeur de fonction objectif que n'importe quelle solution proposée.

Méthodes pour résoudre le problème

Si la fonction objectif est concave (problème de maximisation) ou convexe (problème de minimisation) et que l'ensemble de contraintes est convexe , alors le programme est appelé convexe et les méthodes générales d' optimisation convexe peuvent être utilisées dans la plupart des cas.

Si la fonction objectif est quadratique et que les contraintes sont linéaires, des techniques de programmation quadratique sont utilisées.

Si la fonction objectif est le rapport d'une fonction concave et d'une fonction convexe (dans le cas de la maximisation) et que les contraintes sont convexes, alors le problème peut être transformé en un problème d'optimisation convexe en utilisant des techniques de programmation fractionnaire .

Plusieurs méthodes sont disponibles pour résoudre des problèmes non convexes. Une approche consiste à utiliser des formulations spéciales de problèmes de programmation linéaire. Une autre méthode implique l'utilisation de techniques de branchement et de limite , où le programme est divisé en sous-classes à résoudre avec des approximations convexes (problème de minimisation) ou linéaires qui forment une limite inférieure sur le coût global au sein de la subdivision. Avec les divisions suivantes, à un moment donné, une solution réelle sera obtenue dont le coût est égal à la meilleure borne inférieure obtenue pour l'une des solutions approximatives. Cette solution est optimale, bien que peut-être pas unique. L'algorithme peut également être arrêté prématurément, avec l'assurance que la meilleure solution possible se situe dans une tolérance à partir du meilleur point trouvé ; de tels points sont appelés ε-optimaux. Une terminaison aux points ε-optimaux est généralement nécessaire pour assurer une terminaison finie. Ceci est particulièrement utile pour les problèmes importants et difficiles et les problèmes avec des coûts ou des valeurs incertains où l'incertitude peut être estimée avec une estimation de fiabilité appropriée.

Sous les qualifications de différentiabilité et de contraintes , les conditions de Karush-Kuhn-Tucker (KKT) fournissent les conditions nécessaires pour qu'une solution soit optimale. Sous convexité, ces conditions sont également suffisantes. Si certaines fonctions sont non différentiables, sous - différentiel versions de conditions Karush-Kuhn-Tucker (KKT) sont disponibles.

Exemples

exemple en 2 dimensions

Image
La région bleue est la région réalisable . La tangence de la droite avec la région des possibles représente la solution. La ligne est la meilleure courbe de niveau réalisable (locus avec une valeur donnée de la fonction objectif).

Un problème simple (montré dans le diagramme) peut être défini par les contraintes

x 1 0
x 2 0
x 1 2 + x 2 2 1
x 1 2 + x 2 2 2

avec une fonction objectif à maximiser

f ( x ) = x 1 + x 2

où x = ( x 1 , x 2 ).

exemple en 3 dimensions

Image
La tangence de la surface supérieure avec l'espace contraint au centre représente la solution.

Un autre problème simple (voir schéma) peut être défini par les contraintes

x 1 2 − x 2 2 + x 3 2 2
x 1 2 + x 2 2 + x 3 2 ≤ 10

avec une fonction objectif à maximiser

f ( x ) = x 1 x 2 + x 2 x 3

où x = ( x 1 , x 2 , x 3 ).

Voir également

Les références

Lectures complémentaires

Liens externes