METHODES DE
LINEARISATIONS
• Principe: ramener la résolution du problème non linéaire donné à
celle d'une suite de programmes linéaires d'approximation.
Linéarisation
• 1er procédé : approximation tangentielle
• Étant donné une fonction non linéaire dérivable(), un premier procédé
consiste à lui substituer la fonction affine (linéaire plus constante) de variable
et de paramètre :
• : point de linéarisation
• Les 2 fonctions sont égales si =
• : valable pour une utilisation au voisinage de , donc revient à remplacer le
graphe de () par son plan tangent au point [, ()]
Linéarisation
• 2ème procédé : Changement de variables
• utilisé dans le cas d'un programme du type : Maximiser () sous les conditions
i() 0, i = 1, 2 ... m, lorsque les fonctions sont concaves.
• S’appuie sur la notion de barycentre
Cas d’approximation tangentielle : Stratégie
de linéarisation de Frank-Wolfe
• Soit le problème :
• Si l’ensemble est un polyèdre, on peut se ramener à un problème de
programmation linéaire en faisant une approximation linéaire de
l’objectif
• Ceci correspond à un développement de Taylor du premier ordre et
conduit au sous-problème
• Soit () une solution de ce programme linéaire. On démontre aisément
que la direction = ()− est une direction d’amélioration. On maximise
alors la fonction dans la direction d :
• La solution de cette recherche linéaire conduit au nouveau point +
d’où l’on redémarre le processus
Changement de variables : méthode
barycentrique
• consiste à approcher les graphes des fonctions considérées supposées
concaves, par des surfaces polyédriques inscrites (c'est-à-dire, dont
les sommets sont situés sur le graphe).
• Étant donnée une fonction concave (), et un ensemble fini de points
de , , ,..., , appelés générateurs, les sommets du graphe approché
(défini dans n+1) auront pour coordonnées
• Un point x étant considéré comme un barycentre des générateurs
c'est-à-dire s'exprimant sous la forme :
• on considère le point z Rn+1 qui lui est associé par :
• L'ensemble de tous les points z que l'on peut obtenir de cette
manière est un polyèdre, enveloppe convexe des k points
• Ainsi on peut remplacer une fonction () par une fonction linéaire (l),
de variables lj , j = 1,2,..., k, en ajoutant les conditions linéaires Σlj = 1
et l0.