Optimisation sous contraintes

Fabrice Rossi

TELECOM ParisTech

Dcembre 2009/Janvier 2010

Plan

Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

AlgorithmesIntroductionGradientPnalisationDualit

2 / 32 F. Rossi

Plan

Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

AlgorithmesIntroductionGradientPnalisationDualit

3 / 32 F. Rossi Rsultats thoriques

Forme gnrale

un problme doptimisation (P) est dfini par

minimiser sur Rn J(x)avec hi(x) = 0 ,1 i p

gj(x) 0 ,1 j q

rappel de vocabulaire : les hi sont les contraintes dgalit (notes h(x) = 0) les gj sont les contraintes dingalit (notes g(x) 0) lensemble des contraintes est

C = {x Rn|hi(x) = 0 ,1 i p et gj(x) 0 ,1 j q}

ensemble des points admissibles ou ralisables

4 / 32 F. Rossi Rsultats thoriques

Forme gnrale

un problme doptimisation (P) est dfini par

minimiser sur Rn J(x)avec hi(x) = 0 ,1 i p

gj(x) 0 ,1 j q

rappel de vocabulaire : les hi sont les contraintes dgalit (notes h(x) = 0) les gj sont les contraintes dingalit (notes g(x) 0) lensemble des contraintes est

C = {x Rn|hi(x) = 0 ,1 i p et gj(x) 0 ,1 j q}

ensemble des points admissibles ou ralisables

4 / 32 F. Rossi Rsultats thoriques

Consquences

les contraintes changent les conditions doptimalitexemple : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = 4 x2 y2 0 sur R2, on tudierait J = 2(x , y)T mais ici, le minimum vaut 4 et est atteint sur le cercle

x2 + y2 = 4 sur lequel J 6= 0

mais pas toujours : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = x2 + y2 4 0 le minimum est atteint en (0,0), avec J = 0

les contraintes doivent donc apparatre dans les conditionsdoptimalit

5 / 32 F. Rossi Rsultats thoriques

Consquences

les contraintes changent les conditions doptimalitexemple : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = 4 x2 y2 0 sur R2, on tudierait J = 2(x , y)T mais ici, le minimum vaut 4 et est atteint sur le cercle

x2 + y2 = 4 sur lequel J 6= 0mais pas toujours : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = x2 + y2 4 0 le minimum est atteint en (0,0), avec J = 0

les contraintes doivent donc apparatre dans les conditionsdoptimalit

5 / 32 F. Rossi Rsultats thoriques

Consquences

les contraintes changent les conditions doptimalitexemple : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = 4 x2 y2 0 sur R2, on tudierait J = 2(x , y)T mais ici, le minimum vaut 4 et est atteint sur le cercle

x2 + y2 = 4 sur lequel J 6= 0mais pas toujours : J(x , y) = x2 + y2 minimiser sous la contrainte

g(x , y) = x2 + y2 4 0 le minimum est atteint en (0,0), avec J = 0

les contraintes doivent donc apparatre dans les conditionsdoptimalit

5 / 32 F. Rossi Rsultats thoriques

Existence dun minimum

cas gnral : (P) : min J(x),x C Rn

on suppose : J continue et C ferm et non vide

alors : si :

C est born ou si J est coercitive

alors (P) admet au moins une solution

6 / 32 F. Rossi Rsultats thoriques

Existence et unicit

remarque : si

C ={

x Rn|hi(x) = 0 ,1 i p et gj(x) 0 ,1 j q}

avec des hi et gj continues, alors C est fermsi J est strictement convexe et C est convexe, alors (P)admet au plus une solutionproblme convexe : J est convexe les hi sont affines les gj sont convexes et donc C est convexe

7 / 32 F. Rossi Rsultats thoriques

Condition du premier ordre

si J est Gteaux-diffrentiable en x solution de (P) et si Cest convexe, alors :

x C, 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 C alors J(x) = 0

si J est convexe la condition est ncessaire et suffisante

8 / 32 F. Rossi Rsultats thoriques

galits et ingalits

Conditions ncessaires non qualifiescas particulier hi(x) = 0 et gj(x) 0 o tout est C1 (Jinclus)soit x une solution de (P), alors il existe = (1, . . . , p)et = (0,

1, . . . ,

q) tels que

(,) 6= 0 hi(x) = 0, 1 i p (admissibilit en galit) gj(x) 0, 1 j q (admissibilit en ingalit) j 0, 0 j q j gj(x

) = 0, 1 j q (conditions de complmentarit) et

0J(x) +p

i=1

i hi(x) +q

j=1

j gj(x) = 0

9 / 32 F. Rossi Rsultats thoriques

Qualification

condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

trs nombreuses variantes plus ou moins sophistiques

contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

rgularit de Mangasarian-Fromowitz

10 / 32 F. Rossi Rsultats thoriques

Qualification

condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

trs nombreuses variantes plus ou moins sophistiques

contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

rgularit de Mangasarian-Fromowitz

10 / 32 F. Rossi Rsultats thoriques

Qualification

condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

trs nombreuses variantes plus ou moins sophistiques

contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

rgularit de Mangasarian-Fromowitz

10 / 32 F. Rossi Rsultats thoriques

Conditions qualifiesConditions ncessaires qualifies du 1er ordre de KKT(Karush, Kuhn et Tucker)Hypothses : J, h et g C1 x solution de (P) x est rgulier pour g et h

Alors il existe = (1, . . . , p) et = (1, . . . ,

q) tels

que hi(x) = 0, 1 i p gj(x) 0, 1 j q j 0, 1 j q j gj(x

) = 0, 1 j q et

J(x) +p

i=1

i hi(x) +q

j=1

j gj(x) = 0

11 / 32 F. Rossi Rsultats thoriques

Cas convexe

si le problme (P) est convexe, les conditions de KKT sontncessaires et suffisantes en un point x rgulierremarque : le caractre suffisant ne ncessite pas largularitconditions de qualification plus simples (de Slater) : ilexiste au moins un point strictement admissible g(x) < 0

12 / 32 F. Rossi Rsultats thoriques

Lagrangien

le Lagrangien du problme (P) est la fonction

L(x,,) = J(x) +p

i=1

ihi(x) +q

j=1

jgj(x)

quand J, h et g sont C1 les conditions de KKT sexprimentpar xL(x,,) = 0les i et les j sont les multiplicateurs de Lagrangeassocis aux contraintes

13 / 32 F. Rossi Rsultats thoriques

Dualit

fonction duale de Lagrange

g(,) = infx

L(x,,)

g est toujours concavepour 0

g(,) infxC

J(x)

problme dual (Q) associ au problme primal (P)

maximiser sur Rp+q g(,)avec j 0 ,1 j q

saut de dualit : infxC J(x)max0 g(,)

14 / 32 F. Rossi Rsultats thoriques

Point sellesymtrisation du problme : (P) est quivalent

infx

sup,0

L(x,,)

le problme dual (Q) est

sup,0

infx

L(x,,)

point selle : minimal par rapport une variable, maximalpar 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 sellesymtrisation du problme : (P) est quivalent

infx

sup,0

L(x,,)

le problme dual (Q) est

sup,0

infx

L(x,,)

point selle : minimal par rapport une variable, maximalpar 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 unesolution de (P), (,) est une solution de (Q) et le sautde dualit est nulintrt : pour rsoudre le problme, on peut donc chercherun point selle du Lagrangien

remarque : un point selle du Lagrangien vrifie lesconditions de KKT (sans hypothse autre que J, h et g C1)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 unesolution de (P), (,) est une solution de (Q) et le sautde dualit est nulintrt : pour rsoudre le problme, on peut donc chercherun point selle du Lagrangienremarque : un point selle du Lagrangien vrifie lesconditions de KKT (sans hypothse autre que J, h et g C1)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 hi(x) et les gj(x) sont linairement indpendants pour

j I(x)Contraintes fortement actives :

