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 (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)

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.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é

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 (7)

Exemple

V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES

KKT

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

V.4 Programmation quadratique séquentielle (SQP) V. OPTIMISATION AVEC CONTRAINTES NON LINEAIRES

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