Optimisation Non Linéaire Sans Contraintes PDF

OPTIMISATION NON LINÉAIRE SANS CONTRAINTES Table of Contents 1 Notions fondamentales 2 1.1 Classification des problèmes d’optimisation.............. 3 1.2 Différentiabilité: Premier ordre........................

OPTIMISATION NON LINÉAIRE SANS CONTRAINTES Table of Contents 1 Notions fondamentales 2 1.1 Classification des problèmes d’optimisation.............. 3 1.2 Différentiabilité: Premier ordre...................... 4 1.3 Différentiabilité: Second ordre....................... 13 1.4 Formule de Taylor.............................. 13 1.5 Signe d’une matrice............................. 14 1  Notions fondamentales 1 PARTIE La programmation non linéaire traite du problème d’optimisation d’une fonction ob- jectif en présence de contraintes d’égalité et d’inégalité. Si toutes les fonctions sont linéaires, nous avons évidemment un programme linéaire. Sinon, le problème est ap- pelé programme non linéaire. Le développement d’algorithmes et de logiciels haute- ment efficaces et robustes pour la programmation linéaire, l’avènement des ordina- teurs haute vitesse et la sensibilisation des gestionnaires et des praticiens aux avan- tages et à la rentabilité de la modélisation mathématique et de l’analyse ont fait de la programmation linéaire un outil important pour résoudre des problèmes dans divers domaines. Cependant, de nombreux problèmes réalistes ne peuvent pas être adéquate- ment représentés ou approximés en tant que programme linéaire, en raison de la nature de la non-linéarité de la fonction objectif et/ou de la non-linéarité de l’une des con- traintes. Les efforts pour résoudre de tels problèmes non linéaires de manière efficace ont progressé rapidement au cours des quatre dernières décennies. Le problème d’optimisation Consiste à trouver, parmi un ensemble de solutions respec- tant des contraintes, une solution qui optimise une fonction objectif. Par optimiser, on entend trouver la plus petite valeur (problème de minimisation) ou la plus grande valeur (problème de maximisation) de la fonction. Étant donné un ensemble S ⊂ Rn et une fonction f : S → R, la forme générale d’un prob- lème d’optimisation est la suivante min{ f (x) : x ∈ S} (1) où S ⊂ Rn est appelé ensemble des solutions admissibles ou réalisables, x ∈ Rn s’appelle vecteur des variables de décision, f s’appelle fonction économique ou fonction objectif. 2  Si S = Rn , le problème d’optimisation (1) s’appelle problème d’optimisation sans contraintes. Le problème (1) est un problème d’optimisation sans contraintes non linéaire si f n’est pas affine. Si l’ensemble S est défini par des équations ou des inéquations, le problème (1) s’appelle dans ce cas problème d’optimisation avec contraintes. Résoudre un problème d’optimisation consiste à trouver (s’il en existe) un élément x min de S minimisant la fonction f sur S, c’est-à-dire, tel que f (x min ) ≤ f (x) ∀x ∈ S 1.1 Classification des problèmes d’optimisation Les problèmes d’optimisation diffèrent selon l’espace de recherche, les contraintes, la fonction objectif, etc. Selon la nature de la fonction objectif et la nature des contraintes on distingue deux classes d’optimisation : Optimisation linéaire dans Rn : le problème (1) s’appelle problème d’optimisation linéaire avec contraintes si la fonction objectif f et toutes les contraintes sont affines.     mi n f (x) = C x  (P ) sous Ax ≤ b    x ≥ 0 où : A ∈ Rm×n , b ∈ Rm×1 et C ∈ R1×n Optimisation non linéaire dans Rn : le problème (1) est un problème d’optimisation non linéaire avec contraintes si f ou l’une des contraintes est non linéaire.     mi n f (x)  (P ) sous g i (x) ≤ 0   x ∈ Rn  où f et g i , i = 1..., m sont des fonctions non linéaires. Cas particuliers: Programmation quadratique: Dans ce cas, la fonction f est de la forme quadratique et les fonctions g i sont linéaires.     mi n f (x) = 1/2x t Qx + b t x + c  (P ) sous Ax ≤ b    x ≥ 0 où Q est une n × n− matrice et b est un n−vecteur réel. Programmation con vexe: Les fonctions f et g i , i = 1,..., m sont convexes 3 Problème Soit un rectangle de périmètre 300 cm. Déterminer les dimensions qui maximisent sa surface. L’hypothèse de base dans le cadre de ce cours est que la fonction objectif f ainsi que les contraintes sont continues et différentiables sur S. Nous jugeons utiles de rappeler ci-dessous, les principaux concepts de la différentiabilité : 1.2 Différentiabilité: Premier ordre Nous rappelons, lorsque n = 1, la dérivée de f : R → R en x̄ ∈ R est donnée par f (x̄ + t ) − f (x̄) f ′ (x̄) = lim t →0 t à condition que cette limite existe et soit finie, c’est-à-dire f (x̄ + t ) − f (x̄) + f ′ (x̄)t ¡ ¢ lim =0 t →0 t autrement dit, la fonction affine y = f (x̄) + f ′ (x̄)(x − x̄) (dont le graphe est la droite tan- gente au graphe de f en (x̄, f (x̄))) est une bonne approximation de y = f (x) au voisi- nage de x̄. La fonction linéaire h 7→ f ′ (x̄)h est la différentielle de f en x̄ son graphe est la droite passant par l’origine et parallèle à la tangente mentionnée). La pente de ces lignes, f ′ (x̄), est la tangente trigonométrique de l’angle entre la ligne tangente au graphe de f en (x̄, f (x̄) ) et l’axe des x, et représente le taux de variation de f lorsqu’on se déplace depuis x̄. Lorsque n > 1 , plusieurs concepts sont des candidats concurrents pour étendre la notion de dérivée de f en x̄ ∈ R. Par souci de simplicité, nous supposons que n = 2. Définition 1.1 La dérivée partielle de f par rapport à x 1 en x̄ est le taux de variation de f lorsqu’on se déplace depuis x̄ dans la direction de l’axe x 1. Plus précisément, ∂ f (x̄) f (x̄ 1 + t , x̄ 2 ) − f (x̄ 1 , x̄ 2 ) = lim ∂x 1 t →0 t dont la signification géométrique n’est autre que la pente de la ligne tangente à l’intersection du graphe de f avec le plan vertical x 2 = x̄ 2. De manière analogue, la dérivée partielle de f par rapport à x 2 en x̄ est ∂ f (x̄) f (x̄ 1 , x̄ 2 + t ) − f (x̄ 1 , x̄ 2 ) = lim ∂x 2 t →0 t L’interprétation géométrique des dérivées partielles d’une fonction f est illustrée dans les Figures 1 et 2: Définition 1.2 Lorsque les deux dérivées partielles de la fonction f en x̄ existent, le gra- dient de f en x̄ est défini comme le vecteur à ∂ f (x̄) ! ∂x 1 ∇ f (x̄) = ∂ f (x̄) ∂x 2 4  ∂ f (x) Figure 1: Interprétation géométrique de ∂x 1 ∂ f (x) Figure 2: Interprétation géométrique de ∂x 2 5  Figure 3: Plan tangent au graphe de f en un point donné. Considérons les lignes tangentes aux courbes lisses (ou de classe C k ) contenues dans gph f et passant par f (x̄x̄). Dans le cas où toutes ces lignes tangentes se trouvent dans ¡ ¢ un même plan, ce plan est appelé le plan tangent à gph f en f (x̄x̄) (voir Figure 3). ¡ ¢ Définition 1.3 (Dérivée partielle) Soit f : Rn → R une fonction continue. La fonction notée ∇i f (x) : Rn → R, également ∂ f (x) notée ∂x i est appelée ième dérivée partielle de f et est définie par: ∂ f (x) f (x 1 ,..., x i + α,..., x n ) − f (x 1 ,..., x i ,..., x n ) ∇i f (x) = = lim. ∂x i α→0 α Cette limite peut ne pas exister. ∂ f (x) Si les dérivées partielles ∂x i existent pour tout i , le gradient de f est défini de la façon suivante. Définition 1.4 (Gradient) Soit f : Rn → R une fonction continue. La fonction notée ∇ f (x) : Rn → Rn est appelée le gradient de f et est définie par: ∂ f (x) ∂ f (x) ∂ f (x) µ ¶ ∇ f (x) = , ,..., ∈ Rn. ∂x 1 ∂x 2 ∂x n Elle peut ne pas exister pour certains vecteurs x ∈ Rn 6  Figure 4: Vecteurs tangents aux courbes. Si les deux dérivées partielles de f en x̄ existent, les courbes obtenues par intersection de gph f avec les plans x 2 = x̄ 2 et x 1 = x̄ 1 ont pour équations paramétriques   x 1 = x̄ 1 + t    x 1 = x̄ 1    x 2 = x̄ 2 and x 2 = x̄ 2 + t   x 3 = f (x̄ 1 + t , x̄ 2 ) x 3 = f (x̄ 1 , x̄ 2 + t )     dont les vecteurs tangents en f (x̄x̄) sont donnés par les dérivées correspondantes à t = 0 ¡ ¢ ∂ f (x̄) T ³ ´ (je dérive par rapport a t après je remplace par t=0), c’est-à-dire les vecteurs 1, 0, ∂x1 ∂ f (x̄) T ³ ´ ¡ f (x̄)¢ et 0, 1, ∂x2 , qui sont orthogonaux au vecteur ∇−1. Par conséquent, le vecteur ¡∇ f (x̄)¢ ¡ x̄ ¢ −1 doit être orthogonal au plan tangent à gph f en f (x̄) , à condition que ce plan tangent existe. Autrement dit, lorsque le plan tangent existe, son équation est néces- sairement donnée par :   à !T x 1 − x̄ 1 ∇ f (x̄)   =0  x 2 − x̄ 2 −1   x 3 − f (x̄ 1 , x̄ 2 ) à ! T x 1 − x̄ 1 x 3 = f (x̄ 1 , x̄ 2 ) + ∇ f (x̄) x 2 − x̄ 2 Voir les figures 4 and 5. L’existence de toutes les dérivées partielles ne suffit pas à garan- 7  Figure 5: Plan tangent et vecteur orthogonal à gph f. tir l’existence d’un plan tangent, comme le montre la Fig. 6. La définition de la dif- férentiabilité de f en x̄ exige que la fonction affine dont le graphe est donné par (1.5), c’est-à-dire le plane tangent x 3 = f (x̄) + ∇ f (x̄)T (x − x̄), est une bonne approximation de f à proximité de x̄. Plus précisément, on dit que la fonction f est différentiable en x̄ ∈ int dom f lorsque ses dérivées partielles enx̄ existent et que f (x) − f (x̄) + ∇ f (x̄)T (x − x̄) £ ¤ lim x→x̄ ∥x − x̄∥ f (x̄ + h) − f (x̄) + ∇ f (x̄)T h £ ¤ = lim =0 h→02 ∥h∥ (où nous avons fait le changement de variable x = x̄ + h ). La différentielle de f en x̄ est la fonction linéaire h 7→ ∇ f (x̄)T h, dont le graphe est le plan passant par l’origine et parallèle au plan tangent au graphe de f en f (x̄x̄). Les fonctions polynomiales, parmi ¡ ¢ d’autres, sont différentiables en tout point de leurs domaines. Lorsque u ∈ R2 \ {02 } et que f est différentiable en x̄, en prenant h = t u dans (1.6), on obtient f (x̄ + t u) − f (x̄) + t ∇ f (x̄)T u £ ¤ lim =0 t →0 ∥u∥|t | f (x̄ + t u) − f (x̄) + t ∇ f (x̄)T u £ ¤ lim =0 t →0 ∥u∥|t | Donc, nous avons que : 8  x 23 Figure 6: La fonction f (x) = x 12 +x 22 n’est pas différentiable à l’origine, malgré le fait que toutes les dérivées partielles existent. 9 Figure 7: Interprétation géométrique de f ′ ((1, 2)T ; ( p1 , p1 )T ) 2 2 10  f (x̄ + t u) − f (x̄) + t ∇ f (x̄)T u £ ¤ lim =0 t →0 t À partir de l’équation (1.7), il s’ensuit que : f (x̄ + t u) − f (x̄) lim = ∇ f (x̄)T u t →0 t Lorsqu’il existe et est fini, le premier membre de (1.8) est appelé la dérivée directionnelle de f en x̄ dans la direction de u, et est noté f ′ (x̄; u). Il représente le taux de changement de f lorsque l’on se déplace de x̄ dans la direction de u, à condition que ∥u∥ = 1, voir Fig. 1.14. Ainsi, lorsque f est différentiable en x̄, f ′ (x̄; u) = ∇ f (x̄)T u Nous avons vu que, lorsque f est différentiable en x̄, le plan tangent à gph f en f (x̄x̄) ¡ ¢ ¡ f (x̄)¢ est orthogonal à ∇−1. Ainsi, ce dernier vecteur est orthogonal à tout vecteur tan- ¡ x̄ ¢ gent en f (x̄) des courbes contenues dans la surface gph f. En particulier, il doit être orthogonal au vecteur tangent à la courbe résultant de l’intersection de gph f avec le plan horizontal passant par f (x̄x̄) , dont l’équation est x 3 = f (x̄). Un tel vecteur tangent ¡ ¢ horizontal est de la forme v0 , où v est tangent à la courbe de niveau f (x̄), c’est-à-dire ¡ ¢ {x ∈ dom f : f (x) = f (x̄)}. Nous avons donc à !T à ! ∇ f (x̄) v = ∇ f (x̄)T v = 0 −1 0 Ainsi , ∇ f (x̄) est orthogonal à la courbe de niveau qui contient x̄. D’autre part, si ∥u∥ = 1 et nous notons θ l’angle entre u et ∇ f (x̄), par (1.9) nous avons f ′ (x̄; u) = ∇ f (x̄)T u = ∥∇ f (x̄)∥∥u∥ cos θ = ∥∇ f (x̄)∥ cos θ dont la valeur maximale (minimale) est atteinte lorsque cos θ = 1(cos θ = −1), c’est-à- dire, θ = 0 ( θ = π, respectivement). Par conséquent, la dérivée ³ directionnelle de f en ∇ f (x̄) ∇ f (x̄) x̄ atteint sa valeur maximale (minimale) lorsque u = ∥∇ f (x̄)∥ u = − ∥∇ f (x̄)∥ , respective- ment). En conclusion, ∇ f (x̄) s’avère être orthogonal à la courbe de niveau de f à travers x̄ et sa direction est celle qui fournit son taux de croissance maximal. Définition 1.5 (Dérivée directionnelle) Soit f : Rn → R une fonction continue. Soient x ∈ Rn et d ∈ Rn. La dérivée directionnelle de f en x ∈ Rn dans la direction d ∈ Rn est donnée par: f (x + αd ) − f (x) lim+ , α→0 α si la limite existe. De plus, lorsque le gradient existe, la dérivée directionnelle est d ⊤ ∇ f (x). 11 Les dérivée partielles sont en fait les dérivées directionnelles dans la direction des dif- férents axes des coordonnées et ∂ f (x) = ∇ f (x)e i , ∂x i où e i est la colonne i de la matrice identité. Exemple 1 Soit f (x, y) = x 2 + x y + y 2 Calculer la dérivée directionnelle de f en x = (1, 1) dans la direction d t = (1, −2). La dérivée directionnelle donne des information sur la pente de la fonction dans la di- rection d , tout comme la dérivée donne des informations sur la pente des fonctions à une variable. Notamment, la fonction est croissante dans la direction d si la dérivée directionnelle est strictement positive et décroissante si elle est strictement négative. Dans ce dernier cas, nous dirons qu’il s’agit d’une direction de descente. La direction d ∈ Rn est une direction de descente de f en x ∈ Rn si f d′ (x) = d ⊤ ∇ f (x) < 0 Parmi toutes les directions d à partir d’un point x celle où la pente est la plus forte est la direction du gradient ∇ f (x). Pour démontrer cela nous considérons toutes les direc- tions d ayant la même norme que le gradient et comparons la dérivé directionnelle pour chacune d’elles. Théorème 1.1 Soit f : Rn → R une fonction différentiable. Soient x ∈ Rn et d ∗ = ∇ f (x). Alors pour tout d ∈ Rn tel que ∥ d ∥=∥ ∇ f (x) ∥ on a d T ∇ f (x) ≤ d ∗T ∇ f (x) = ∇ f (x)T ∇ f (x) Preuve 1 Soit d une direction quelconque. Nous avons d T ∇ f (x) ≤∥ d ∥∥ ∇ f (x) ∥ =∥ ∇ f (x) ∥2 = ∇ f (x)T ∇ f (x) = (d ∗ )T ∇ f (x) Comme (d ∗ )T ∇ f (x) =∥ ∇ f (x) ∥2 >= 0, la fonction est croissante dans la direction (d ∗ ), qui correspond bien à la plus forte pente. Si la direction du gradient correspond à la plus fort pente de la fonction en x il suffit de considérer la direction opposé au gradient −∇ f (x) pour trouver la plus forte descente. Théorème 1.2 Soient f : Rn → R une fonction différentiable. Soient x ∈ Rn tel que | ∇ f (x) ̸= 0 et x ∈ Rn. Si d est une direction de descente, alors il existe µ > 0 tel que : f(x + αd) < f(x) 0 < α ≤ µ 12 1.3 Différentiabilité: Second ordre Définition 1.6 (Matrice Hessienne) Soit f : X ⊂ Rn → R une fonction deux fois différentiable. La fonction notée ∇2 f (x) : Rn → Rn × Rn est appelée matrice Hessienne, ou Hessien de f, et est définie par: ∂2 f µ ¶ 2 ∇ f (x) = (x). ∂x i ∂x j ij La matrice Hessienne est toujours symétrique. ∂2 f ∂ f µ ¶ µ 2 ¶ (x) = (x) ∂x i ∂x j ∂x j ∂x i 1.4 Formule de Taylor Théorème 1.3 (Taylor au premier ordre) Soit f : Rn → R une fonction continûment différentiable. Pour tout x ∈ S et h suffisamment petit: f (x + h) = f (x) + h t ∇ f (x) + Θ(∥ h ∥) (formule de Taylor-young) Θ(∥ h ∥) =∥ h ∥ ϵ(h) où lim∥h∥→0 ϵ(h) = 0 Pour tout x ∈ S et h suffisamment petit; il existe α ∈ ]0, 1[ tel que: f (x + h) = f (x) + h t ∇ f (x + αh) (formule de Taylor-lagrange) Théorème 1.4 (Taylor au second ordre) Soit f : Rn → R une fonction deux fois différentiable. Pour tout x ∈ S et h suffisamment petit: 1 f (x + h) = f (x) + h t ∇ f (x) + h t ∇2 f (x)h + Θ(∥ h ∥2 ) 2 (formule de Taylor-young) Pour tout x ∈ S et h suffisamment petit; il existe α ∈ ]0, 1[ tel que: 1 f (x + h) = f (x) + h t ∇ f (x) + h t ∇2 f (x + αh)h 2 (formule de Taylor-lagrange) 13 1.5 Signe d’une matrice A ∈ Rn×n symétrique est dite : semi-définie positive si y ⊤ Ay ≥ 0 pour tout y ∈ Rn définie positive si y ⊤ Ay > 0 pour tout y ∈ Rn ̸= 0; semi-définie négative si y ⊤ Ay ≤ 0 pour tout y ∈ Rn définie négative si y ⊤ Ay < 0 pour tout y ∈ Rn ̸= 0 à ! 1 −1 ¢2 , f (y) = y 12 + 4y 22 − 2y 1 y 2 = y 1 − y 2 + 3y 22 est strictement ¡ Exemple 2 A = −1 4 ¡ ¢ positif ∀ y 1 , y 2 ̸= (0, 0).A est donc définies positives. En pratique, on peut vérifier le signe d’une matrice en examinant ses valeurs propres ou ses mineurs principaux. A est semi-définie positive (resp. négative) ssi toutes ses valeurs propres sont ≥ 0 (resp. ≤ 0 ). A est définie positive (resp. négative) ssi toutes ses valeurs propres sont > 0 (resp. < 0 ). à ! 1 −1 Exemple 3 les valeurs propres de A = sont les racines du polynôme carac- −1 4 p p téristique det(A −λI ) = (1−λ)(4−λ)−1 soit λ1 = 5+ 2 13 et λ2 = 5− 2 13.λ1 et λ2 sont stricte- ment positives et donc A est définie positive. Les mineurs principaux   a 11 a 12 ··· a 1n    a 12 a 22 ··· a 2n  Si A = .   ......  .. ···   a 1n a 2n · · · a nn ¯ ¯ ¯ a ¯ 11 a 12 ¯ alors ∆1 = a 11 , ∆2 = ¯ ¯ ,... , ∆n = det(A) sont les mineurs principaux de A. ¯ ¯ a 12 a 22 ¯ A est définie positive si et seulement si (−A) est définie négative A est définie positive ssi ∆k > 0, ∀k = 1,... , n A est définie négative ssi (−1)k ∆k > 0, ∀k = 1,... , n à ! 1 −1 Exemple 4 A = , ∆1 = 1, ∆2 = 3.A est donc définie positive. −1 4 14  à ! a c Soit A = , c d A est semi-définie positive ssi a ≥ 0, d ≥ 0, ad − c 2 ≥ 0. A est définie positive ssi a > 0, d > 0, ad − c 2 > 0. Soit A une matrice carrée d’ordre n, symétrique, alors: S’il existe i ∈ {1,..., n} tel que a i i ≤ 0 alors A n’est pas définie positive. S’il existe i ∈ {1,..., n} tel que a i i < 0 alors A n’est pas semi-définie positive. S’ils existent i , j ∈ {1,..., n}(i ̸= j ) tels que a i i = 0 et a i j ̸= 0 alors A n’est pas semi- définie positive. 15