View
239
Download
3
Category
Preview:
Citation preview
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.1 Multiplicateurs de Lagrange (1)
Problèmes avec contraintes d’égalité
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
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.1 Multiplicateurs de Lagrange (2)
V.111 Points réguliers (suite)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.112 Courbe sur une surface Une courbe C sur la surface S est un ensemble de points continûment paramétré par
Le vecteur est la tangente à la courbe C au point x*
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)
La courbe C passe par un point x* s’il existe t* tel que x(t*)=x*
Propriété
V.1 Multiplicateurs de Lagrange (3)
V.113 Espace tangent
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.114 Espace normal
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)
Propriété
Soit une courbe C sur la surface S passant par x* alors la tangente à la courbe
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
V.1 Multiplicateurs de Lagrange (4)
V.12 Condition nécessaire du premier ordre
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
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.1 Multiplicateurs de Lagrange (7)
Exemple (suite)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
• •
•
•
h(x)=0
f(x)=1
f(x)=1/2
1
-1
V.1 Multiplicateurs de Lagrange (8) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
• Maximum
Minimum
• •
Pas un extremum
h(x)=0
•
Condition vérifiée en x* et pas en y*
h(x)=0
V.1 Multiplicateurs de Lagrange (9)
V.13 Conditions nécessaires et suffisantes
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
Fonction de Lagrange
Hessien de f(x) Hessien de
Condition nécessaire du second ordre
le Hessien de l(x,λ)
Soit f(x) minimum en x* sous la contrainte h(x) = 0 Si x* est un point régulier, alors
V.1 Multiplicateurs de Lagrange (10)
Condition suffisante
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
€
si ∃x * ∃λ∗ 1° ∇f (x∗) +∇hT (x∗)λ∗ = 0 et h(x∗) = 0
2° yTL(x∗,λ∗)y > 0 ∀y ≠ 0 yT∇hT (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.2 Conditions de Karush-Kuhn-Tucker (1)
Problèmes avec contraintes d’inégalité
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
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.2 Conditions de Karush-Kuhn-Tucker (2) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.21 Condition nécessaire du premier ordre
€
∃λ∗,µ∗
1°µ∗ ≥ 02°∇f (x∗) +∇hT (x∗)λ∗ +∇cT (x∗)µ∗ = 03° µ∗Tc(x∗) = 04° h(x*) = 0 et c(x∗) ≤ 0
(µ*≤ 0)
(c(x) ≥ 0) Soit x* qui minimise f(x) sous les contraintes h(x) = 0 et
Si x* est un point régulier, alors
contrainte inactive
(c(x*) ≥ 0)
V.2 Conditions de Karush-Kuhn-Tucker (3) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
•
minimum admissible
ensemble admissible
c2(x)=0
c1(x)=0 c3(x)=0
V.2 Conditions de Karush-Kuhn-Tucker (4) V.22 Conditions nécessaires et suffisantes
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
Hessien de f(x) Hessien de
€
∃ λ∗,µ∗
1° µ∗ ≥ 02°∇f (x∗) +∇hT (x∗)λ∗ +∇cT (x∗)µ∗ = 0 et h(x∗) = 0 et c(x*) ≤ 03° µ∗Tc(x∗) = 0
4° yTL(x∗,λ∗,µ∗)y ≥ 0 ∀y ≠ 0yT∇hT (x∗) = 0yT∇c j (x
∗) = 0 ∀j ∈ I(x*)
⎧ ⎨ ⎩
⇔ y ∈T (x*)
(µ* ≤ 0)
Hessien de Soit
Condition nécessaire du second ordre
(c(x) ≥ 0) Soit x* qui minimise f(x) sous les contraintes h(x) = 0 et Si x* est un point régulier, alors
(c(x*) ≥ 0)
V.2 Conditions de Karush-Kuhn-Tucker (5)
Condition suffisante (minimum)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
€
si ∃ x*,λ∗,µ∗
1° µ∗ ≥ 02°∇f (x∗) +∇hT (x∗)λ∗ +∇cT (x∗)µ∗ = 0 et h(x∗) = 0 c(x∗) ≤ 0 3° µ∗Tc(x∗) = 0
4° yTL(x∗,λ∗,µ∗)y > 0 ∀y ≠ 0yT∇hT (x∗) = 0yT∇c j (x
∗) = 0 ∀j ∈ I(x*)
⎧ ⎨ ⎩
⇔ y ∈T(x*)
est un minimum local au sens strict de f(x) avec h(x) = 0 et c(x) ≤ 0
contraintes actives
(µ* ≤ 0)
(c(x) ≥ 0)
Remarque: Si T(x*) est l’ensemble vide, alors la condition nécessaire du premier ordre est aussi suffisante
V.2 Conditions de Karush-Kuhn-Tucker (6)
Condition suffisante (maximum)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
est un maximum local au sens strict de f(x) avec h(x) = 0 et c(x) ≤ 0
contraintes actives
(µ* ≥ 0)
(c(x) ≥ 0)
€
si ∃ x*,λ∗,µ∗
1° µ∗ ≤ 02°∇f (x∗) +∇hT (x∗)λ∗ +∇cT (x∗)µ∗ = 0 et h(x∗) = 0 c(x∗) ≤ 0 3° µ∗Tc(x∗) = 0
4° yTL(x∗,λ∗,µ∗)y < 0 ∀y ≠ 0yT∇hT (x∗) = 0yT∇c j (x
∗) = 0 ∀j ∈ I(x*)
⎧ ⎨ ⎩
⇔ y ∈T(x*)
V.2 Conditions de Karush-Kuhn-Tucker (8)
Exemple (suite)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
A. Contrainte active:
=> impossible
V.2 Conditions de Karush-Kuhn-Tucker (9)
Exemple (suite)
V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
B. Contrainte inactive:
Minimum local au sens strict
V.3 Méthode des pénalités (1) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
fonctions de pénalité Avec :
1° P(c(x)) continu 2° P(c(x)) ≥ 0 ∀x 3°
=> Problème d’optimisation sans contrainte
Soit le problème d’optimisation
€
min g(x,αk ) = f(x) +αk Pi(ci(x))i=1
p
∑
Ce problème est transformé en un problème d’optimisation sans contrainte:
V.3 Méthode des pénalités (2) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.31 Méthode des pénalités intérieures
Par exemple:
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:
avec x dans l’espace admissible
V.3 Méthode des pénalités (3) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.31 Méthode des pénalités intérieures (suite)
Exemple
ensemble admissible •
1
• •
• f(x)=2x
c(x)=0
V.3 Méthode des pénalités (4) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.32 Méthode des pénalités extérieures
Par exemple:
c(x) ≤ 0 => ensemble admissible
Les pénalités sont nulles dans l’espace admissible et positives quand les contraintes ne sont plus satisfaites:
V.3 Méthode des pénalités (5) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES
V.32 Méthode des pénalités extérieures (suite)
Exemple
•
1
• •
•
f(x)=2x
c(x)=0
ensemble admissible
Recommended