RO - 00 - Résumé

RESUME DE RECHERCHE OPERATIONNELLE
RO – Résumé
I. Dérivées
1. Ligne de niveau
𝑁𝑐 = {𝑥 ∈ ℝ𝑛 |𝐽(𝑥) = 𝑐}
2. Dérivée première
a. Gradient
𝜕𝐽 𝜕𝐽 ⊤
∇ 𝐽(𝑥0 ) = [ ,…, ]
𝜕𝑥1 𝜕𝑥𝑛
Propriété : Au point 𝑥0 , ∇ 𝐽(𝑥0 ) est ⏊ à la ligne de niveau, son sens va dans le sens de 𝐽 croissant.
b. Dérivée directionnelle
𝜑(𝜀)
𝐽(𝑥 + 𝜀𝑑) − 𝐽(𝑥) 𝑑⏞

𝐽(𝑥 + 𝜀𝑑)
𝐷𝑥 𝐽(𝑥, 𝑑) = lim = = 𝜑′ (0) = ∇ 𝐽(𝑥)⊤ 𝑑
𝜀→0 𝜀 𝑑𝜀
⌋𝜀=0
c. Plan tangent
Passe par (𝑥0 , 𝐽(𝑥0 )) et vecteur directeur ∇ 𝐽(𝑥0 ) Approximation locale de 𝐽
𝑃 = {𝑥 ∈ ℝ𝑛 | ∇ 𝐽(𝑥0 )⊤ (𝑥 − 𝑥0 ) = 0} 𝐽(𝑥) ≈ 𝑃(𝑥) = 𝐽(𝑥0 ) + ∇ 𝐽(𝑥0 )⊤ 𝑥
d. Développement limité au premier ordre
∇ 𝐽(𝑥)⊤ 𝑑 + 𝑜(𝜀)
𝐽(𝑥) ≈ 𝐽(𝑥 + 𝜀𝑑) = 𝐽(𝑥) + 𝜀 ⏟
𝐷𝐽𝑥 (𝑥,𝑑)
e. Règles de calcul pour la dérivée

