Optimisation sous contraintes
Fabrice Rossi
TELECOM ParisTech
Dcembre 2009/Janvier 2010
Plan
Rsultats thoriques
Introduction
Existence et unicit
Conditions doptimalit
Dualit
Second ordre
Algorithmes
Introduction
Gradient
Pnalisation
Dualit
2 / 32 F. Rossi
Plan
Rsultats thoriques
Introduction
Existence et unicit
Conditions doptimalit
Dualit
Second ordre
Algorithmes
Introduction
Gradient
Pnalisation
Dualit
3 / 32 F. Rossi Rsultats thoriques
Forme gnrale
un problme doptimisation (T) est dni par
minimiser sur R
n
J(x)
avec h
i
(x) = 0, 1 i p
g
j
(x) 0, 1 j q
rappel de vocabulaire :
les h
i
sont les contraintes dgalit (notes h(x) = 0)
les g
j
sont les contraintes dingalit (notes g(x) 0)
lensemble des contraintes est
( = x R
n
[h
i
(x) = 0, 1 i p et g
j
(x) 0, 1 j q
ensemble des points admissibles ou ralisables
4 / 32 F. Rossi Rsultats thoriques
Forme gnrale
un problme doptimisation (T) est dni par
minimiser sur R
n
J(x)
avec h
i
(x) = 0, 1 i p
g
j
(x) 0, 1 j q
rappel de vocabulaire :
les h
i
sont les contraintes dgalit (notes h(x) = 0)
les g
j
sont les contraintes dingalit (notes g(x) 0)
lensemble des contraintes est
( = x R
n
[h
i
(x) = 0, 1 i p et g
j
(x) 0, 1 j q
ensemble des points admissibles ou ralisables
4 / 32 F. Rossi Rsultats thoriques
Consquences
les contraintes changent les conditions doptimalit
exemple :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = 4 x
2
y
2
0
sur R
2
, on tudierait J = 2(x, y)
T
mais ici, le minimum vaut 4 et est atteint sur le cercle
x
2
+ y
2
= 4 sur lequel J ,= 0
mais pas toujours :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = x
2
+ y
2
4 0
le minimum est atteint en (0, 0), avec J = 0
les contraintes doivent donc apparatre dans les conditions
doptimalit
5 / 32 F. Rossi Rsultats thoriques
Consquences
les contraintes changent les conditions doptimalit
exemple :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = 4 x
2
y
2
0
sur R
2
, on tudierait J = 2(x, y)
T
mais ici, le minimum vaut 4 et est atteint sur le cercle
x
2
+ y
2
= 4 sur lequel J ,= 0
mais pas toujours :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = x
2
+ y
2
4 0
le minimum est atteint en (0, 0), avec J = 0
les contraintes doivent donc apparatre dans les conditions
doptimalit
5 / 32 F. Rossi Rsultats thoriques
Consquences
les contraintes changent les conditions doptimalit
exemple :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = 4 x
2
y
2
0
sur R
2
, on tudierait J = 2(x, y)
T
mais ici, le minimum vaut 4 et est atteint sur le cercle
x
2
+ y
2
= 4 sur lequel J ,= 0
mais pas toujours :
J(x, y) = x
2
+ y
2
minimiser sous la contrainte
g(x, y) = x
2
+ y
2
4 0
le minimum est atteint en (0, 0), avec J = 0
les contraintes doivent donc apparatre dans les conditions
doptimalit
5 / 32 F. Rossi Rsultats thoriques
Existence dun minimum
cas gnral : (T) : minJ(x), x ( R
n
on suppose :
J continue
et ( ferm et non vide
alors :
si :
C est born
ou si J est coercitive
alors (T) admet au moins une solution
6 / 32 F. Rossi Rsultats thoriques
Existence et unicit
remarque : si
( =
x R
n
[h
i
(x) = 0, 1 i p et g
j
(x) 0, 1 j q
avec des h
i
et g
j
continues, alors ( est ferm
si J est strictement convexe et ( est convexe, alors (T)
admet au plus une solution
problme convexe :
J est convexe
les h
i
sont afnes
les g
j
sont convexes
et donc ( est convexe
7 / 32 F. Rossi Rsultats thoriques
Condition du premier ordre
si J est Gteaux-diffrentiable en x
solution de (T) et si (
est convexe, alors :
x (, J(x
), x x
) 0
remarques :
intuitivement : on ne peut sloigner du minimum que dans
une direction de monte
gnralisable : notion de direction admissible
si x
est un point intrieur de ( alors J(x
) = 0
si J est convexe la condition est ncessaire et sufsante
8 / 32 F. Rossi Rsultats thoriques
galits et ingalits
Conditions ncessaires non qualies
cas particulier h
i
(x) = 0 et g
j
(x) 0 o tout est C
1
(J
inclus)
soit x
une solution de (T), alors il existe
= (
1
, . . . ,
p
)
et
= (
0
,
1
, . . . ,
q
) tels que
(
) ,= 0
h
i
(x
) = 0, 1 i p (admissibilit en galit)
g
j
(x
) 0, 1 j q (admissibilit en ingalit)
j
0, 0 j q
j
g
j
(x
) = 0, 1 j q (conditions de complmentarit)
et
0
J(x
) +
p
i =1
i
h
i
(x
) +
q
j =1
j
g
j
(x
) = 0
9 / 32 F. Rossi Rsultats thoriques
Qualication
condition utile si
0
,= 0
problme de qualication des contraintes :
conditions (locales) sur le problme qui garantissent que
0
,= 0
trs nombreuses variantes plus ou moins sophistiques
contrainte active : g
j
est active (ou sature) en x
si
g
j
(x
) = 0 ; I(x
), ensemble des indices des contraintes
actives en x
rgularit : x
est rgulier pour g et h si
x
est admissible
les h
i
(x
) sont linairement indpendants
il existe d ,= 0 tel que h
i
(x
), d) = 0 pour tout i et
g
j
(x
), d) < 0 pour tout j I(x
) (ou g
j
(x
), d) = 0 si
g
j
est afne)
rgularit de Mangasarian-Fromowitz
10 / 32 F. Rossi Rsultats thoriques
Qualication
condition utile si
0
,= 0
problme de qualication des contraintes :
conditions (locales) sur le problme qui garantissent que
0
,= 0
trs nombreuses variantes plus ou moins sophistiques
contrainte active : g
j
est active (ou sature) en x
si
g
j
(x
) = 0 ; I(x
), ensemble des indices des contraintes
actives en x
rgularit : x
est rgulier pour g et h si
x
est admissible
les h
i
(x
) sont linairement indpendants
il existe d ,= 0 tel que h
i
(x
), d) = 0 pour tout i et
g
j
(x
), d) < 0 pour tout j I(x
) (ou g
j
(x
), d) = 0 si
g
j
est afne)
rgularit de Mangasarian-Fromowitz
10 / 32 F. Rossi Rsultats thoriques
Qualication
condition utile si
0
,= 0
problme de qualication des contraintes :
conditions (locales) sur le problme qui garantissent que
0
,= 0
trs nombreuses variantes plus ou moins sophistiques
contrainte active : g
j
est active (ou sature) en x
si
g
j
(x
) = 0 ; I(x
), ensemble des indices des contraintes
actives en x
rgularit : x
est rgulier pour g et h si
x
est admissible
les h
i
(x
) sont linairement indpendants
il existe d ,= 0 tel que h
i
(x
), d) = 0 pour tout i et
g
j
(x
), d) < 0 pour tout j I(x
) (ou g
j
(x
), d) = 0 si
g
j
est afne)
rgularit de Mangasarian-Fromowitz
10 / 32 F. Rossi Rsultats thoriques
Conditions qualies
Conditions ncessaires qualies du 1er ordre de KKT
(Karush, Kuhn et Tucker)
Hypothses :
J, h et g C
1
x
solution de (T)
x
est rgulier pour g et h
Alors il existe
= (
1
, . . . ,
p
) et
= (
1
, . . . ,
q
) tels
que
h
i
(x
) = 0, 1 i p
g
j
(x
) 0, 1 j q
j
0, 1 j q
j
g
j
(x
) = 0, 1 j q
et
J(x
) +
p
i =1
i
h
i
(x
) +
q
j =1
j
g
j
(x
) = 0
11 / 32 F. Rossi Rsultats thoriques
Cas convexe
si le problme (T) est convexe, les conditions de KKT sont
ncessaires et sufsantes en un point x
rgulier
remarque : le caractre sufsant ne ncessite pas la
rgularit
conditions de qualication plus simples (de Slater) : il
existe au moins un point strictement admissible g(x) < 0
12 / 32 F. Rossi Rsultats thoriques
Lagrangien
le Lagrangien du problme (T) est la fonction
L(x, , ) = J(x) +
p
i =1
i
h
i
(x) +
q
j =1
j
g
j
(x)
quand J, h et g sont C
1
les conditions de KKT sexpriment
par
x
L(x
) = 0
les
i
et les
j
sont les multiplicateurs de Lagrange
associs aux contraintes
13 / 32 F. Rossi Rsultats thoriques
Dualit
fonction duale de Lagrange
g(, ) = inf
x
L(x, , )
g est toujours concave
pour 0
g(, ) inf
xC
J(x)
problme dual (Q) associ au problme primal (T)
maximiser sur R
p+q
g(, )
avec
j
0, 1 j q
saut de dualit : inf
xC
J(x) max
0
g(, )
14 / 32 F. Rossi Rsultats thoriques
Point selle
symtrisation du problme : (T) est quivalent
inf
x
sup
,0
L(x, , )
le problme dual (Q) est
sup
,0
inf
x
L(x, , )
point selle : minimal par rapport une variable, maximal
par rapport lautre
(x
) est un point selle du Lagrangien si pour tout
(x, , ) (
0 et 0)
L(x
, , ) L(x
) L(x,
)
15 / 32 F. Rossi Rsultats thoriques
Point selle
symtrisation du problme : (T) est quivalent
inf
x
sup
,0
L(x, , )
le problme dual (Q) est
sup
,0
inf
x
L(x, , )
point selle : minimal par rapport une variable, maximal
par rapport lautre
(x
) est un point selle du Lagrangien si pour tout
(x, , ) (
0 et 0)
L(x
, , ) L(x
) L(x,
)
15 / 32 F. Rossi Rsultats thoriques
Thorme de dualit
(x
) est un point selle avec
0 ssi x
est une
solution de (T), (
) est une solution de (Q) et le saut
de dualit est nul
intrt : pour rsoudre le problme, on peut donc chercher
un point selle du Lagrangien
remarque : un point selle du Lagrangien vrie les
conditions de KKT (sans hypothse autre que J, h et g C
1
)
si le problme est convexe : point selle KKT
16 / 32 F. Rossi Rsultats thoriques
Thorme de dualit
(x
) est un point selle avec
0 ssi x
est une
solution de (T), (
) est une solution de (Q) et le saut
de dualit est nul
intrt : pour rsoudre le problme, on peut donc chercher
un point selle du Lagrangien
remarque : un point selle du Lagrangien vrie les
conditions de KKT (sans hypothse autre que J, h et g C
1
)
si le problme est convexe : point selle KKT
16 / 32 F. Rossi Rsultats thoriques
Rgularit
Condition plus forte que celle de Mangasarian-Fromowitz :
x
est admissible
h
i
(x
) et les g
j
(x
) sont linairement indpendants pour
j I(x
)
Contraintes fortement actives :
I
+
(x
) = j [ g
j
(x
) = 0 et
j
> 0
si I(x
) = I
+
(x
) on a complmentarit stricte
17 / 32 F. Rossi Rsultats thoriques
Conditions ncessaires du 2me ordre
Hypothses :
J, h et g C
2
x
solution de (T) et fortement rgulier
alors il existe
= (
1
, . . . ,
p
) et
= (
1
, . . . ,
q
) tels
que
les conditions de KKT sont vries
et pour tout d vriant :
h
i
(x
), d = 0 pour 1 i p
g
j
(x
), d = 0 pour j I
+
(x
)
g
j
(x
), d 0 pour I(x
) \ I
+
(x
)
on a
2
xx
L(x
)d, d
0
18 / 32 F. Rossi Rsultats thoriques
Conditions sufsantes
Hypothses :
J, h et g C
2
(x
) vrie les conditions KKT
si la matrice
2
xx
L(x
) est dnie positive sur
d R
n
[ h
i
(x
), d) = 0, 1 i , p
et
g
j
(x
), d
= 0, j I
+
(x
alors x
est un minimum local de J sur (
19 / 32 F. Rossi Rsultats thoriques
Plan
Rsultats thoriques
Introduction
Existence et unicit
Conditions doptimalit
Dualit
Second ordre
Algorithmes
Introduction
Gradient
Pnalisation
Dualit
20 / 32 F. Rossi Algorithmes
Classes dalgorithmes
quelques grandes classes dalgorithmes :
gradient projet :
descente de gradient
projection sur C chaque tape
pnalisation :
optimisation sans contrainte de J+pnalit
mthodes extrieures : on ramne progressivement le
candidat minimum dans C
mthodes intrieures : on relche progressivement les
pnalits
programmation quadratique successive : rsoudre des
approximations quadratiques du problme
principe sous-jacent : rsoudre une srie de problmes
sans contrainte (ou plus simple)
21 / 32 F. Rossi Algorithmes
Projection
outil important : projection sur un convexe ferm
soit C un convexe ferm et non vide de R
n
pour tout x alors
C
(x) = arg min
yC
|x y|
2
existe et est unique
proprits :
C
(x) est lunique lment de C tel que
y C, x
C
(x), y
C
(x)) 0
ou encore tel que
y C,
C
(x) y, y x) 0
22 / 32 F. Rossi Algorithmes
Projection
C
est une contraction :
x, y, |
C
(x)
C
(y)| |x y|
preuve simple :
on a
x
C
(x),
C
(y)
C
(x)) 0
y
C
(y),
C
(x)
C
(y)) 0
soit
x y,
C
(y)
C
(x)) +|
C
(x)
C
(y)|
2
0
et on termine par Cauchy-Schwartz
23 / 32 F. Rossi Algorithmes
Gradient projet
minimisation de J sur C convexe ferm
algorithme :
1. point initial x
0
2. pour k 1 croissant
2.1 calculer y
k+1
= x
k
k
J(x
k
)
2.2 puis x
k+1
=
C
(y
k+1
)
2.3 tester la convergence et quitter la boucle le cas chant (par
ex. x
k+1
x
k
< )
formulation simple mais mise en oeuvre potentiellement
dlicate :
si C est simple (par ex., l
i
x
i
u
i
), pas de problme
sinon le calcul de
C
(y
k+1
) est un problme doptimisation
sous contraintes
24 / 32 F. Rossi Algorithmes
Gradient projet
minimisation de J sur C convexe ferm
algorithme :
1. point initial x
0
2. pour k 1 croissant
2.1 calculer y
k+1
= x
k
k
J(x
k
)
2.2 puis x
k+1
=
C
(y
k+1
)
2.3 tester la convergence et quitter la boucle le cas chant (par
ex. x
k+1
x
k
< )
formulation simple mais mise en oeuvre potentiellement
dlicate :
si C est simple (par ex., l
i
x
i
u
i
), pas de problme
sinon le calcul de
C
(y
k+1
) est un problme doptimisation
sous contraintes
24 / 32 F. Rossi Algorithmes
Convergence
si J est C
1
, -convexe et de drive M-lipschitzienne
et si
k
[
1
,
2
] avec 0 <
1
<
2
<
2
M
2
alors lalgorithme du gradient projet converge :
preuve trs proche de celle du cas sans contrainte
si x
est loptimum, on a pour tout
x
=
C
(x
J(x
))
donc par contraction de
C
|x
k+1
x
|
2
|(x
k
k
J(x
k
)) (x
k
J(x
))|
2
ce qui nous ramne au cas sans projection
25 / 32 F. Rossi Algorithmes
Pnalisation
ide principale : remplacer un problme avec contraintes
par un problme sans contrainte dont la fonction objectif
dcourage les points non admissibles
solution nave :
on dnit
(x) =
+ x , C
0 x C
alors trouver arg min
xC
J(x) est quivalent trouver
arg min
xR
n J(x) +(x)
solutions ralistes : utiliser une fonction rgulire (C
1
au
moins) petite sur C et grande en dehors
26 / 32 F. Rossi Algorithmes
Mthodes de point extrieur
vrie :
est continue sur R
n
(x) 0
(x) = 0 x C
Exemples :
h(x) = 0 est reprsente par (x) = |h(x)|
2
g(x) 0 est reprsente par (x) = |g
+
(x)|
2
on considre la famille de problmes (T
r
) pour r > 0
dnis par
min
xR
n
(J(x) + r (x))
mthodes de point extrieur : on ne peut pas garantir
x
r
C
27 / 32 F. Rossi Algorithmes
Mthodes de point intrieur
mme principe, mais avec des points lintrieur de C
pour les contraintes dingalit seulement
est une barrire et vrie :
est continue sur
C
x , C (x) =
pour les contraintes g(x) 0, on prend gnralement
j =1
log(g
j
(x))
comme pour les mthodes de point extrieur, on considre
les problmes (T
r
) pour r > 0 dnis par
min
xR
n
(J(x) + r (x))
ici, on a toujours x
C
28 / 32 F. Rossi Algorithmes
Pnalisation
minimisation de J sur C convexe ferm
algorithme (pour une suite (r
k
)
k
croissante) :
1. point initial x
0
2. pour k 1 croissant
2.1 rsoudre le problme (P
r
k
)
min
xR
n
(J(x) + r
k
(x))
en partant de la solution x
k1
2.2 tester la qualit du point obtenu x
k
et quitter la boucle le cas
chant
fonctionne trs bien en pratique pour le cas du point
intrieur (on rsout (T
r
k
) par une mthode de
(quasi)Newton avec contraintes dgalits)
lefcacit vient du redmarrage depuis un bon candidat
29 / 32 F. Rossi Algorithmes
Pnalisation
minimisation de J sur C convexe ferm
algorithme (pour une suite (r
k
)
k
croissante) :
1. point initial x
0
2. pour k 1 croissant
2.1 rsoudre le problme (P
r
k
)
min
xR
n
(J(x) + r
k
(x))
en partant de la solution x
k1
2.2 tester la qualit du point obtenu x
k
et quitter la boucle le cas
chant
fonctionne trs bien en pratique pour le cas du point
intrieur (on rsout (T
r
k
) par une mthode de
(quasi)Newton avec contraintes dgalits)
lefcacit vient du redmarrage depuis un bon candidat
29 / 32 F. Rossi Algorithmes
Convergence
on suppose J continue et coercitive, et C ferm et non vide
on considre une mthode de point extrieur
rsultat :
pour tout r > 0, (T
r
) possde au moins une solution
toute famille (x
r
)
r >0
de solutions est borne
les valeurs dadhrence de toute famille (x
r
)
r >0
de
solutions sont des solutions de (T)
preuve (x
est une solution de (T)) :
J
r
(x) = J(x) + r (x) est coercitive et continue
x
r
solution de (T
r
), J(x
r
) J
r
(x
r
) J
r
(x
) = J(x
), donc
(x
r
)
r >0
est borne
comme (x
r
)
1
r
(J(x
) J(x
r
)), on a lim
r +
(x
r
) = 0
et donc pour toute valeur dadhrence
x, J(
x) J(x
)
30 / 32 F. Rossi Algorithmes
Convergence
on suppose J continue et coercitive, et C ferm et non vide
on considre une mthode de point extrieur
rsultat :
pour tout r > 0, (T
r
) possde au moins une solution
toute famille (x
r
)
r >0
de solutions est borne
les valeurs dadhrence de toute famille (x
r
)
r >0
de
solutions sont des solutions de (T)
preuve (x
est une solution de (T)) :
J
r
(x) = J(x) + r (x) est coercitive et continue
x
r
solution de (T
r
), J(x
r
) J
r
(x
r
) J
r
(x
) = J(x
), donc
(x
r
)
r >0
est borne
comme (x
r
)
1
r
(J(x
) J(x
r
)), on a lim
r +
(x
r
) = 0
et donc pour toute valeur dadhrence
x, J(
x) J(x
)
30 / 32 F. Rossi Algorithmes
Algorithme dUzawa
ide : chercher directement un point selle du Lagrangien
algorithme (paramtre > 0) :
1. valeurs initiales des multiplicateurs
1
,
1
2. pour k 1 croissant
2.1 trouver x
k
solution du problme (sans contrainte)
min
xR
n
L(x,
k
,
k
)
2.2 mettre jour (
k
,
k
) par
k+1
i
=
k
i
+h
i
(x
k
)
k+1
j
= max(0,
k
j
+g
j
(x
k
))
2.3 tester la convergence et quitter la boucle le cas chant (par
ex. x
k+1
x
k
< )
31 / 32 F. Rossi Algorithmes
Algorithme dUzawa
on peut montrer que lalgorithme dUzawa est un gradient
projet sur le problme dual :
on montre que g(, ) = (, )
T
on maximise g(, ), ce qui explique le signe dans la mise
jour des multiplicateurs
intressant parce que la projection est triviale
Convergence :
si J est C
1
, -convexe, h afne et g convexe et M
g
lipschitzienne
et si L possde un point selle (x
)
alors lalgorithme converge vers x
pour tout choix de
dans ]0,
2
M
2
g
+M
2
h
[
32 / 32 F. Rossi Algorithmes
