La programmation non linéaire  

Généralités sur la programmation non linéaire

De nombreuses applications industrielles de l’optimisation impliquent une modélisation plus proche de la physique. En optimisation de la conception par exemple, on optimise des méta-modèles ou surfaces de réponse issus d’un modèle statistique qui ne sont pas linéaires. De même l’optimisation topologique ou l’optimisation de forme fait largement appel à des modèles non linéaires et de plus de très grande taille dans cet exemple.

Formellement un programme mathématique non linéaire s’écrit :
Min f(x)
g_j(x) <=0 j = 1,…,m
x vecteur de nombre réels représentant les variables de décision

Les techniques pour résoudre les problèmes mathématiques et la performance des algorithmes d’optimisation dépendent de la nature de la fonction objectif et des fonctions contraintes.

• La programmation linéaire traite le cas où f(x) et g_j(x) sont linéaires. L’algorithme du simplexe ou les méthodes intérieures permettent de résoudre de problèmes de très grande taille (centaine de milliers à quelques millions de variables et plusieurs dizaines milliers de contraintes).
• La programmation quadratique traite le cas où la fonction objectif f(x) est quadratique, et les contraintes g_j(x) sont linéaires. Des algorithmes performants traitent ce cas particulier rencontré par exemple dans des problématiques d’optimisation de portefeuilles financiers.
• la programmation stochastique et la programmation robuste abordent des situations où des données sont connues en probabilité (variables aléatoires) ou de façon imprécise (cadre de la programmation robuste).
• la programmation dynamique est adaptée aux cas où une solution optimale se compose nécessairement de sous-solutions optimales (exemple de propriété utilisée pour la recherche de plus courts chemins dans des graphes) et de plus courts chemins sous contraintes (algorithmes mis en œuvre dans des méthodes de génération de colonnes pour résoudre le sous-problème dans des composants tels que LP-ShiftPlanner).
• la programmation non-linéaire étudie le cas général dans lequel l’objectif f(x) ou les contraintes g_j(x) (ou les deux) sont des fonctions non-linéaires

La plupart des méthodes de programmation non linéaires utilisent la notion de gradient des fonctions f(x) et g_j(x) pour calculer des directions de descente cad d’amélioration de la fonction objectif. Dans le cas de la programmation linéaire le gradient est le vecteur c de la fonction objectif et il ne varie pas dans l’espace des solutions.
Lorsque les fonctions sont convexes (cas par exemple de la programmation linéaire continue), des algorithmes de descentes convergent vers un optimum global. Dans le cas général, ces algorithmes et les logiciels correspondant ne convergent que vers un optimum local et il importe lorsque c’est possible d’exécuter ces algorithmes à partir de plusieurs solutions initiales différentes pour retenir la meilleure solution parmi celles trouvées.

Un programme non linéaire sous contraintes peut aussi être transformé en un problème sans contraintes à l’aide du multiplicateur de Lagrange : cette méthode revient en effet à introduire dans la fonction objectif des variables d’écart au respect des contraintes et des pénalités croissantes de ces écarts à mesure qu’on se rapproche de la saturation des contraintes correspondantes.

Solveurs et mise en œuvre informatique

Plusieurs solveurs existent pour résoudre des programmes non linéaires.
EURODECISION a expérimenté les solveurs suivants :

• OPT++
• FSQP
• KNITRO
• FAIPA
• GLPK
• LPSOLVE
• Coin-OR : IPOpt, OBOE