𝐷(𝐽1 + 𝛼𝐽2 ) = 𝐷𝐽1 + 𝛼𝐽2 𝐷(𝐽1 (𝐽2 )) = 𝐷𝑧 𝐽1 (𝑧 = 𝐽2 ) 𝐷𝑥 𝐽2 (𝑥) ∇ 𝑎⊤ 𝑥 = 𝑎 ∇ 𝑥 ⊤ 𝐴𝑥 = 2𝐴𝑥
3. Dérivées secondes
a. Dérivée directionnelle au sens de Gâteaux
𝐷𝐽𝑥 (𝑥 + 𝑒𝑑) − 𝐷𝐽𝑥 (𝑥)
𝐷 2 𝐽(𝑥, 𝑑) = lim
𝜀→0 𝜀
b. Matrice Hessienne
𝜕 2 𝐽(𝑥) 𝜕 2 𝐽(𝑥) 𝜕 2 𝐽(𝑥) Calcul pratique :
… …
𝜕𝑥1 𝜕𝑥1 𝜕𝑥1 𝜕𝑥𝑗 𝜕𝑥1 𝜕𝑥𝑛 A partir de la dérivée de
⋮ ⋱ ⋮ ⋱ ⋮
2
𝜕 𝐽(𝑥) 2
𝜕 𝐽(𝑥) 2
𝜕 𝐽(𝑥) 𝜑(𝜀) = 𝐷𝑥 𝐽(𝑥 + 𝜀𝑑)
𝐻𝐽 (𝑥) = … …
𝜕𝑥𝑖 𝜕𝑥1 𝜕𝑥𝑖 𝜕𝑥𝑗 𝜕𝑥𝑖 𝜕𝑥𝑛 Identifier 𝐻 dans 𝜑′ (0) :
⋮ ⋱ ⋮ ⋱ ⋮ 𝜑′ (0) = 𝑑⊤ 𝐻𝑋 (𝑥)⊤ 𝑑
𝜕 2 𝐽(𝑥) 𝜕 2 𝐽(𝑥) 𝜕 2 𝐽(𝑥)
… …
(𝜕𝑥𝑛 𝜕𝑥1 𝜕𝑥𝑛 𝜕𝑥𝑗 𝜕𝑥𝑛 𝜕𝑥𝑛 )
c. Développement limité au second ordre
1
𝐽(𝑥 + 𝑑) = 𝐽(𝑥) + 𝐷𝑥 𝐽(𝑥, 𝑑) + 𝐷𝑥2 𝐽(𝑥, 𝑑) + 𝑜(‖𝑑‖2 )
2
1
𝐽(𝑥 + 𝑑) = 𝐽(𝑥) + ∇𝑥 𝐽(𝑥) 𝑑 + 𝑑⊤ 𝐻𝑑
⊤
+ 𝑜(‖𝑑‖2 )
2
Thomas v1
ROBERT
1
RO – Résumé
II. Généralités
Variables 𝑽 𝑉 ∈ ℝ𝑝
𝑞
Objectifs 𝑶 𝑉 ↦ ℝ min 𝐽(𝑥)
𝑥∈Ω
ℎ𝑖 (𝑥) = 0 𝐻(𝑥) = (ℎ1 , … , ℎ𝑛 )⊤ = 0
Contraintes 𝑪 𝑉 ↦ ℝ𝑚+𝑛 { ⟺{
𝑔𝑗 (𝑥) ≤ 0 𝐺(𝑥) = (𝑔1 , … , 𝑔𝑚 )⊤ ≤ 0
Domaine de faisabilité 𝛀 Ω = {𝑥 ∈ ℝ𝑑 ; 𝐻(𝑥) = 0 et 𝐺(𝑥) ≤ 0}
Fonction coût 𝐽: Ω ↦ ℝ
dom 𝐽 = {𝑥 ∈ Ω ; −∞ < 𝐽(𝜃) < +∞}
Domaine de la fonction coût
Si ∅, fonction coût impropre : pas de solution
Minimum global 𝜽∗ 𝐽(𝜃 ∗ ) ≤ 𝐽(𝜃) ∀ 𝜃
̂ 𝐽(𝜃̂) ≤ 𝐽(𝜃) ∀ 𝜃 | ‖𝜃̂ − 𝜃‖ ≤ 𝜀
Minimum local 𝜽
III. Optimisation convexe sous contraintes

1. Avec contraintes d’égalités
Problème Lagrangien Conditions d’optimalité
𝑝 𝑝
min 𝐽(𝑥) 𝐿(𝑥, 𝜆) = 𝐽(𝑥) + ∑ 𝜆𝑗 𝐻𝑗 (𝑥) ∇𝑥 𝐿 = 0 ⇒ ∇𝑥 𝐽(𝑥) + ∑ 𝜆𝑖 ∇𝑥 𝐻𝑗 (𝑥) = 0

{𝑥∈ℝ𝑛
𝑠. 𝑐. 𝐻(𝑥) = 0 𝑗=1 𝑗=1
𝜆𝑗 multiplicateurs de Lagrange ∇𝜆𝑗 𝐿 = 0 ⇒ 𝐻𝑗 (𝑥) = 0
2. Avec contraintes d’inégalités

a. Lagrangien et conditions d’optimalité
Problème Lagrangien Conditions d’optimalité KKT
𝑝 𝑞 Stationarité : ∇𝐿(𝑥, 𝜆) = 0
min𝑛 𝐽(𝑥) 𝐺(𝑥) ≤ 0
𝑥∈ℝ 𝐿(𝑥, 𝜆, 𝜇) = 𝐽(𝑥) + ∑ 𝜆𝑗 𝐻𝑗 (𝑥) + ∑ 𝜇𝑖 𝐺𝑖 (𝑥) Adm. primale :
{s.c. 𝐻(𝑥) = 0 𝐻(𝑥) = 0
𝑗=1 𝑖=1
et 𝐺(𝑥) ≤ 0 Adm. duale : 𝜇𝑖 ≥ 0
𝜆𝑗 multiplicateurs de Lagrange Complémentarité : 𝜇𝑖 𝑔𝑖 (𝑥) = 0
b. Problème dual
Le problème dual est ℒ(𝜇, 𝜆) = min 𝐿(𝑧, 𝜆, 𝜇)
𝑥
Thomas v1
ROBERT
2
RO – Résumé
IV. Optimisation convexe sans contraintes

1. Matrice définie positive
𝑨 définie positive 𝑨 définie négative 𝑨 quadratique
𝜆𝑖 ≤ 0 𝜆𝑖 ≥ 0 𝜆𝑖 ≤ 0
𝐽 convexe {𝜆 ≥ 0
𝑗
2. Condition d’optimalité
a. Existence de solution
𝑱 est coercivité ‖𝑥‖ → ∞ ⇒ 𝐽(𝑥) → ∞ (fonction infinie à l’infini)
𝑱 est propre ∃ 𝑥 | 𝐽(𝑥) ∈ ℝ
∃ solution globale Si 𝐽 continue, propre, coercive, min
𝑥
𝐽(𝑥) admet une solution globale
b. Conditions d’optimalité
1er ordre 𝑥0 solution ⇒ ∇ 𝐽(𝑥0 ) = 0
𝑥0 solution ⇒ ∇ 𝐽(𝑥0 ) = 0 et 𝐻(𝑥0 ) définie positive
2ème ordre
∇ 𝐽(𝑥0 ) = 0 et 𝐻(𝑥0 ) définie positive ⇒ 𝑥0 solution locale
𝐽 est convexe et 𝑥0 respecte condition d’optimalité
Convexité
⇒ 𝑥0 = 𝑥 ∗ solution globale
3. Optimisation itérative
a. Recherche linéaire (line search)
𝑥𝑘+1 = 𝑥𝑘 + 𝜌𝑘 𝑑𝑘 lim 𝑥𝑘 = 𝑥 ∗ = argmin 𝐽(𝑥)
𝑘→∞ 𝑥∈ℝ𝑛
i. Direction de descente 𝑑 (𝛻𝐽⊤ 𝑑 < 0)

 Gradient : 𝑑𝑘 = −∇𝐽 𝒪(𝑛)
 Gradient conjugué : 𝑑𝑘 = −∇𝐽 + 𝛽𝑘 𝑑𝑘−1 𝒪(𝑛2 )
 Quasi-Newton : 𝑑𝑘 = −𝐵∇𝐽 (Ex : 𝐵 = 𝑑𝑖𝑎𝑔(𝐻)−1 ) 𝒪(𝑛2 )
 Newton : 𝑑𝑘 = −𝐻 −1 ∇𝐽 𝒪(𝑛3 )
ii. Choix du pas 𝜌

 Pas fixe : 𝜌𝑘 = 𝑐 𝒪(1)
𝛼𝜌 si 𝐽 diminue 𝛼 = 1,15
 Pas variable : 𝜌𝑘 = { 𝑘−1 𝒪(1)
𝛼𝜌𝑘−1 si 𝐽 augmente 𝛽 = 0,5
argmin 𝐽(𝑥 + 𝜌𝑑)
𝜌∈ℝ+ < 𝒪(𝑛2 )
 Pas optimal : 𝜌𝑘 = { ⊤
𝑑 𝑑 𝒪(𝑛2 )
𝑑 ⊤ 𝐻𝑑
b. Région de confiance (trust region)

Comme recherche linéaire avec saut maximum limité par une région de confiance
𝑥𝑘+1 = 𝑥𝑘 + 𝑑𝑘 avec 𝑑𝑘 = argmin 𝑀(𝑥𝑘 + 𝑑)

𝑑∈𝑹(𝒙𝒌 )
𝑅(𝑥) : région de confiance autour de 𝑥 𝑀(𝑥 + 𝑑) : modèle dans la région de confiance (DL)
Thomas v1
ROBERT
3
RO – Résumé
V. Programmation linéaire
1. Forme standard
𝑧 : 𝑚 inconnues
min 𝑐 ⊤ 𝑧
𝑧∈ℝ𝑚 𝑐 : 𝑚 couts
{ 𝐴𝑧 = 𝑏
𝐴 : 𝑝 contraintes (𝑝 < 𝑚)
𝑧≥0 𝑏 : 𝑝 seconds membres des contraintes
2. Méthodes de réduction à la forme standard
a. Inégalités ⇒ variables d’écart (positives)
𝑥 𝑓𝑖 (𝑥) ≥ 𝑏𝑖 ⟺ 𝑓𝑖 (𝑥) − 𝑒𝑖 = 𝑏𝑖
𝑧=[ ]
𝑒 𝑓𝑖 (𝑥) ≤ 𝑏𝑖 ⟺ 𝑓𝑖 (𝑥) + 𝑒𝑖 = 𝑏𝑖
b. Variables non contraintes ⇒ décomposition

𝑥𝑖 = 𝑥𝑖+ − 𝑥𝑖−
𝑥𝑖 sans contraintes remplacé par {
𝑥𝑖+ , 𝑥𝑖− ≥ 0
3. Forme duale standard

max 𝑏 ⊤ 𝑦
𝑝
{𝑦∈ℝ 𝑐 ⊤𝑥 ∗ = 𝑏⊤𝑦 ∗ 𝑦=𝜆
⊤
𝐴 𝑦≤𝑐
4. Méthode du point intérieur

a. Principe
Résolution d’un problème à la forme standard en résolvant simultanément le primal et le dual à
travers les KKT, en les écrivant sous la forme 𝐹(𝑧, 𝜆, 𝜇) = 0 avec 𝑧, 𝜇 ≥ 0.
Δ𝑧
C’est une méthode itérative de Newton projeté appliquée à 𝐹 (Δ𝜆 ).
Δ𝜇
b. Maths et algorithme
𝐴⊤ 𝜆 + 𝜇 − 𝑐 = 0 Forme matricielle de 𝑭 :
min𝑚 𝑐 ⊤ 𝑧 𝐴𝑧 = 𝑏 } ⟺ 𝐹(𝑧, 𝜆, 𝜇) = 0 𝐹(𝑧) = 𝐴𝐹 × 𝑥𝐹 + 𝑏𝐹
𝑧∈ℝ
{ 𝐴𝑧 = 𝑏 𝑑𝑖𝑎𝑔(𝜇)𝑧 = 0
𝑧≥0 𝑚 𝑝 𝑚
𝑧≥0
𝜇≥0
𝑚 0 𝐴⊤ 𝐼 𝑧 −𝑐
𝑧 𝑧 Δ𝑧
𝜆 𝜆 Δ𝜆 𝑝 𝐴 0 0 × 𝜆 + −𝑏
( ) = ( ) = 𝑝𝑎𝑠 × ( )
𝜇 𝜇 ⏟Δ𝜇 𝑑𝑖𝑎𝑔
𝑑 𝑚 0 0 𝜇 𝛿𝜎
(𝜇)
Avec un DL au 1er ordre :
⏟ + 𝑑) = 𝐹(𝑥) + 𝑑⊤ ∇𝑥 𝐹(𝑥) + 𝑜(‖𝑑‖)
𝐹(𝑥 ⏟
=0 =0 Pour que ça marche, on met 𝛿𝜎 dans 𝑏𝐹 avec
⇒ 𝑑 = ∇𝑥 𝐹(𝑥) 𝐹(𝑥) −1 𝛿 = 𝜇⊤ 𝑧 et 𝜎 ≪ 1
0 𝐴⊤ 𝐼
∇𝑥 𝐹(𝑥) = ( 𝐴 0 0 ) On calcule le pas tel que 𝑧 ≥ 0, 𝜇 ≥ 0.
𝑑𝑖𝑎𝑔(𝜇) 0 𝑑𝑖𝑎𝑔(𝑧)
Thomas v1
ROBERT
4

RO - 00 - Résumé

Transféré par

Droits d'auteur :

Formats disponibles

RO - 00 - Résumé

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

RO - 00 - Résumé

Transféré par

Droits d'auteur :

Formats disponibles

RESUME DE RECHERCHE OPERATIONNELLE

𝐽(𝑥 + 𝜀𝑑) − 𝐽(𝑥) 𝑑⏞

e. Règles de calcul pour la dérivée

III. Optimisation convexe sous contraintes

min 𝐽(𝑥) 𝐿(𝑥, 𝜆) = 𝐽(𝑥) + ∑ 𝜆𝑗 𝐻𝑗 (𝑥) ∇𝑥 𝐿 = 0 ⇒ ∇𝑥 𝐽(𝑥) + ∑ 𝜆𝑖 ∇𝑥 𝐻𝑗 (𝑥) = 0

2. Avec contraintes d’inégalités

IV. Optimisation convexe sans contraintes

i. Direction de descente 𝑑 (𝛻𝐽⊤ 𝑑 < 0)

ii. Choix du pas 𝜌

b. Région de confiance (trust region)

𝑥𝑘+1 = 𝑥𝑘 + 𝑑𝑘 avec 𝑑𝑘 = argmin 𝑀(𝑥𝑘 + 𝑑)

b. Variables non contraintes ⇒ décomposition

3. Forme duale standard

4. Méthode du point intérieur

Vous aimerez peut-être aussi