Programmation stochastique
Rappels doptimisation
Fabian Bastin
IFT-6512 Hiver 2011
Fabian Bastin
Rappels doptimisation
Rappels utiles en optimisation. . .
ees
Deriv
ee
directionnelle f de f dans la
Soit f : Rn R. La deriv
direction d est
f (x + d) f (x)
.
0
f (x, d) = lim
ee
directionnelle existe
f est dite differentiable
si cette deriv
n
et a la meme
valeur pour tout d R . Lunique valeur de
ee
est appelee
le gradient de f en x, denot
cette deriv
ee
x f (x).
Si f est differentiable,
nous avons aussi
f (x, d) = x f (x)T d.
Mais toutes les fonction que nous considererons
ne seront
pas differentiables.
Fabian Bastin
Rappels doptimisation
Sous-gradients
Un vecteur Rn est un sous-gradient dune fonction
convexe f en un point x si et seulement si
f (y) f (x) + T (y x), y Rn .
Le graphe de la fonction (lineaire)
h(y) = f (x) + T (y x)
est un hyperplan de support a` lensemble convexe epi(f )
au point (x, f (x)).
Lensemble de tous les sous-gradients de f en x est appele
le sous-differentiel
de f en x, denot
e par f (x).
eme
`
Theor
: f (x) si et seulement si
f (x, d) T d, d Rn .
`
Pourquoi ne considere-t-on
ici que des fonctions
convexes ? Lien avec le cas differentiable
: soit
n
1
: R R C . est convexe ssi x, y Rn ,
(y x)T x (x) (y) (x).
Fabian Bastin
Rappels doptimisation
Hyperplan de support
eralement
Hyperplan ? Gen
de la notion de plan. . .
On parle ici dhyperplan affine. Un hyperplan dans lespace Rn
peut etre
decrit
par lequation
n
X
ai xi = b.
i=1
Au moins un des ai , i = 1, . . . , n, est non nul.
eralisation
Hyperplan de support : gen
de la notion de tangente.
Un hyperplan de support a` f en x est un hyperplan
lintersection avec f dans un voisinage de x est le singleton
{x}, excepte dans les directions ou` f est lineaire,
auquel cas la
tangente se confond avec le graphe de f .
Fabian Bastin
Rappels doptimisation
Hyperplan de support (2)
Source : Wikipedia.
Fabian Bastin
Rappels doptimisation
Sous-differentiels
Le sous-differentiel
est toujours un ensemble compact
non-vide et convexe.
En une dimension, le sous-differentiel
de f en x0 est
lintervalle [a, b], avec
a = lim
xx0
b = lim+
xx0
f (x) f (x0 )
,
x x0
f (x) f (x0 )
.
x x0
Si f est differentiable
en x, f (x) = {x f (x)}.
Fabian Bastin
Rappels doptimisation
Illustration
Source : Wikipedia.
Fabian Bastin
Rappels doptimisation
Conditions doptimalite
Sous quelles conditions une solution est-elle optimale ?
Beaucoup dalgorithmes visent a` trouver des points qui
satisfont ces conditions.
`
On peut souvent apprendre beaucoup sur un probleme
en
es
de ses solutions optimales.
observant les propriet
Dans un premier temps, considerons
la minimisation de
fonction qui sont
unidimensionnelle ;
continue au sens de Lipschitz :
|f (a) f (b)| L|a b|;
differentiable.
Fabian Bastin
Rappels doptimisation
Conditions necessaires
Condition necessaire
pour que x soit une solution optimale :
f (x) = 0. Mais ce nest pas une condition suffisante !
9
1
(x-1)**2
1-(x-1)**2
-1
-2
-3
-4
-5
-6
-7
-8
-2
-1.5
-1
-0.5
0.5
f (x) = (x
1.5
1)2
-2
-1.5
-1
-0.5
0.5
1.5
f (x) = 1 (x 1)2
Condition suffisante pour que x soit (localement) optimal :
f (x) > 0.
Cela revient a` exiger que f (x) soit strictement convexe en x.
Fabian Bastin
Rappels doptimisation
Cas multidimensionnel
Soit f : Rn R C 2 (i.e. f est deux fois continument
differentiable).
Condition necessaire
: si x est un optimum (local),
x f (x ) = 0.
Mais x f (x) = 0 peut correspondre a` un maximum (local)
ou meme
a` un point selle !
Condition suffisante : f strictement convexe en x et
x f (x ) = 0. Ou f convexe sur Rn et x f (x ) = 0. Dans ce
dernier cas, nous avons pour tout x Rn
0 = (x x )T x f (x ) f (x) f (x )
et donc
f (x ) f (x), x Rn .
Fabian Bastin
Rappels doptimisation
(convexite),
Optimisation sous contraintes
`
Considerons
le probleme
(unidimensionnel) suivant :
min f (x).
0xu
Il y a trois cas, pour lesquels une solution optimales pourrait
etre
x = 0, 0 < x < u, x = u.
Si 0 < x < u, alors les conditions necessaires
et les
conditions suffisantes doptimalite sont les meme
que pour
le cas sans contraintes.
Si x = 0, nous devons avoir f (x)|x=0 0 (necessaire),
f (x)|x=0 > 0.
Si x = u, nous devons avoir f (x)|x=u0 0 (necessaire),
f (x)|x=u > 0.
Fabian Bastin
Rappels doptimisation
Conditions KKT
eralisation
`
Gen
a` des problemes
a` plus dune variable et
erales.
avec des contraintes plus gen
Intuition : si une contrainte est active (elle tient avec une
alors le gradient de la fonction objectif doit pointer
egalit
e),
` que la fonction objectif serait amelior
ee
en
de maniere
sortant de la region
de faisabilite.
Formellement : loppose du gradient de la fonction objectif
doit etre
une combinaison lineaire
des gradients des
contraintes actives.
KKT tient pour Karush-Kuhn-Tucker.
Karush-Kuhn-Tucker ou Kuhn-Tucker ? Meme
chose, juste
`
un probleme
de reconnaissance dauteur, Karush ayant
developp
e les conditions avec Kuhn-Tucker, mais son
papier est reste longtemps ignore.
Fabian Bastin
Rappels doptimisation
Exemple (x R2 )
`
Considerons
le probleme
min f (x) = x1 + x2
t.q. x12 + x22 2
x2 0.
La solution optimale est ( 2, 0). Le gradient de f est (1, 1).
Fabian Bastin
Rappels doptimisation
`
Probleme
canonique
`
eral
Nous considerons
le probleme
gen
min f (x)
xRn
t.q. ci (x) = 0, i E,
ci (x) 0, i I.
Ensemble realisable
:
C = {x | t.q. ci (x) = 0, i E; ci (x) 0, i I}.
Fabian Bastin
Rappels doptimisation
Conditions critiques au premier ordre
`
Lagrangien du probleme
avec contraintes :
X
i ci (x).
L(x, ) = f (x)
iEI
Conditions de Karush-Kuhn-Tucker :
x L(x , ) = 0,
ci (x ) = 0,
ci (x ) 0,
i
i ci (x
0,
) = 0,
Fabian Bastin
i E,
i I,
i I,
i E I.
Rappels doptimisation
Conditions critiques au premier ordre (2)
` equation
La premiere
des conditions KKT implique que
X
i x ci (x ),
x f (x ) =
iA(x )
ou`
A(x ) = E {i I | ci (x) = 0}.
A(x ) est lensemble des contraintes actives.
Geom
etriquement,
on observe que si x est une solution
optimale, alors x f (x ) est combinaison lineaire
des
contraintes actives. Si la contraintes est non-active, son poids
est nul.
Fabian Bastin
Rappels doptimisation
Conditions critiques au premier ordre (3)
multiplicateurs de Lagrange, ou variables
Les i sont appeles
duales. x est le vecteur des variables primales.
Les conditions KKT sont des conditions necessaire
si une
qualification de contraintes tient en x .
est la LICQ
La qualification de contraintes la plus utilisee
(Linear Independence Constraint Qualification - qualification de
contraintes dindependance
lineaire).
La LICQ tient si lensemble des gradients des contraintes
actives {x ci (x ), i A(x )} est lineairement
independant.
Fabian Bastin
Rappels doptimisation
Conditions de complementarit
e
La condition
i ci (x ) = 0,
i E I,
est connue sous le bnom de condition de complementarit
e,
puisquelle implique que pour i E I, i = 0 ou ci (x ) = 0.
e stricte.
Cas particulier : complementarit
au vecteur de Lagrange
Etant donne une solution x associee
, la condition de complementarit
e stricte tient si exactement
un des i et ci (x ) est nul, pour chaque index i I.
Autrement dit, nous avons i > 0, i I A(x ).
Fabian Bastin
Rappels doptimisation
Conditions au second-ordre
Un peu de maths. . .
`
eralement
Probleme
non-convexe : nous avons gen
besoin de
ees
seconde de f (. . . hypothese
` : f C 2 ).
connatre les deriv
x Rn et
Soit p = #I et m = #E. Pour des vecteurs donnes
p+m
R
, lensemble N+ (x, ) est defini
par
def
N+ (x, ) =
T
n x ci (x) w = 0 i E {j A(x) I : j > 0}
w R
.
et x ci (x)T w 0 i {j A(x) I : j = 0}
Fabian Bastin
Rappels doptimisation
Conditions necessaires
au second-ordre
Theorem (Conditions necessaires
au second-ordre)
`
Supposons que x est une solution locale de notre probleme
doptimisation et quune qualification de contrainte tient en x .
Soit un vecteur de multiplicateurs de Lagrange tel que les
conditions KKT soient satisfaites. La courbure du Lagrangien le
long des directions dans N+ (x , ) doit etre
non-negative,
`
cest-a-dire
w T 2xx L(x , )w 0, for all w N+ (x , ).
Fabian Bastin
Rappels doptimisation
Conditions suffisantes au second-ordre
ant linegalit
eme
`
edent,
En reforc
e du theor
prec
nous pouvons
deriver
des conditions suffisantes.
Theorem (Conditions suffisantes au second ordre)
Supposons que pour un certain point realisable
x Rn , il
existe un vecteur de Lagrange tel que les conditions KKT
soient satisfaites. Supposons de plus que
w T 2xx L(x , )w > 0, w N+ (x , ) avec w 6= 0.
`
Alors x est une solution locale stricte de notre probleme
doptimisation.
Note : ces conditions suffisantes sont valables sans necessiter
de qualification de contraintes.
Fabian Bastin
Rappels doptimisation
Retour a` lexemple
min x1 + x2 ,
tel que
x12 + x22 2
(),
x2 0
().
Conditions KKT
Faisabilite primale
x12 + x22 2,
x2 0.
Fabian Bastin
Rappels doptimisation
Retour a` lexemple (2)
Faisabilite duale
0,
0,
1 = (2x1 ),
1 = (2x2 ) .
Conditions de complementarit
e
(2 x12 x22 ) = 0,
x2 = 0.
Fabian Bastin
Rappels doptimisation
Un point de vue geom
etrique
Rappel : ensemble realisable
denot
e par A. On supposera
simplement ici que A est ferme.
Condition necessaire
: si x est un miminum local,
x f (x ) NA (x ),
ou` NA (x ) est le cone
normal a` A en x .
? (Encore des) definitions.
Question : definition
dun cone
..
Un sous-ensemble C dun espace vectoriel V est un cone
(lineaire)
si et seulement si x appartient a` C pour nimporte
quel x C et nimporte quel scalaire strictement positif de V .
Il est pointe si peut etre
nul.
Un cone
convexe est un cone
qui est ferme sous les
combinaisons convexe, i.e. si et seulement x + y C, ,
non-negatifs,
avec + = 1.
Fabian Bastin
Rappels doptimisation
Cone
tangent, cone
normal
eral.
Cadre gen
Nous dirons tout dabord quun vecteur w Rn
est tangent a` A en x A si pour toutes les sequences
de
vecteur {xi } avec xi x, et xi A, et toutes les sequences
de
scalaires positifs ti 0, il existe une sequence
wi w tel que
xi + ti wi A pour tout i.
Le cone
tangent TA (x) est la collection de tous les vecteurs
tangents a` A en x.
Le cone
normal NA (x) est le complement
orthogonal au cone
`
tangent, cest-a-dire
NA (x) = {v | v T w 0, w TA (x)}.
Oui, mais, en pratique ? ? ?
Fabian Bastin
Rappels doptimisation
Cone
tangent, cone
normal (2)
La definition
du cone
normal se simplifie fortement si A est
convexe. En effet, on a alors
NA (x) = {v | v T (x x0 ) 0, x0 A}.
La condition necessaire
doptimalite devient alors
x f (x )(x x ) 0, x A.
Si f est convexe (i.e. on est dans le cadre de la programmation
convexe), cette condition est de plus suffisante.
Fabian Bastin
Rappels doptimisation
eralisation
Gen
aux fonctions non-differentiables
Les choses se compliquent fortement, en particulier dans
le cas non-convexe. Nous naborderons que le cas
convexe. . . sans entrer dans les details
de lanalyse
convexe (sauf si vous y tenez vraiment !).
Globalement, cela revient a` remplacer x f (x) = 0 par
0 f (x).
Theorem
Soit une fonction convexe f : Rn R, et soit S un ensemble
convexe non vide. x arg minxS f (x) si (et seulement si) est
un sous-gradient de f en x tel que T (x x ) 0, x S.
Comparaison avec le cas differentiable
: la condition est
x f (x )(x x ) 0, x S (cf interpretation
geom
etrique).
Fabian Bastin
Rappels doptimisation
eralisation
Gen
aux fonctions non-differentiables
(2)
Demonstration.
On ne prouvera que la partie facile. . .
Si est un sous-gradient de f en x tel que T (x x ) 0,
x S, alors
f (x) f (x ) + T (x x ) f (x ), x S.
Par consequent,
x arg min f (x).
xS
Fabian Bastin
Rappels doptimisation
eralisation
Gen
aux fonctions non-differentiables
(3)
Theorem
Soit une fonction convexe f : Rn R. x arg minxRn f (x) si
(et seulement si) 0 f (x ).
Demonstration.
x arg minxRn f (x) si et seulement si est un
sous-gradient avec T (x x ) 0, x Rn .
Prenons x = x . On a
0 T (x x ) = T 0.
` lors, = 0.
Des
Ainsi, = 0 f (x ).
Fabian Bastin
Rappels doptimisation
eralisation
Gen
Theorem
Pour une fonction convexe f : Rn R et des fonctions
convexes gi : Rn R, i = 1, 2, . . . , m, sous certaines conditions
x est une solution optimale du probleme
`
de regularit
e,
min f (x) t.q. gi (x) 0, i = 1, 2, . . . , m
si et seulement si les conditions suivantes tiennent :
gi (x) 0, i = 1, 2, . . . , m,
1 , . . . , m R tels que
Pm
0 f (x ) + i=1 i gi (x ),
i 0, i = 1, . . . , m,
i gi (x ) = 0, i = 1, . . . , m.
Fabian Bastin
Rappels doptimisation
eralisation
Gen
nest pas
Que signifie m
i=1 i gi (x ) quand le sous-differentiel
reduit
a` un point (ce qui serait le cas si on pouvait parler de
gradient) ?
Que signifie additionner des ensembles ? Etant donne deux
ensembles C1 et C2 ,
C1 + C2 = {x1 + x2 | x1 C1 , x2 C2 }.
somme de Minkowski.
Cette operation
est aussi appelee
Fabian Bastin
Rappels doptimisation
Le vendeur de journaux (le retour. . . )
edent.
Retour a` lexemple du cours prec
`
Nous voulons resoudre
le probleme
max cx + Q(x),
x0
ou`
Q(x) = qx (q r )
F ()d.
` simples. . .
Les conditions KKT sont ici tres
Il suffit dannuler le gradient de lobjectif, en notant que
Q(x) = q (q r )F (x),
aussi, il faut resoudre
c + q (q r )F (x) = 0.
Fabian Bastin
Rappels doptimisation
Le vendeur de journaux (suite)
` lors
La solution x est des
x =F
qc
qr
Un exemple : c = 0.15, q = 0.25, r = 0.02, N(650, 80).
Alors
x = N 1 (0.1/0.23) 636.86.
Autre interpretation,
plus intuitive : supposons que le vendeur a
e sil
achete t journaux. Quel est le revenu marginal esper
` un journal supplementaire
achete
? Dun point de vue
economique,
nous souhaiterions que ce revenu marginal soit
egal
a` 0. . . comme explicite par les conditions KKT !
Fabian Bastin
Rappels doptimisation
Revenu marginal
e par MR ; on a
Denotons
le revenu marginal esper
MR(t) = c + qP[ t] + rP[ t]
= c + q(1 F (t)) + rF (t).
En annulant cette expression, on obtient
MR(t) = 0 ssi F (t) =
qc
,
qr
edente.
et donc on retrouve la solution prec
Pour des complements,
consultez Linderoth.
Fabian Bastin
Rappels doptimisation
