Cours Optimisation [PDF]

Zitiervorschau

Optimisation L2-MASS 2013-2014 Pierre Puiseux 20 février 2014

2

3

TABLE DES MATIÈRES

Table des matières 1

2

3

4

Introduction et rappels

5

1.1

Représentation graphique . . . . . . . . . . . . . . . . . . . . .

5

1.2

Formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3

Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.4

Applications quadratiques . . . . . . . . . . . . . . . . . . . .

9

Optimisation sans contrainte

11

2.1

Extrema libres . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2

Dérivée directionnelle, profil . . . . . . . . . . . . . . . . . . .

12

2.3

Condition nécessaire d’optimalité . . . . . . . . . . . . . . . .

14

2.4

Condition suffisante d’optimalité . . . . . . . . . . . . . . . . .

14

2.5

Algorithmes de gradient . . . . . . . . . . . . . . . . . . . . .

16

2.5.1

Gradient à pas fixe . . . . . . . . . . . . . . . . . . . .

17

2.5.2

Gradient à pas optimal . . . . . . . . . . . . . . . . . .

18

Contraintes égalité, multiplicateurs de Lagrange

21

3.1

Définitions et notations . . . . . . . . . . . . . . . . . . . . . .

21

3.2

Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . .

22

3.3

Deux variables et une seule contrainte égalité . . . . . . . . . .

23

3.4

Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.5

En résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Contrainte inégalité

31

4.1

Définition et exemples . . . . . . . . . . . . . . . . . . . . . .

31

4.2

Conditions nécessaires (KKT) . . . . . . . . . . . . . . . . . .

33

4.3

Conditions suffisantes (KKT) . . . . . . . . . . . . . . . . . . .

33

cc le mercredi 5/03 Correction lundi 10/03 Exam mercredi 12/03 Pierre Puiseux

4

TABLE DES MATIÈRES

Avertissement ce ne sont que des notes de cours, en perpétuelle évolution, dans lesquelles subsistent certainement de nombreuses erreurs et approximations !

Notations R : R ∪ {−∞, +∞} C : C ∪ {−∞, +∞} K : R ou C et K : R ou C. χA : fonction caractéristique de l’ensemble A. L (E, F ) : applications linéaires de E dans F (E et F espaces vectoriels). Lc (E, F ) : applications linéaires continues de E dans F (E et F espaces vectoriels normés). |||Φ||| : norme de l’application linéaire Φ. (f |g) produit scalaire. C (A, B) = C 0 (A, B) fonctions continues de A dans B. C p : fonctions de classe C p (u|v) : produit scalaire. x, y, z, . . . des nombres réels x, y, z, . . . des vecteurs de Rn ∇f (x) ou f ′ (x) : le gradient de f au point x. ∇2 f (x) ou f ′′ (x) ou Hf (x) : la matrice hessienne de f au point x.

5

