V.
PROGRAMMATION NON LINEAIRE
–Problèmes avec contraintes d’égalité -
Multiplicateurs de Lagrange
–Problèmes avec contraintes d’inégalité –
Conditions de Karush-Kuhn-Tucker
–Méthode des pénalités
–Programmation quadratique séquentielle
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (1)
Problèmes avec contraintes d’égalité
V.111 Points réguliers
Soit la matrice Jacobienne J(x) de dimension
Un point x* tel que h(x*)=0 est appelé un point régulier des contraintes
si
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (2)
V.111 Points réguliers (suite)
Les contraintes d’égalité h(x)=0 décrivent une surface dans
Si les points de S sont réguliers alors S est de dimension (n-m)
V.112 Courbe sur une surface
Une courbe C sur la surface S est un ensemble de points
continûment paramétré par
La courbe C passe par un point x* s’il existe t* tel que x(t*)=x*
Le vecteur est la tangente à la courbe C au point x*
Propriété
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (3)
V.113 Espace tangent
L’espace tangent T(x*) en un point x* sur la surface S est définit
comme l’ensemble
Si x* est régulier alors T(x*) est de dimension (n-m)
Soit une courbe C sur la surface S passant par x* alors la tangente
à la courbe
V.114 Espace normal
L’espace normal N(x*) en un point x* sur la surface S est définit
comme l’ensemble
Si x* est régulier alors N(x*) est de dimension m
Propriété
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (4)
V.12 Condition nécessaire du premier ordre
Soit f(x) minimum en x* sous la contrainte h(x) = 0
Si x* est un point régulier, alors
Condition nécessaire mais pas suffisante
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (5)
Démonstration
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (6)
Exemple
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (7)
Exemple (suite)
f(x)=1
•
1
• •
-1
•
h(x)=0
f(x)=1/2
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (8)
Maximum Condition vérifiée
• en x* et pas en y*
•
h(x)=0
Minimum
•
•
h(x)=0
Pas un extremum
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (9)
V.13 Conditions nécessaires et suffisantes
Fonction de Lagrange
le Hessien de l(x,λ)
Hessien de f(x) Hessien de
Condition nécessaire du second ordre
Soit f(x) minimum en x* sous la contrainte h(x) = 0
Si x* est un point régulier, alors
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (10)
Condition suffisante
si ∃x * ∃λ∗ 1° ∇f (x ∗ ) + ∇h T (x ∗ ) λ∗ = 0 et h(x ∗ ) = 0
2° y T L(x ∗ , λ∗ )y > 0 ∀y ≠ 0 y T ∇h T (x ∗ ) = 0 ⇔ y ∈ T(x * )
<0
€
est un minimum local au sens strict de f(x) avec h(x)=0
maximum
Remarque: Si n = m alors la condition nécessaire du premier ordre
est aussi suffisante ( T(x*) est l’ensemble vide)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (11)
Exemple
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.1 Multiplicateurs de Lagrange (12)
Exemple (suite)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (1)
Problèmes avec contraintes d’inégalité
Contrainte actives-inactives
Une contrainte d’inégalité est active en x si
Elle est inactive si
Point régulier
Un point x* satisfaisant les contraintes h(x*)=0 et
l’ensemble des indices des contraintes actives est
appelé un point régulier si les vecteurs
sont linéairement indépendants
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (2)
V.21 Condition nécessaire du premier ordre
Soit x* qui minimise f(x) sous les contraintes h(x) = 0 et
(c(x) ≥ 0)
Si x* est un point régulier, alors
∃λ∗ , µ∗
1°µ∗ ≥ 0 (µ*≤ 0)
2° ∇f (x ∗ ) + ∇h T (x ∗ ) λ∗ + ∇c T (x ∗ ) µ∗ = 0
3° µ∗T c(x ∗ ) = 0
4° h(x * ) = 0 et c(x ∗ ) ≤ 0 (c(x*) ≥ 0)
contrainte inactive
€
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (3)
c2(x)=0
•
ensemble
admissible
c3(x)=0
c1(x)=0
minimum admissible
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (4)
V.22 Conditions nécessaires et suffisantes Hessien de
Soit
Hessien de f(x) Hessien de
Condition nécessaire du second ordre
Soit x* qui minimise f(x) sous les contraintes h(x) = 0 et
Si x* est un point régulier, alors (c(x) ≥ 0)
∃ λ∗ , µ∗
1° µ∗ ≥ 0 (µ* ≤ 0)
2° ∇f (x ∗ ) + ∇h T (x ∗ ) λ∗ + ∇c T (x ∗ ) µ∗ = 0 et h(x ∗ ) = 0 et c(x * ) ≤ 0
∗T ∗ (c(x*) ≥ 0)
3° µ c(x ) = 0
⎧ y T ∇h T (x ∗ ) = 0
4° y T L(x ∗ , λ∗ , µ∗ )y ≥ 0 ∀y ≠ 0 ⎨ T ∗ ⇔ y ∈ T (x*)
⎩ y ∇c j (x ) = 0 ∀j ∈ I(x*)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (5)
Condition suffisante (minimum)
si ∃ x * , λ∗ , µ∗
1° µ∗ ≥ 0 (µ* ≤ 0)
2° ∇f (x ∗ ) + ∇h T (x ∗ ) λ∗ + ∇c T (x ∗ ) µ∗ = 0 et h(x ∗ ) = 0 c(x ∗ ) ≤ 0
3° µ∗T c(x ∗ ) = 0 (c(x) ≥ 0)
⎧ y T ∇h T (x ∗ ) = 0
4° y T L(x ∗ , λ∗ , µ∗ )y > 0 ∀y ≠ 0 ⎨ T ∗ ⇔ y ∈ T(x * )
⎩ y ∇c j (x ) = 0 ∀j ∈ I(x*)
contraintes actives
est un minimum local au sens strict de f(x) avec h(x) = 0 et c(x) ≤ 0
Remarque: Si T(x*) est l’ensemble vide, alors la condition nécessaire
du premier ordre est aussi suffisante
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (6)
Condition suffisante (maximum)
si ∃ x * , λ∗ , µ∗
1° µ∗ ≤ 0 (µ* ≥ 0)
2° ∇f (x ∗ ) + ∇h T (x ∗ ) λ∗ + ∇c T (x ∗ ) µ∗ = 0 et h(x ∗ ) = 0 c(x ∗ ) ≤ 0
3° µ∗T c(x ∗ ) = 0 (c(x) ≥ 0)
⎧ y T ∇h T (x ∗ ) = 0
4° y T L(x ∗ , λ∗ , µ∗ )y < 0 ∀y ≠ 0 ⎨ T ∗ ⇔ y ∈ T(x * )
⎩ y ∇c j (x ) = 0 ∀j ∈ I(x*)
contraintes actives
est un maximum local au sens strict de f(x)
avec h(x) = 0 et c(x) ≤ 0
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (7)
Exemple
KKT
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (8)
Exemple (suite)
A. Contrainte active:
=> impossible
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.2 Conditions de Karush-Kuhn-Tucker (9)
Exemple (suite)
B. Contrainte inactive:
Minimum local
au sens strict
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.3 Méthode des pénalités (1)
Soit le problème d’optimisation
Ce problème est transformé en un problème d’optimisation
sans contrainte: p
min g(x, α k ) = f(x) + α k ∑ P (c (x))
i i
i=1
fonctions de pénalité
Avec :
1° P(c(x)) continu
€ 2° P(c(x)) ≥ 0 ∀x
3°
=> Problème d’optimisation sans contrainte
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.3 Méthode des pénalités (2)
V.31 Méthode des pénalités intérieures
c(x) ≤ 0 => ensemble admissible
Les pénalités sont proches de zéro loin des contraintes et tendent
vers l’infini aux limites des contraintes:
Par exemple: avec x dans l’espace
admissible
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.3 Méthode des pénalités (3)
V.31 Méthode des pénalités intérieures (suite)
Exemple
•
• f(x)=2x
•
•
ensemble admissible
c(x)=0
1
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.3 Méthode des pénalités (4)
V.32 Méthode des pénalités extérieures
c(x) ≤ 0 => ensemble admissible
Les pénalités sont nulles dans l’espace admissible et positives quand
les contraintes ne sont plus satisfaites:
Par exemple:
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.3 Méthode des pénalités (5)
V.32 Méthode des pénalités extérieures (suite)
Exemple
f(x)=2x
• •
•
• ensemble admissible
c(x)=0
1
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.4 Programmation quadratique séquentielle (SQP)
Fonction de Lagrange :
⇒Solution par la méthode de Newton
⇒Direction de recherche
⇒Minimisation du pas dans cette direction
⇒Mise à jour de l’estimée du Hessien