I+(x) = {j | gj(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 C2 x solution de (P) et fortement rgulier

alors il existe = (1, . . . , p) et = (1, . . . ,

q) tels

que les conditions de KKT sont vrifies et pour tout d vrifiant :

hi(x), d = 0 pour 1 i p gj(x), d = 0 pour j I+(x) gj(x), d 0 pour I(x) \ I+(x)

on a 2xxL(x,

,)d ,d 0

18 / 32 F. Rossi Rsultats thoriques

Conditions suffisantes

Hypothses : J, h et g C2 (x,,) vrifie les conditions KKT

si la matrice 2xxL(x,,) est dfinie positive sur{d Rn | hi(x),d = 0, 1 i ,p

etgj(x),d

= 0, j I+(x)

}alors x est un minimum local de J sur C

19 / 32 F. Rossi Rsultats thoriques

Plan

Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

AlgorithmesIntroductionGradientPnalisationDualit

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 problmessans 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 Rn pour tout x alors

C(x) = arg minyCx y2

existe et est uniqueproprits : 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) 0y 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 fermalgorithme :

1. point initial x02. pour k 1 croissant

2.1 calculer yk+1 = xk kJ(xk )2.2 puis xk+1 = C(yk+1)2.3 tester la convergence et quitter la boucle le cas chant (par

ex. xk+1 xk < )

formulation simple mais mise en oeuvre potentiellementdlicate : si C est simple (par ex., li xi ui ), pas de problme sinon le calcul de C(yk+1) est un problme doptimisation

sous contraintes

24 / 32 F. Rossi Algorithmes

Gradient projet

minimisation de J sur C convexe fermalgorithme :

1. point initial x02. pour k 1 croissant

2.1 calculer yk+1 = xk kJ(xk )2.2 puis xk+1 = C(yk+1)2.3 tester la convergence et quitter la boucle le cas chant (par

ex. xk+1 xk < )formulation simple mais mise en oeuvre potentiellementdlicate : si C est simple (par ex., li xi ui ), pas de problme sinon le calcul de C(yk+1) est un problme doptimisation

sous contraintes

24 / 32 F. Rossi Algorithmes

Convergence

si J est C1, -convexe et de drive M-lipschitzienneet si k [1, 2] avec 0 < 1 < 2 < 2M2alors 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

xk+1 x2 (xk kJ(xk )) (x kJ(x))2

ce qui nous ramne au cas sans projection

25 / 32 F. Rossi Algorithmes

Pnalisation

ide principale : remplacer un problme avec contraintespar un problme sans contrainte dont la fonction objectif dcourage les points non admissiblessolution nave : on dfinit

(x) ={

+ x 6 C0 x C

alors trouver arg minxC J(x) est quivalent trouverarg minxRn J(x) + (x)

solutions ralistes : utiliser une fonction rgulire (C1 aumoins) petite sur C et grande en dehors

26 / 32 F. Rossi Algorithmes

Mthodes de point extrieur

vrifie : est continue sur Rn (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 (Pr ) pour r > 0dfinis par

minxRn

(J(x) + r(x))

mthodes de point extrieur : on ne peut pas garantirxr C

27 / 32 F. Rossi Algorithmes

Mthodes de point intrieurmme principe, mais avec des points lintrieur de Cpour les contraintes dingalit seulement est une barrire et vrifie : est continue sur

C

x 6 C (x) =pour les contraintes g(x) 0, on prend gnralement

q

j=1

log(gj(x))

comme pour les mthodes de point extrieur, on considreles problmes (Pr ) pour r > 0 dfinis par

minxRn

(J(x) + r(x))

ici, on a toujours xr C

28 / 32 F. Rossi Algorithmes

Pnalisation

minimisation de J sur C convexe fermalgorithme (pour une suite (rk )k croissante) :

1. point initial x02. pour k 1 croissant

2.1 rsoudre le problme (Prk )

minxRn

(J(x) + rk(x))

en partant de la solution xk12.2 tester la qualit du point obtenu xk et quitter la boucle le cas

chant

fonctionne trs bien en pratique pour le cas du pointintrieur (on rsout (Prk ) par une mthode de(quasi)Newton avec contraintes dgalits)lefficacit vient du redmarrage depuis un bon candidat

29 / 32 F. Rossi Algorithmes

Pnalisation

minimisation de J sur C convexe fermalgorithme (pour une suite (rk )k croissante) :

1. point initial x02. pour k 1 croissant

2.1 rsoudre le problme (Prk )

minxRn

(J(x) + rk(x))

en partant de la solution xk12.2 tester la qualit du point obtenu xk et quitter la boucle le cas

chant

fonctionne trs bien en pratique pour le cas du pointintrieur (on rsout (Prk ) par une mthode de(quasi)Newton avec contraintes dgalits)lefficacit vient du redmarrage depuis un bon candidat

29 / 32 F. Rossi Algorithmes

Convergence

on suppose J continue et coercitive, et C ferm et non videon considre une mthode de point extrieurrsultat : pour tout r > 0, (Pr ) possde au moins une solution toute famille (xr )r>0 de solutions est borne les valeurs dadhrence de toute famille (xr )r>0 de

solutions sont des solutions de (P)

preuve (x est une solution de (P)) : Jr (x) = J(x) + r(x) est coercitive et continue xr solution de (Pr ), J(xr ) Jr (xr ) Jr (x) = J(x), donc

(xr )r>0 est borne comme (xr ) 1r (J(x

) J(xr )), on a limr+ (xr ) = 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 videon considre une mthode de point extrieurrsultat : pour tout r > 0, (Pr ) possde au moins une solution toute famille (xr )r>0 de solutions est borne les valeurs dadhrence de toute famille (xr )r>0 de

solutions sont des solutions de (P)preuve (x est une solution de (P)) : Jr (x) = J(x) + r(x) est coercitive et continue xr solution de (Pr ), J(xr ) Jr (xr ) Jr (x) = J(x), donc

(xr )r>0 est borne comme (xr ) 1r (J(x

) J(xr )), on a limr+ (xr ) = 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 Lagrangienalgorithme (paramtre > 0) :

1. valeurs initiales des multiplicateurs 1,12. pour k 1 croissant

2.1 trouver xk solution du problme (sans contrainte)

minxRn

L(x,k ,k )

2.2 mettre jour (k ,k ) par

k+1i = ki + hi(xk )

k+1j = max(0, kj + gj(xk ))

2.3 tester la convergence et quitter la boucle le cas chant (parex. xk+1 xk < )

31 / 32 F. Rossi Algorithmes

Algorithme dUzawa

on peut montrer que lalgorithme dUzawa est un gradientprojet 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 C1, -convexe, h affine et g convexe et Mg

lipschitzienne et si L possde un point selle (x,,) alors lalgorithme converge vers x pour tout choix de

dans ]0, 2M2g +M2h[

32 / 32 F. Rossi Algorithmes

Rsultats thoriquesIntroductionExistence et unicitConditions d'optimalitDualitSecond ordre

AlgorithmesIntroductionGradientPnalisationDualit