Chapitre 1 Introduction et rappels L’optimisation est l’étude des fonctions f : Rn → R, pour lesquelles on cherche un point a = (a1 , a2 , . . . an ) ∈ C ⊂ Rn en lequel f atteint un maximum ou un minimum. Le point a est recherché dans un ensemble C qui prend en compte certaines contraintes du problème. Un problème d’optimisation (minimisation) s’écrira : { Minf (x) (P) x∈C

On se restreint le plus souvent ici à des fonctions de deux ou trois variables (n = 2). La fonction à optimiser est appelée fonction coût ou fonction objectif.

1.1

Représentation graphique

On considèrera une fonction f d’un ouvert D à valeurs dans R, où D est de la forme D = ]α1 , β1 [ × ]α2 , β2 [ si n = 2 et plus généralement D = ]α1 , β1 [ × ]α2 , β2 [ × · · · × ]αn , βn [ dans Rn . On sait représenter graphiquement une fonction f : R2 → R et traçant dans R3 l’ensemble des points de coordonnées (x, y, z) avec z = f (x, y). On peut également tracer les courbes de niveau ou isovaleurs (comme sur une carte IGN). Pour n > 2 c’est plus délicat, on n’a pas de mode de visualisation directe de f comme dans R2 . Les n−1 isovaleurs sont des surfaces dans R , difficiles à représenter graphiquement. Pierre Puiseux

6

Chapitre 1. Introduction et rappels

1

0.5

-1.5

-1

-0.5

0

0.5

1

1.5

-0.5

-1

Fig. 1.1.1 : Fonction (x, y) 7→ sin (xy), isovaleurs et représentation standard

2

1,5

1

0,5

-2,5

-2

-1,5

-1

-0,5

0

0,5

1

1,5

2

2,5

-0,5

-1

-1,5

-2

( ) 2 2 2 2 2 2 Fig. 1.1.2 : Fonction (x, y) 7→ 3 (x − 1)2 e(−x −(y−1) ) − 10 x5 − x3 − y 5 e−x −y − 13 e(−(x+1) −y ) , isovaleurs et représentation standard

1.2

Formules de Taylor

Rappellons la formule de Taylor à l’ordre 2 pour les fonctions de 1, 2 ou n variables : Théorème. (Formule de Taylor à l’ordre 2) 1. Dimension n = 1 : si f est 2 fois continuement dérivable en a ∈ D alors pour h suffisament proche de 0 1 : f (a + h) = f (a) + f ′ (a) h + f ′′ (a) h2 + h2 ε (h) avec lim ε (h) = 0 h→0

1

h suffisament proche de 0 pour que a + h appartienne à D, afin que f (a + h) ait un sens.

1.3 Convexité

7

2. Dimension n = 2 : si f est 2 fois continuement dérivable en (a, b) ∈ D alors pour (h, k) suffisament proche de (0, 0) : f (a + h, b + k) = f (a, b)+ avec

lim

) ∂f ∂f ∂ 2f ∂ 2f ∂ 2f ( (a, b) h+ (a, b) k+ 2 h2 +2 (a, b) hk+ 2 k 2 h2 + k 2 ε (h, k) ∂x ∂y ∂x ∂x∂y ∂y

ε (h, k) = 0

(h,k)→(0,0)

3. Dimension n : si f est 2 fois continuement dérivable en a ∈ D alors pour h ∈ Rn suffisament proche de 0Rn : f (a + h) = f (a) + ∇f (a) .h + ∇2 f (a) (h, h) + ∥h∥22 ε (h) avec lim ε (h) = 0 h→0Rn

Remarque. Dans cette écriture, ∇f (a) ∈ Rn est le vecteur gradient de f en a, ∇2 f (a) ∈ Rn,n est la matrice hessienne de f en a et ∇2 f (a) (h, h) désigne le produit matriciel h × ∇2 f (a) × ht .   2 ∂2f ∂2f ∂ f   (a) (a) . . . (a) 2 ∂x1 ∂x2 ∂x1 ∂xn ∂x1 h1  2  .. . .     ∂ f . . ( )  . . (a) .   h2  h1 h2 . . . hn ×  ∂x1 ∂x.2 ×   . ... ... ∂2f    ..  .. (a)   ∂xn−1 ∂xn hn ∂2f ∂2f ∂2f (a) ... (a) (a) ∂x1 ∂xn ∂xn−1 ∂xn ∂x2 n

1.3

Convexité

Un résumé très rapide des propriétés de positivité des matrices. Proposition 1.1. Soit n un entier et A ∈ Rn,n une matrice carrée. – On appelle valeurs propres de A les racines du polynôme de degré n pA (λ) = det (A − λIn ) – Si la matrice A est symétrique, alors elle admet n valeurs propres réelles λi , i ∈ J1, nK, certaines de ces valeurs pouvant être multiples, c’est à dire des racines multiples de pA . – Si ∀i ∈ J1, nK, λi ≥ 0 alors la matrice est positive, et on a ∀x ∈ Rn , xt .A.x ≥ 0 – Si ∀i ∈ J1, nK, λi > 0 alors la matrice est définie positive, et on a ∀x ∈ Rn , x ̸= 0 ⇒ xt .A.x > 0 Dans ce cas, A est également inversible.

8

Chapitre 1. Introduction et rappels

Définition 1.1. Une partie de C ⊂ Rn est dite convexe si et seulement si ∀a, b ∈ C , ∀ω ∈ [0, 1] , (1 − ω) a + ωb ∈ C En d’autre termes, tout segment qui relie deux points de C est entièrement dans C . Exemple. – Un ballon de rugby, de foot, sont convexes, un freezebee n’est pas convexe, un gruyère non plus. 2 – le est strictement convexe : si a, b ∈ C et ω ∈ [0, 1] alors (1 − ω) a + ωb = ( carré C = [0, 1] ) (1 − ω) xa + ωxb . Or (1 − ω) ya + ωyb { 0 ≤ xa ≤ 1 et 0 ≤ xb ≤ 1

comme ω et 1 − ω sont positifs, on en déduit : { 0 ≤ (1 − ω) xa ≤ 1 − ω 0 ≤ ωxb ≤ ω

et

et en additionnant : 0 ≤ (1 − ω) xa + ωxb ≤ 1 de manière analogue la deuxième coordonnée de (1 − ω) a + ωb vérifie : 0 ≤ (1 − ω) ya + ωyb ≤ 1 et finalement on a bien (1 − ω) a + ωb ∈ C

Définition 1.2. Soit D un ouvert de Rn et f : D → R. On dit que f est 1. convexe si ∀x, y ∈ D, ∀ω ∈ [0, 1] , f ((1 − ω) x + ωy) ≤ (1 − ω) f (x) + ωf (y) 2. strictement convexe si l’inégalité précédente est stricte : ∀x, y ∈ D, x ̸= y, ∀ω ∈ [0, 1] , f ((1 − ω) x + ωy) < (1 − ω) f (x) + ωf (y) 3. f est (strictement) concave si −f est (strictement) convexe. Autrement dit f est convexe signifie que la représentation graphique de f est en dessous du segment qui joint le point (x, f (x)) au point (y, f (y)).

1.4 Applications quadratiques

9

Fig. 1.3.1 : Fonction strictement convexe, convexe, non convexe Proposition 1.2. Soit D un ouvert convexe de Rn et f : D → R une application deux fois continuement dérivable. Alors – f est convexe ◃ si et seulement si ∇2 f (x) est une matrice positive pour tout x ∈ D, ◃ si et seulement si les valeurs propres de ∇2 f (x) sont toutes positives pour tout x ∈ D. – f est strictement convexe ◃ si et seulement si ∇2 f (x) est une matrice définie positive pour tout x ∈ D ◃ si et seulement si les valeurs propres de ∇2 f (x) sont strictement positives pour tout x ∈ D. ) ( 2x − y + 2 2 2 , Exemple. La fonction f (x, y) = x + y − xy + 2x + 2y est convexe : ∇f (x, y) = 2y − x + 2 ) ( 2 −1 2 qui a pour valeurs propres λ1 = 1, λ2 = 3 elle est donc strictement convexe ∇ f (x, y) = −1 2 sur R.

1.4

Applications quadratiques

Définition 1.3. Soit n un entier. On appelle application quadratique de Rn dans R toute application f de la forme 1 f (x) = ⟨Ax, x⟩ + ⟨b, x⟩ + c 2 n,n n où A ∈ R est une matrice, b ∈ R est un vecteur et ⟨., .⟩ désigne le produit scalaire de Rn : ∀x = (x1 , . . . , xn )t , ∀y = (y1 , . . . , yn )t ∑ ⟨x, y⟩ = xi yi i∈J1,nK

Proposition 1.3. Si f est une application quadratique f (x) =

1 ⟨Ax, x⟩ + ⟨b, x⟩ + c 2

alors ∇f (x) = Ax + b et ∇2 f (x) = A

10

Chapitre 1. Introduction et rappels

Exemple 1.1. (x, y) 7→ x2 + y 2 + xy − 2x + 3 est une application quadratique dont les éléments sont donnés par : ( ) 2x + y − 2 ∇f (x) = 2y + x ( ) 2 1 2 ∇ f (x) = 1 2 ( ) ( ) 2 1 −2 1 Donc f (x) = 2 ⟨Ax, x⟩ + ⟨b, x⟩ + c avec A = ,b = et c = 3. 1 2 0

11

Chapitre 2 Optimisation sans contrainte 2.1

Extrema libres

Définition. Soit (a, b) un point de D. On dit que 1. f admet un maximum local en (a, b) s’il existe un ε > 0 tel que f (a, b) ≥ f (x, y) pour tout (x, y) tel que |x − a| < ε et |y − b| < ε ; 2. f admet un minimum local en (a, b) s’il existe un ε > 0 tel que f (a, b) ≤ f (x, y) pour tout (x, y) tel que |x − a| < ε et |y − b| < ε ; 3. f admet un maximum global en (a, b) si f (a, b) ≥ f (x, y) pour tout (x, y) ∈ D ; 4. f admet un minimum global en (a, b) si f (a, b) ≤ f (x, y) pour tout (x, y) ∈ D. – Dessin en 2d, en 3d – extremum = max ou min Remarque. On notera que trouver un minimum pour la fonction f équivaut à trouver un maximum pour la fonction -f rappel extremum 1d Théorème 2.1. Soit I un intervalle ouvert de R, non vide, et f : I → R une fonction deux fois continuement dérivable en a ∈ I, telle que f ′ (a) = 0. Alors : – si f ′′ (a) < 0, f admet un maximum local en a – si f ′′ (a) > 0 alors f admet un minimum local en a – si f ′′ (a) = 0 on ne peut pas conclure. Pour le 3-ème cas, penser aux deux fonctions x 7→ x2 et x 7→ x3 en a = 0, dont l’une est minimum, l’autre ne l’est pas. Ce comportement de f au voisinage de a se lit directement dans son développement limité à l’ordre 2, (h positif ou négatif ) : f (a + h) − f (a) = h2 (f ′′ (a) + ε (h)) avec limh→0 ε (h) = 0. Donc si f ′′ (a) > 0, alors f (a + h) > f (a), autrement dit f est minimum en a. Pierre Puiseux

12

Chapitre 2. Optimisation sans contrainte

2.2

Dérivée directionnelle, profil

Définition. On suppose f continuement dérivable sur D. Soit A = (a, b) ∈ D et une direction d = (u, v) donnée. – On appelle dérivée directionnelle de f en (a, b) dans la direction (u, v) la quantité ∂f ∂f (a, b) u + (a, b) v ∂x ∂y – on appelle coupe ou profil de f le long de la droite A, d la fonction γ (t) = f (A + td) = f (a + tu, b + tv) Le profil est la représentation en dimension 1 de la fonction f dans le plan vertical défini par le point A (voir figure 2.2.1) et la direction d et la dérivée directionnelle de f en A dans la direction d est g ′ (0).

( ) 2 2 2 2 Exemple. Pour la fonction f : (x, y) → 7 3 (x − 1)2 e(−x −(y−1) ) − 10 x5 − x3 − y 5 e−x −y − 2 1 (−(x+1) −y 2 ) e , au point (a, b) = (0, 0) et dans la direction d = (0, 1), on obtient la coupe suivant 3 l’axe Oy : γ (t) = f (0, t) 2 1 2 2 = 3e−(t−1) + 10t5 e−t − e−1−t 3

10

7,5

x=0 5

x = 0.5

x=1 2,5

-2,8

-2,4

-2

-1,6

-1,2

-0,8

-0,4

0

0,4

0,8

1,2

1,6

2

2,4

2,8

-2,5

-5

-7,5

Fig. 2.2.2 : La fonction ( ) 2 2 2 2 2 2 f : (x, y) 7→ 3 (x − 1)2 e(−x −(y−1) ) − 10 x5 − x3 − y 5 e−x( −y )− 13 e(−(x+1) −y ) Les coupes dans la direction passant par (0, 0) , 21 , 0 , (1, 0) ( 1 ) Oy = (0,(1), ) c’est à dire γ (t) = f 2 , t , γ (t) = f 12 , t et γ (t) = f (1, t)

Proposition 2.1. Le gradient de f en (a, b) est la direction de plus grande pente de f au point (a, b).

2.2 Dérivée directionnelle, profil

13

(a,b) (u,v)

1800 m

g(t)

1700 m 1600 m 1500 m 1400 m 1300 m 1200 m 1100 m

0

1

2

t

1000 m

Fig. 2.2.1 : profil γ (t) et isovaleurs

Démonstration. pour une direction d = (u, v) donnée, de norme ∥d∥2 = 1, la dérivée en γ ′ (0) de la fonction γ : t 7→ f (a + tu, b + tv) mesure la pente de la fonction f en (a, b) et dans la direction d. Or

γ ′ (0) =

∂f ∂f (a, b) u + (a, b) v ∂x ∂y

est la dérivée directionnelle dans la direction d. C’est le produit scalaire de ∇f (a, b) par d, c’est à dire, en désignant par α l’angle entre ces deux vecteurs :: γ ′ (0) = ∥∇f (a, b)∥2 ∥d∥2 cos (α) Donc γ ′ (0) est maximal lorsque cos (α) = 1 c’est à dire pour α = 0 c’est à dire encore pour d dans la direction du gradient.

14

Chapitre 2. Optimisation sans contrainte

2.3

Condition nécessaire d’optimalité

Théorème. (condition nécessaire, ordre 1) si f est continuement dérivable sur D, si (a, b) ∈ D est un extremum, alors le gradient de f en (a, b) est nul : ∂f ∂f (a, b) = (a, b) = 0 ∂x ∂y La nullité du gradient en (a, b) est une condition nécessaire, mais insuffisante, pour que f admette un extremum en (a, b). Les points ou le gradient s’annule sont appelés points critiques. Exemple. f (x, y) = xy a pour point critique (0, 0) et f (0, 0) = 0 n’est ni un minimum ni un maximum car f prend des valeurs positives et négatives sur tout voisinage de (0, 0) puisque f (x, x) > 0 et f (x, −x) < 0.

2.4

Condition suffisante d’optimalité

Cherchons maintenant une condition suffisante d’optimalité.

Une condition suffisante pour que la fonction f soit maximum au point (a, b) est que la coupe γ soit maximum en 0 pour toutes les directions (u, v). Ce qui revient à dire que γ ′ (0) = 0 et γ ′′ (0) < 0 pour toutes les directions (u, v), ou encore : –

∂f ∂x

(a, b) u +

– γ ′′ (0) =

∂2f ∂x2

∂f ∂y

(a, b) v est nul pour toute direction (u, v) et 2

∂ f (a, b) u2 + 2uv ∂x∂y (a, b) +

∂2f ∂y 2

(a, b) v 2 est négatif pour toute direction (u, v)

La première condition est la nullité du gradient de f en (a, b). ( Définition. On appelle hessienne de f en (a, b) la matrice D2 f (a, b) ou Hf (a, b) ou même simplement f ′′ (a, b).

∂2f (a, b) ∂x2 ∂2f (a, b) ∂x∂y

)

∂2f (a, b) ∂x∂y ∂2f (a, b) ∂y 2

, parfois notée

Les valeurs propres d’une matrice A sont les racines du polynôme P (λ) = det (A − λI). On appelle vecteur propre associé à la valeur propre λ tout vecteur U non nul vérifiant AU = λU . ( ) u On remarque que γ ′′ (0) = u v D2 f (a, b) , la théorie des formes bilinéaires s’applique : pour v que γ ′′ (0) > 0 dans toutes les directions (u, v), il suffit que la hessienne soit une matrice définie positive, c’est à dire que ses valeurs propres soient strictement positives. (

On peut retenir le théorème :

)

2.4 Condition suffisante d’optimalité

15

Théorème 2.2. Soit D un domaine ouvert de R2 , f une fonction deux fois continûment différentiable sur D et (a, b) un point de D. Notons ∇ le gradient et H la matrice hessienne de f au point (a, b). 1. Si ∇ = 0 et si H a toutes ses valeurs propres strictement négatives, alors (a, b) est un maximum local pour f . 2. Si ∇ = 0 et si H a toutes ses valeurs propres strictement positives, alors (a, b) est un minimum local pour f . 3. Si ∇ = 0 et si H a certaines de ses valeurs propres strictement positives, toutes les autres strictement négatives, alors (a, b) est un point selle pour f . 4. Si ∇ = 0 et si certaines valeurs propres de H sont nulles, alors on ne peut pas conclure.

z

z

y

y

(a,b) x

(a,b)

D

x

D

z

y (a,b) x

D

Fig. 2.4.1 : Maximum, minimum et point col en dimension 2 Exemple. (dimension 2) f (x, y) = xy 2 +2x2 +y 2 . Au point (x, y), le gradient et la matrice hessienne sont : ( 2 ) ( ) y + 4x 4 2y ∇f (x, y) = ;H = 2xy + 2y 2y 2 (x + 1)

16

Chapitre 2. Optimisation sans contrainte – CN : les points critiques sont (−1, 2) , (−1, −2) et (0, 0). – CS : ( ) √ 4 4 ◃ (a, b) = (−1, 2) H = la hessienne a pour valeurs propres λ = 2 + 2 5 > 0, 4 0 √ µ = 2 − 2 5 < 0 c’est un point selle. ( ) √ 4 −4 ◃ (a, b) = (−1, −2) H = la hessienne a pour valeurs propres λ = 2+2 5 > 0, −4 0 √ µ = 2 − 2 5 < 0 c’est un point selle. ( ) 4 0 ◃ (a, b) = (0, 0) H = la hessienne a pour valeurs propres λ = 4, µ = 2 toutes deux 0 2 positives, c’est un minimum.

Lorsque la fonction f est à deux variables (x, y), cette analyse par valeurs propres se simplifie, et il n’est pas nécessaire de calculer les valeurs propres : 2

2

2

∂ f γ ′′ (0) = ∂∂xf2 (a, b) u2 + 2uv ∂x∂y (a, b) + ∂∂yf2 (a, b) v 2 est un polynôme du second degré en u, la condi2 tion γ ′′ (0) < 0 (suffisante pour avoir un maximum) est de tout ((la forme αu) + 2βu + γ < 0 pour ) 2 2 2 ∂2f (u, v). Le discriminant réduit de ce polynôme est ∆′ = v 2 (a, b) − ∂∂xf2 (a, b) ∂∂yf2 (a, b) = ∂x∂y

−v 2 det H (x, y). On en déduit :

Théorème 2.3. (spécifique à la dimension 2) – si det H (a, b) > 0 alors γ ′′ (0) est de signe constant : le signe de ◃ si

∂2f ∂x2

(a, b) < 0 , alors f admet un maximum en (a, b) ;

◃ si

∂2f

(a, b) > 0 , alors f admet un minimum en (a, b) ;

∂x2

∂2f ∂x2

(a, b) ;

– si det H (a, b) < 0 alors γ ′′ (0) change de signe (a, b) est un point selle ; – si det H (a, b) = 0 on ne peut pas conclure.

2.5

Algorithmes de gradient

Pour calculer le minimum d’une fonction f : Rn → R dont on connaît le gradient ∇f : Rn → Rn On rappelle que le gradient de f en (a, b) est un vecteur de Rn qui indique la plus grande pente en (a, b). L’idée pour minimiser une fonction (si le problème est de trouver un maximum pour +f , on minimise −f ) , est de partir d’un point donné, x(0) et de suivre la plus grande pente (en descendant) pour aboutir à un point x(1) , puis de recommencer jusqu’à aboutir à un point critique (où le gradient est nul).

2.5 Algorithmes de gradient

2.5.1

17

Gradient à pas fixe

Pour deux vecteurs u, v ∈ Rn , on définit le produit scalaire : ∑ u.v = uk vk 1≤k≤n

et la norme euclidienne de u par ∥u∥2 =

√ u.u

L’algorithme du gradient consiste à partir d’une approximation initiale x(0) = (x0 , y0 ), à se déplacer dans la direction de la plus grande pente, donc du gradient, d’un pas t. Si t > 0, le déplacement se fait dans la direction f croissante, si t < 0, on se déplace dans la direction f décroissante. ( (k) ) On stoppe les itérations lorsque f x ou bien x(k) est stationnaire. Ici, on a choisi la stationnarité ( (k) ) de f x . Algorithme 2.1 Algorithme du gradient à pas fixe pour minimiser une fonction f x(0) , ε, f, ∇f, t sont donnés, k = 0 répéter : ( ) – x(k+1) = x(k) − t∇f x(k) – k =k+1 ( ) ( ) jusqu’à f x(k) − f x(k−1) < ε Exemple. Le programme Python qui suit implémente l’algorithme du gradient à pas fixe, pour la fonction (x, y) 7→ x2 + y 2 − xy. Le test d’arrêt des itérations se fait sur la norme du gradient : c’est à

( ) 2 dire sur ∇f x(k) 2 < ε2 , ce qui équivaut à x(k+1) − x(k) 2 < ε. Afin d’interdire une boucle infini, (en cas de non convergence), on limite également le nombre d’itérations avec le paramètre itmax # !/usr/local/bin/python2.7 # -*- coding : utf-8 -*''' Optimisation : gradient à pas fixe''' def f(x,y) : return x*x + y*y - x*y def gradf(x,y) : return [2*x - y, 2*y - x] def gradient(X0=[1.0,1.0], f=f, gradf=gradf, eps=1.e-5, itmax=100, t=1.0) : '''Gradient à pas fixe''' X = [X0] x,y = X0 F = [f(x,y)] it = 1 while 1 : dx, dy = gradf(x, y)

18

Chapitre 2. Optimisation sans contrainte dx, dy = t*dx, t*dy if (dx*dx+dy*dy)< eps*eps or it >= itmax : break else : it += 1 x -= dx y -= dy F.append(f(x,y)) X.append([x,y]) return (it, X, F) if __name__ == '__main__' : import numpy as np import matplotlib.pyplot as plt it, X, F = gradient(X0=[1.0,0.0], f=f, gradf=gradf, eps=1.e-6, itmax=50, t=0.667) print it, len(F) print F plt.plot(range(it), F) plt.show()

1.0 0.8 0.6 0.4 0.2 0.0 0

5

10

15

20

25

Fig. 2.5.1 : Valeur de la fonction objectif en fonction du numéro d’itération, algorithme du gradient

2.5.2

Gradient à pas optimal

Ici, on demande à l’algorithme de déplacer x(k) , toujours dans la direction du gradient, mais cette fois jusqu’au minimum de f , c’est à dire de minimiser la coupe )) ( ( t ∈ R 7→ γk (t) = f x(k) + t.∇f x(k) En général, on ne dispose pas d’une expression analytique de la coupe γk . La minimisation de cette fonction (appelée recherche linéaire) peut être assez difficile à mener. Il existe des algorithmes (règles de Wolfe, d’Armijo, ...) qui approchent ce minimum.

2.5 Algorithmes de gradient

Algorithme 2.2 Algorithme du gradient à pas optimal x(0) , ε, f, ∇f sont donnés k=0 répéter : ( ) – calcul de ∇f x(k) ( ( )) – trouver tk qui minimise la coupe γk : t ∈ R 7→ f x(k) + t∇f x(k) ( ) – x(k+1) = x(k) − tk ∇f x(k) – k =k+1 ( ) ( ) jusqu’à f x(k) − f x(k−1) < ε

19

20

Chapitre 2. Optimisation sans contrainte

21

Chapitre 3 Contraintes égalité, multiplicateurs de Lagrange 3.1

Définitions et notations

En toute généralité, nous posons le problème d’optimisation sous contraintes égalité ainsi : Soit D un ouvert non vide de Rn , et soit f : D → R la fonction coût ou fonction objectif, continuement différentiable. Les contraintes g1 , . . . , gp sont p applications continuement différentiables et C = {x ∈ D, gi (x) = 0, ∀i ∈ J1, pK} Le problème de minimisation à résoudre est : { Minf (x) (P) x∈C Définition 3.1. On appelle lagrangien du problème (P) la fonction L (x, λ) = L (x1 , x2 , . . . , xn , λ1 , . . . , λm ) ∑ = f (x) + λi gi (x) i∈J1,pK

Notation. On note (observez l’indice x) ∇x L (x, λ) = ∇f (x) +

∑

λi ∇gi (x)

i∈J1,pK

et ∇2x L (x, λ) = ∇2 f (x) +

∑ i∈J1,pK

On voit facilement Pierre Puiseux

λi ∇2 gi (x)

22

Chapitre 3. Contraintes égalité, multiplicateurs de Lagrange – que ∇x L (x, λ) est le vecteur constitué des n premières composantes de ∇L (x, λ) et – que ∇2x L (x, λ) est la sous matrice constituée des n première lignes et n premières colonnes de ∇2 L (x, λ)  2  ∂2L ∂ L ∂2L . . . 2 ∂x1 ∂x2 ∂x1 ∂xn  ∂x2 1  .. .. ..  ∂L  . . .  ∂x1 ∂x2  2 ∇x L (x, λ) =  .  (x, λ) 2 . . ∂ L  ..  .. ..  ∂xn−1 ∂xn  2 2 2 ∂ L ∂ L ∂ L ... ∂x1 ∂xn ∂xn−1 ∂xn ∂x2 n

3.2

Quelques exemples

Exemple 3.1. Minimiser la fonction f : x 7→ x2 sous la contrainte x = 1 à pour unique solution évidente x = 1. Mais x = 1 n’est pas point critique de f puisque f ′ (1) = 2 ̸= 0. Il est donc clair que la méthode d’optimisation sans contrainte du chapitre précédent ne peut pas s’appliquer telle qu’elle au problème contraint.

Exemple 3.2. Minimiser ou maximiser f (x, y) = x3 y − x2 + 3x + y 2 + 2y sous la contrainte g (x, y) = 2x + y − 1 = 0 La contrainte fournit y = 1 − 2x que l’on reporte dans f (x, y) qui devient une fonction à une seule variable h (x) = f (x, 1 − 2x) = −2x4 + x3 + 3x2 − 5x + 3 = −(x − 1)(2x3 + x2 − 2x + 3)

10

7,5

5

2,5

-2

-1,5

-1

-0,5

0

0,5

1

1,5

2

-2,5

-5

Fig. 3.2.1 : h (x) = −2x4 + x3 + 3x2 − 5x + 3 Remarque. g (x, y) = 0 est l’équation de la droite passant par A = (0, 1) et dirigée par le vecteur d = (1, −2). Minimiser la fonction f sous la contrainte g (x, y) = 0 équivaut donc à minimiser la coupe de f sur cette droite. Cette coupe est précisément la fonction γ : t 7→ f (A + td). on trouve facilement que γ est maximum en x = −1, avec γ (−1) = 8.

3.3 Deux variables et une seule contrainte égalité

23

Les contraintes ne sont pas nécessairement linéaires comme g (x, y) dans l’exemple précédent. Exemple 3.3. (contrainte non linéaire) : parmi les parallélépipèdes de surface S0 fixée, lequel a le volume maximal ? x, y désignant les longueurs des cotés du parallélépipède, la surface est S (x, y, z) = 2 (xy + yz + zx) et son volume est V (x, y, z) = xyz. Le problème consiste donc à trouver le maximum de V (x, y, z) sous la contrainte 2 (xy + yz + zx) = S0 . On peut calculer z : z=

− xy x+y

S0 2

et maximiser VS0 (x, y) = xy

On trouve alors la maximum par la technique usuelle : √ x=y=

− xy x+y

S0 2

S0 6

puis z = x = y, ce qui montre que le cube est la solution cherchée. Remarque. dans le cas d’un problème d’optimisation à n variables le nombre de contraintes « indépendantes » (dans un sens à préciser) doit être inférieur à n car sinon, pour p = n contraintes, les contraintes forment un système de n équations à n inconnues. Dans les bons cas, il n’y a qu’une seule solution, indépendante de la fonction à optimiser. Pour p > n il peut n’y avoir aucune solution. Exemple 3.4. Le problème suivant : trouver le minimum de la fonction f (x, y) = xy sous les contraintes x + y = 1 et x − y = 1 a pour unique solution (x, y) = (1, 0), qui est le seul point de R2 satisfaisant les deux contraintes. Cette solution est obtenue sans tenir aucun compte de la fonction à optimiser. Les contraintes dans ce cas sont deux équations de droites, la solution est l’unique intersection de ces deux droites, sauf cas particulier (droites parallèles ou confondues).

3.3

Deux variables et une seule contrainte égalité

On se place en dimension n = 2 (f est une fonction a deux variables) avec une seule contrainte égalité g. L’ensemble des contraintes est C = {(x, y) ∈ D, g (x, y) = 0} Le lagrangien du problème est donc L (x, y, λ) = f (x, y) + λg (x, y) Le théorème suivant donne une condition nécessaire d’existence d’un minimum contraint : Théorème 3.1. (condition nécessaire, ordre 1) Soit D un domaine ouvert de R2 , f et g deux applications continuement dérivables de D dans R. On note C = {(x, y) ∈ D, g (x, y) = 0}

24

Chapitre 3. Contraintes égalité, multiplicateurs de Lagrange

Si f restreinte à C présente un extrémum en (a, b) ∈ C et si la contrainte est qualifiée : ∇g (a, b) ̸= 0R2 alors le lagrangien admet un point critique (a, b, λ∗ ) et λ∗ est appelé multiplicateur de Lagrange : ∇L (a, b, λ∗ ) = 0R3 Remarque. 1. Si (a, b, λ∗ ) et un point critique du lagrangien, alors (a, b) ∈ A car

∂L ∂λ

(a, b, λ∗ ) = g (a, b) = 0.

2. Si la contrainte n’est pas qualifiée en (a, b), il se peut que f restreinte à A présente un extrémum en (a, b) ∈ A mais que le multiplicateur de Lagrange λ∗ n’existe pas. 3. Si la contrainte est le cercle unité x2 + y 2 = 1 on a une interprétation simple du multiplicateur de Lagrange : minimiser f (x, y) sous la contrainte x2 + y 2 = 1 revient à minimiser φ (θ) = f (cos (θ) , sin (θ)) pour θ ∈ R, c’est un problème en 1 dimension, sans contrainte. La condition nécessaire d’optimalité s’écrit : φ′ (θ) = 0 soit − sin (θ)

∂f ∂f (cos (θ) , sin (θ)) + cos (θ) (cos (θ) , sin (θ)) ∂x ∂y

ce qui peut s’interpréter ainsi : les deux vecteurs ∇f (cos (θ) , sin (θ)) et u = (cos (θ) , sin (θ))t sont colinéaires. Or u n’est autre que ∇g (cos (θ) , sin (θ)) avec g (x, y) = x2 + y 2 − 1 donc il existe un réel λ∗ tel que ∇f (cos (θ) , sin (θ)) = λ∗ ∇g (cos (θ) , sin (θ)) Définition 3.2. (Hessienne bordée) La matrice hessienne du lagrangien est aussi appelée la matrice hessienne bordée de f  ∇2 L (x, y, λ) =

∂2L (x, y, λ) ∂x2  ∂2L  ∂x∂y (x, y, λ) ∂g (x, y) ∂x

∂2L (x, y, λ) ∂y∂x ∂2L (x, y, λ) ∂y 2 ∂g (x, y) ∂y

∂g ∂x ∂g ∂y

 (x, y)  (x, y) 0

Théorème 3.2. (Condition suffisante, ordre 2) Soit D un domaine ouvert de R2 , f et g deux applications deux fois continuement dérivables de D dans R. Soit (a, b, λ∗ ) un point critique du lagrangien L (x, y, λ) = f (x, y) + λg (x, y) alors – si le déterminant de la hessienne bordée ∇2 L (a, b, λ∗ ) est strictement négatif, (a, b) est un minimum local du problème contraint ; – si le déterminant de la hessienne bordée ∇2 L (a, b, λ∗ ) est strictement positif, (a, b) est un maximum local du problème contraint.

ATTENTION : Le théorème précédent est valide uniquement pour deux variables (x, y)

3.3 Deux variables et une seule contrainte égalité

25

Exemple 3.5. Optimimiser f (x, y) = x3 y − x2 + 3x + y 2 + 2y sous la contrainte g (x, y) = 2x + y − 1 = 0 Le lagrangien du problème est L (x, y, λ) = x3 y − x2 + 3x + y 2 + 2y + λ (2x + y − 1) 1. Gradient et hessienne bordée :  2  3x y − 2x + 3 + 2λ ∇L (x, y, λ) =  x3 + 2y + 2 + λ  2x + y − 1 et

  6xy − 2 3x2 2 2 1 ∇2 L (x, y, λ) =  3x2 2 1 0

  −20 3 2 2. un seul point critique de L : (−1, 3, 7) ∇2 L (−1, 3, 7) =  3 2 1 et 2 1 0 ( ) 2 ̸= 0R2 3. La contrainte est qualifiée au point (−1, 3) car ∇g (−1, 3) = 1 4. det (∇2 L (−1, 3, 7)) = 24 > 0 donc f présente un maximum contraint en (−1, 3) : f (−1, 3) = 8 5. figures

Fig. 3.3.1 : f (x, y) = x3 y − x2 + 3x + y 2 + 2y et la contrainte 2x + y − 1 = 0

26

Chapitre 3. Contraintes égalité, multiplicateurs de Lagrange

3.4

Cas général

La fonction à optimiser est f : D ⊂ Rn → R où D est un ouvert de Rn . Les p contraintes égalité sont gi (x) = 0, 1 ≤ i ≤ p où gi sont p fonctions de D dans R. L’ensemble contraint est donc C = {x ∈ D, ∀i, 1 ≤ i ≤ p, gi (x) = 0} et le problème de minimisation est :

{ Minf (x) (P) x∈C

Définition 3.3. On dit que les contraintes sont qualifiées au point x∗ si et seulement si la famille {∇gi (x∗ ) , 1 ≤ i ≤ p} est une famille libre. On commence par des conditions nécessaires : Théorème 3.3. (condition nécessaire, ordre 1) On suppose que f et gi , 1 ≤ i ≤ p sont continuement dérivables sur D. – Si f restreinte à C présente un extremum en x∗ ∈ C et – si les contraintes sont qualifiées ( ) alors le lagrangien admet un point critique (x∗ , λ∗ ) avec λ∗ = λ∗1 , λ∗2 , . . . , λ∗p : ∇L (x∗ , λ∗ ) = 0R3 les λ∗i sont appelés multiplicateurs de Lagrange. Remarque. 1. Si (x∗ , λ∗ ) et un point critique du lagrangien, alors x∗ ∈ C car

∂L ∂λj

(x∗ , λ∗ ) = gj (x∗ ) = 0.

2. Si la contrainte n’est pas qualifiée en x∗ , il se peut que f restreinte à C présente un extremum en x∗ ∈ C mais que les multiplicateurs de Lagrange λ∗ n’existent pas. La version « faible » pour les conditions suffisantes : Théorème 3.4. (Condition suffisante d’ordre 2) On suppose que f et gj , 1 ≤ j ≤ p sont deux fois continuement dérivables sur D et que – (x∗ , λ∗ ) est un point critique du lagrangien, – les contraintes en x∗ sont qualifiées, – la matrice ∇2x L (x∗ , λ∗ ) est définie positive,

3.4 Cas général

27

alors x∗ est un minimum du problème contraint. ( ) −20 3 Exemple 3.6. Dans l’exemple (3.5), (−1, 3, 7) = a une valeur propre négative, 3 2 l’autre positive. Ce théorème ne permet pas de conclure. ∇2x L

Dans l’exemple suivant, le théorème permet de conclure : Exemple 3.7. Minimiser f (x, y, z) = x + y + z sous la contrainte g (x, y, z) = x2 + y 2 + z 2 − r2 1. Le Lagrangien est ( ) L (x, y, z, λ) = x + y + z + λ x2 + y 2 + z 2 − r2 le gradient :

 1 + 2λx   1 + 2λy  ∇L (x, y, z, λ) =    1 + 2λz 2 2 2 2 x +y +z −r

la hessienne :

  2λ 0 0 2x  0 2λ 0 2y   ∇2 L (x, y, z, λ) =   0 0 2λ 2z  2x 2y 2z 0



et son déterminant : ( ) ( ) det ∇2 L (x, y, z, λ) = −16λ2 x2 + y 2 + z 2 < 0 1 2. Points critiques : x = y = z = − 2λ et la contrainte donne 3x2 = r2 donc les points critiques sont : (√ √ √ √ ) 3 3 3 3 A = (x∗ , λ∗ ) = r, r, r, − et B = −A. 3 3 3 2r

Vérifions que la contrainte est qualifiée pour chacun de ces points :   2x  ∇g (x, y, z) = 2y  2z donc ∇g (x∗ ) ̸= 0 et ∇g (−x∗ ) ̸= 0 ces deux points critiques sont donc candidats à être des extrema contraints. 3. De l’égalité ∇2x L (x, y, z, λ) = 2λId3 on déduit, en utilisant le théorème précédent : – au point A on a ∇2x L (A) a donc pour valeurs propres λ1 = λ2 = λ3 = − donc un maximum.

√

3 r

< 0 on a

28

Chapitre 3. Contraintes égalité, multiplicateurs de Lagrange – au point B = −A les valeurs propres ∇2x L (B) de sont λ1 = λ2 = λ3 = un minimum.

√

3 r

> 0 on a donc

Voici une version plus raffinée de ce théorème : Théorème 3.5. (Condition suffisante d’ordre 2) On suppose que f et g1 , g2, . . . , gp sont deux fois continuement dérivables sur D et que 1. (x∗ , λ∗ ) est un point critique du lagrangien, et 2. les contraintes en x∗ sont qualifiées, 3. pour tout h ∈ Rn tel que ∀i ∈ J1, pK, ∇gi (x∗ ) .h = 0 ht .∇2x L (x∗ , λ∗ ) .h > 0 alors x∗ est un minimum du problème contraint. Si on remplace la troisième condition par ht .∇2x L (x∗ , λ∗ ) .h < 0 alors x∗ est un maximum Remarque. La différence avec le théorème précédent tient à la condition 3 : on demande ici que la matrice ∇2x L (x∗ , λ∗ ) soit définie positive seulement pour les vecteurs h qui sont orthogonaux à tous les gradients des contraintes. Proposition 3.1. (règle pratique) La troisième condition du théorème précédent est équivalente à : toutes les racines du polynôme ) ( A − λIn D p (λ) = det Dt 0 sont positives, où In la matrice identité de Rn,n , A = ∇2x L (x∗ , λ∗ ) ∈ Rn,n et

D = (∇gj (x∗ ))1≤j≤p ∈ Rn,p

(D est la matrice dont les p colonnes sont les gradients des contraintes). Exemple 3.8. Dans l’exemple (3.5), 

 −20 3 −2 2 −1 ∇2 L (−1, 3, 7) =  3 −2 −1 0 et

−20 − λ 3 −2 3 2 − λ −1 = 24 + 5λ p (λ) = −2 −1 0

a pour racine λ = − 24 < 0, on a donc un maximum en f (−1, 3) = 8. 5

3.5 En résumé

3.5

29

En résumé

Pour une ou plusieurs contraintes égalité, on utilisera la méthodologie suivante :

Contraintes égalités

1. Déterminer les points critiques du lagrangien, et 2. pour chaque point critique (x∗ , λ∗ ) : (a) vérifier que les contraintes en x∗ sont qualifiées, (b) trouver les racines du polynôme ( ) A − tIn D p (t) = det Dt 0 i. si les racines sont toutes strictement positives, on a un minimum en f (x∗ ) ; ii. si les racines sont toutes strictement négatives, on a un maximum en f (x∗ ) ; iii. sinon on ne peut pas conclure.

30

Chapitre 3. Contraintes égalité, multiplicateurs de Lagrange

31

Chapitre 4 Contrainte inégalité 4.1

Définition et exemples

En toute généralité, nous posons le problème d’optimisation sous contraintes (égalité et inégalité) ainsi : Soit D un ouvert non vide de Rn , et soit f : D → R la fonction coût ou fonction objectif, continuement différentiable. Les contraintes g1 , . . . , gp et h1 , . . . , hq sont p + q applications continuement différentiables et C = { x ∈ D, gi (x) = 0, ∀i ∈ J1, pK et hj (x) ≤ 0, ∀j ∈ J1, qK } | {z } | {z } contraintes égalité contraintes inégalité Le problème de minimisation à résoudre est : { Minf (x) (P) x∈C Définition 4.1. Soit x ∈ D. – On dit que la contrainte inégalité hj est active ou saturée en x si et seulement si hj (x) = 0 – On dit que les contraintes g1 , . . . , gp et h1 , . . . , hq sont qualifiées en x si et seulement si ∪ {∇g1 (x) , . . . , ∇gp (x)} {∇hj (x) |hj saturée} (QC)x : est une famille libre – On appelle Lagrangien du problème (P) la fonction : ∑ ∑ L (x, λ, µ) = f (x) + λi gi (x) + µj hj (x) i∈J1,pK

Pierre Puiseux

j∈J1,qK

32

Chapitre 4. Contrainte inégalité – On note ∇x L (x, λ, µ) = ∇f (x) +

∑

λi ∇gi (x) +

i∈J1,pK

et

∑

∇2x L (x, λ, µ) = ∇2 f (x) +

∑

µj ∇hj (x)

j∈J1,qK

λi ∇2 gi (x) +

i∈J1,pK

∑

µj ∇2 hj (x)

j∈J1,qK

Remarque. On voit facilement – que ∇x L (x, λ, µ) est le vecteur constitué des n premières composantes de ∇L (x, λ, µ) et – que ∇2x L (x, λ, µ) est la sous matrice constituée des n première lignes et n premières colonnes de ∇2 L (x, λ, µ) 

∂2L ∂x1 ∂x2

∂2L ∂x21

 2  ∂L  ∇2x L (x, λ, µ) =  ∂x1.∂x2  .. 

∂2L ∂x1 ∂xn

..

.

..

.

...

... .. . .. . ∂2L ∂xn−1 ∂xn

∂2L ∂x1 ∂xn



    (x, λ, µ) 2 ∂ L  ∂xn−1 ∂xn  .. .

∂2L ∂x2n

Exemple 4.1. On considère un bien B, de quantité 100 à répartir entre 5 consommateurs. Chaque consommateur reçoit une quantité xi du bien B. Il doit en recevoir une quantité minimale qi et en espère la quantité pi avec i 1 2 3 4 5

qi 10 15 20 15 25

pi 20 25 40 40 40

Formalisons ce problème sous forme d’un minimum à calculer. La fonction coût : f (x) =

∑

(xi − pi )2

1≤i≤5

les contraintes :

∑

xi = 100

1≤i≤5

et x i ≥ qi , 1 ≤ i ≤ 5

4.2 Conditions nécessaires (KKT)

4.2

33

Conditions nécessaires (KKT)

Théorème 4.1. (conditions nécessaires, Karush-Kuhn-Tucker.) Si x∗ ∈ C est un minimum local de f sur C et si (QC)x∗ est vérifiée, alors il existe λ∗ = (λ1 , . . . , λp ) et µ∗ = (µ1 , . . . , µq ) tels que : 1. (x∗ , λ∗ , µ∗ ) vérifie :

∇x L (x∗ , λ∗ , µ∗ ) = 0

2. et les multiplicateurs µj , j ∈ J1, qK vérifient : { µj > 0 si la contrainte est saturée en x∗ ∀j ∈ J1, qK, µj = 0 sinon ou de manière équivalente :

{ µj ≥ 0 ∀j ∈ J1, qK, µj hj (x∗ ) = 0

et

Remarque. 1. Pour un problème de maximisation, il suffit de remplacer ∀j ∈ J1, qK, µj ≥ 0 par ∀j ∈ J1, qK, µj ≤ 0. 2. Si la contrainte hj n’est pas saturée, alors µj = 0 et la contrainte n’intervient plus dans le lagrangien, c’est comme si elle était absente du problème initial.

4.3

Conditions suffisantes (KKT)

Définition 4.2. On dit que (P) est un problème de programmation convexe si : – D est un ouvert convexe (c’est le cas notamment si D = Rn ) ; – f est convexe ; – les contraintes égalité gi , i ∈ J1, pK sont des applications affines ; – les contraintes inégalité hj , j ∈ J1, qK sont des applications convexes. Théorème 4.2. (conditions suffisantes, Karush-Kuhn-Tucker.) Si (P) est un problème de programmation convexe, et si (QC)x∗ est vérifiée, alors les deux conditions KKT en x∗ ∈ C sont suffisantes pour que x∗ soit un minimum global de f . Exemple 4.2. La fonction objectif : f (x, y, z) = x2 + y 2 + z 2 les contraintes :

{ g (x, y, z) = x + y + z − 3 = 0 h (x, y, z) = 2x − y + z − 5 ≤ 0

Consiste à déterminer dans R3 la distance à l’origine du demi-plan défini par les contraintes.

34

Chapitre 4. Contrainte inégalité

Les conditions KKT s’écrivent : ∇f (x) + λ∇g (x) + µ∇h (x) = 0 µ (2x − y + z − 5) = 0 µ≥0

(ii) (iii) soit

(i)

  2x + λ + 2µ = 0 2y + λ − µ = 0   2z + λ + µ = 0

(ii) µ (2x − y + z − 5) = 0 (iii) µ≥0 Supposons µ ̸= 0, alors (iν) 2x − y + z − 5 = 0 et

  x = (−λ − 2µ)/2 (i) ⇒ y = (−λ + µ)/2   z = (−λ − µ)/2

La contrainte égalité implique 3λ + 2µ = −6 et avec (iν) : λ + 3µ = −5 d’où µ = − 79 < 0 ce qui est incompatible avec (iii). Donc µ = 0 puis λ = −2 et x = y = z = 1. Il s’agit d’un minimum global de f sur C car C est un convexe, f est convexe, ainsi que les contraintes.

Exemple 4.3. On reprend l’exemple donné en introduction et on le simplifie : La fonction objectif est : ∑ f (x) = (xi − pi )2 i∈J1,5K

les contraintes : g (x) =

∑

xi − 100 = 0

i∈J1,5K

hi (x) = qi − xi ≤ 0, i ∈ J1, 5K Le lagrangien L (x, λ, µ) = f (x) + λg (x) +

∑

µi hi (x)

i∈J1,5K

La première condition KKT s’écrit : ∇f (x) + λ∇g (x) +

∑ i∈J1,5K

µi ∇hi (x) = 0

4.3 Conditions suffisantes (KKT)

35

et avec la seconde condition KKT :   2 (xi − pi ) + λ − µi = 0 (i) µi (xi − qi ) = 0 i ∈ J1, nK   µi ≥ 0 ∑ xi = 100 TODO

Exercices Sans contrainte Exercice 4.1. Pour chacune des fonctions de R2 dans R suivantes : f1 (x, y) = x3 + 3xy 2 − 15x − 12y f2 (x, y) = x2 + y 2 − xy f3 (x, y) = x2 − y 2 − xy f4 (x, y) = x3 + y 3 − x2 y 2 f5 (x, y) = 4x2 + 4y 2 − (x + y)4 1. Calculer le gradient de f . 2. Déterminer les points critiques de f . 3. Calculer la matrice hessienne de f . 4. Pour chacun des points critiques de f , donner les conclusions tirées de l’examen de la matrice hessienne. 5. Pour chacun des points critiques de f , dire s’il s’agit ou non d’un extremum global de f . Exercice 4.2. Pour chacune des fonctions de R2 dans R suivantes : f1 (x, y, z) = x2 + 2y 2 + 3z 2 f2 (x, y, z) = x2 + 2y 2 − 3z 2 f3 (x, y, z) = x4 + y 2 + z 2 −4x−2y−2z + 4 f4 (x, y, z) = x4 −2x2 y + 2y 2 + 2z 2 + 2yz−2y−2z + 2 f5 (x, y, z) = 3(x2 + y 2 + z 2 )−2(x + y + z)4 1. Calculer le gradient de f et la matrice hessienne de f . 2. Déterminer les points critiques de f . 3. Pour chacun des points critiques de f , donner les conclusions tirées de l’examen de la matrice hessienne.

36

Chapitre 4. Contrainte inégalité

Contraintes égalité Exercice 4.3. Optimiser f (x, y) = x2 y sous la contrainte 4x + y = 30 en utilisant deux méthodes : 1. en se ramenant à un problème à une variable 2. en utilisant les techniques de lagrangien. Exercice 4.4. Chercher les extrema de la fonction f (x, y) = x2 y sous la contrainte 12x+2y−180 = 0 Exercice 4.5. Chercher les extrema de la fonction f (x, y) = x (1 + y) sous la contrainte 5x + 10y − 5=0 Exercice 4.6. Chercher les extrema de la fonction f (x, y, z) = x + y + z sous la contrainte x2 + y 2 + z2 = 1 Exercice 4.7. Chercher les extrema de la fonction f (x, y) = x + y sous la contrainte x2 + y 2 = 1 Exercice 4.8. Optimiser f (x, y) = xy 1. sous la contrainte x + y = 6 2. sous la contrainte x2 + y 2 = 2 Exercice 4.9. On veut maximiser la fonction f (x, y, z) = x2 yz sous la contrainte 2x + 4y + z − 64 = 0 Montrer que ce problème se ramène à un problème d’optimisation sans contrainte et résoudre ce problème. Exercice 4.10. On note C le cercle unité de R2 : { } C = (x, y) ∈ R2 , x2 + y 2 = 1 On considère les fonctions f (x, y) = x + y f (x, y) = x2 + y 2 − xy

f (x, y) = x + y − xy f (x, y) = x2 + y 2 − x2 y 2

f (x, y) = x2 − y

1. Utiliser les conditions nécessaires d’ordre 1 pour déterminer les candidats à être des extrema pour la restriction de f à C. 2. Pour chacun de ces points, dire s’il s’agit ou non d’un extremum pour la restriction de f à C Exercice 4.11. Optimiser f (x, y, z) = x2 + y 2 + z 2

4.3 Conditions suffisantes (KKT)

37

sous la contrainte x + 2y = 2 et x2 + 2y 2 + 2z 2 = 2 Exercice 4.12. Optimiser f (x, y, z) = xyz difficile sous la contrainte x+y+z−1 = 0 x + y2 + z2 − 1 = 0 2

( ) Indication : il y a 6 points critiques pour le lagrangien. On pourra vérifier que les points 23 , 23 , − 13 , − 29 , 13 et (1, 0, 0, 0, 0) en font partie, et on en déduira les autres avec des arguments de symétrie.

Contraintes inégalités { 2 Exercice 4.13. (Problème de Kepler.) Inscrire dans l’ellipsoïde E = (x, y, z) ∈ R3 , xa2 + le parallèlépipède de volume maximal, sont les cotés sont parallèles aux axes.

y2 b2

+

z2 c2

} =1

Exercice 4.14. Soit f (x, y) = 2x − y 1. Justifier l’existence d’un extrema sur le domaine { } C = (x, y) ∈ R2 , x2 + y 2 = 1 2. Justifier l’existence d’un extrema sur le domaine { } C1 = (x, y) ∈ R2 , x2 + y 2 ≤ 1 Exercice 4.15. Maximiser x sous la contrainte y ≥ x2 et x + y ≤ 1. Exercice 4.16. Minimiser x sous la contrainte y ≥ 0 et y ≤ (1 + x)3 . Exercice 4.17. Optimiser f (x, y) = ex

2 +y 2

+ y 2 − 1 pour (x, y) ∈ C = {(x, y) ∈ R2 ; x2 + y 2 ≤ 9}

Exercice 4.18. Minimiser f (x, y) = x2 pour (x, y) ∈ C = {(x, y) ∈ R2 ; x2 + y 2 ≤ 2 et x = y} Exercice 4.19. Résoudre :

 ( 2 2)  max − (x − 4) − (y − 4) (P) x + y ≤ 4   x + 3y ≤ 9

Exercice 4.20. Les fonctions suivantes sont elles convexes ? 1. (x, y) 7→ x2 + y 2 + 4xy 2. (x, y) 7→ 2x2 − 2y 2 − 6z 2 + 3xy − 4xz + 7yz 3. (x, y) 7→ ex + ey 4. (x, y) 7→ ex ey

38

INDEX

Index C contraintes qualifiées, 26 courbes de niveau, 5 F Formule de Taylor, 6 I isovaleurs, 5 L Lagrangien, 31 lagrangien, 21 M multiplicateurs de Lagrange, 21 P programmation convexe, 33

Pierre Puiseux

39

BIBLIOGRAPHIE

Bibliographie [1]

Pierre Puiseux