[PDF] 3.5 Algorithmes doptimisation sous contraintes - 3.5.1 Méthodes de

View - Download 3.5 Algorithmes doptimisation sous contraintes - 3.5.1 Méthodes de

Previous PDF

Next PDF

3.5. ALGORITHMES D"OPTIMISATION SOUS CONTRAINTES CHAPITRE 3. OPTIMISATION

3.5 Algorithmes d"optimisation sous contraintes

3.5.1 Méthodes de gradient avec projection

On rappelle le résultat suivant de projection sur un convexefermé :

Proposition 3.40(Projection sur un convexe fermé).SoitEun espace de Hilbert, muni d"une norme?.?induite

par un produit scalaire(.,.), et soitKun convexe fermé non vide deE. Alors, toutx?E, il existe un unique

x

Soientx?Eetx0?K. On a également :

x

0=pK(x)si et seulement si(x-x0,x0-y)≥0,?y?K.

Dans le cadre des algorithmes de minimisation avec contraintes que nous allons développer maintenant, nous

considèreronsE= IRn, f?C1(IRn,IR)une fonction convexe, etKfermé convexe non vide. On cherche à

calculer une solution approchée de¯x, solution du problème (3.48).

Algorithmedu gradientàpas fixe avecprojectionsurK(GPFK)Soitρ >0donné,onconsidèrel"algorithme

suivant :

Algorithme (GPFK)

Initialisation :x0?K

Itération :

x kconnuxk+1=pK(xk-ρ?f(xk)) oùpKest la projection surKdéfinie par la proposition 3.40.

Lemme 3.41.Soit(xk)kconstruite par l"algorithme (GPFK). On suppose quexk→xquandn+∞. Alorsxest

solution de(3.48).

DÉMONSTRATION- SoitpK: IRn→K?IRnla projection surKdéfinie par la proposition 3.40. AlorspKest

continue. Donc si x k→xquandn→+∞alorsx=pK(x-ρ?f(x))etx?K(carxk?KetKest fermé). La caractérisation depK(x-ρ?f(x))donnée dans la proposition 3.40 donne alors : Orfest convexe doncf(y)≥f(x) +?f(x)(y-x)pour touty?K, et doncf(y)≥f(x)pour touty?K, ce qui termine la démonstration. Théorème 3.42(Convergence de l"algorithme GPFK). Soitf?C1(IRn,IR), etKconvexe fermé non vide. On suppose que :

1. il existeα >0tel que(?f(x)- ?f(y)|x-y)≥α|x-y|2, pour tout(x,y)?IRn×IRn,

alors :

1. il existe un unique élément¯x?Ksolution de(3.48),

2. si0< ρ <2α

M2, la suite(xk)définie par l"algorithme(GPFK)converge vers¯xlorsquen→+∞.

Analyse numérique I, télé-enseignement, L3271Université d"Aix-Marseille, R. Herbin, 16 septembre 2016

3.5. ALGORITHMES D"OPTIMISATION SOUS CONTRAINTES CHAPITRE 3. OPTIMISATION

DÉMONSTRATION-

1. La condition 1. donne quefest strictement convexe et quef(x)→+∞quand|x| →+∞. CommeKest convexe

fermé non vide, il existe donc un unique¯xsolution de (3.48).

2. On pose, pourx?IRn,h(x) =pK(x-ρ?f(x)). On a doncxk+1=h(xk).Pour montrer que la suite(xk)k?IN

converge, il suffit donc de montrer quehest strictement contractante dès que

0< ρ <2α

M2.(3.61)

Grâce au lemme 3.43 démontré plus loin, on sait quepKest contractante. Orhest définie par :

h(x) =pK(¯h(x))où¯h(x) =x-ρ?f(x).

On a déjà vu que

¯hest strictement contractante si la condition (3.61) est vérifiée (voir théorème 3.19 page 226), et plus

précisément :

On en déduit que :

L"applicationhest donc strictement contractante dès que0<2α M2. La suite(xk)k?INconverge donc bien versx= ¯x

Lemme 3.43(Propriété de contraction de la projection orthogonale).SoitEun espace de Hilbert,? · ?la norme

et(·,·)le produit scalaire,Kun convexe fermé non vide deEetpKla projection orthogonale surKdéfinie par

DÉMONSTRATION- CommeEest un espace de Hilbert,

?pK(x)-pK(y)?2= (pK(x)-pK(y)|pK(x)-pK(y)). On a donc?pK(x)-pK(y)?2= (pK(x)-x+x-y+y-pK(y)|pK(x)-pK(y)) = (pK(x)-x|pK(x)-pK(y))E+ (x-y|pK(x)-pK(y))+ (y-pK(y)|pK(x)-pK(y)). et donc, grâce à l"inégalité de Cauchy-Schwarz, ce qui permet de conclure. Algorithme du gradient à pas optimal avec projection surK(GPOK) L"algorithme du gradient à pas optimal avec projection surKs"écrit :

Initialisationx0?K

Itérationxkconnu

w k=-?f(xk);calculerαkoptimal dans la directionwk x k+1=pK(xk+αkw(k))

La démonstration de convergencede cet algorithme se déduitde celle de l"algorithme à pas fixe.

Remarque 3.44.On pourrait aussi utiliser un algorithme de type Quasi-Newton avec projection surK. Les algorithmes de projection sont simples à décrire, mais ils soulèvent deux questions :

1. Comment calcule-t-onpK?

2. Que faire siKn"est pas convexe?

Analyse numérique I, télé-enseignement, L3272Université d"Aix-Marseille, R. Herbin, 16 septembre 2016

3.5. ALGORITHMES D"OPTIMISATION SOUS CONTRAINTES CHAPITRE 3. OPTIMISATION

On peut donner une réponse à la première question dans les cassimples : Cas 1.On suppose ici queK=C+={x?IRn, x= (x1,...,xk)txi≥0?i}. Siy?IRny= (y1...yn)t,on peut montrer (exercice 132 page 267) que (pK(y))i=y+ i= max(yi,0),?i? {1,...,n} K=? i=1,n[αi,βi], alors (pK(y))i= max(αi,min(yi,βi)),?i= 1,...,n

Dansle cas d"unconvexeKplus"compliqué",oudansle cas oùKn"estpas convexe,onpeututiliser desméthodes

de dualité introduites dans le paragraphe suivant.

3.5.2 Méthodes de dualité

Supposons que les hypothèses suivantes sont vérifiées : ?f?C1(IRn,IR), g i?C1(IRn,IR),

On définit un problème "primal" comme étant le problème de minimisation d"origine, c"est-à-dire

?¯x?K, On définit le "lagrangien" comme étant la fonctionLdéfinie deIRn×IRpdansIRpar :

L(x,λ) =f(x) +λ·g(x) =f(x) +p?

i=1λ igi(x),(3.64) avecg(x) = (g1(x),...,gp(x))tetλ= (λ1,...,λp)t.

On noteC+l"ensemble défini par

C +={λ?IRp, λ= (λ1,...,λp)t,λi≥0pour touti= 1,...,p}.

Remarque 3.45.Le théorème de Kuhn-Tucker entraîne que si¯xest solution du problème primal(3.63)alors il

existeλ?C+tel queD1L(¯x,λ) = 0(c"est-à-direDf(¯x) +λ·Dg(¯x) = 0) etλ·g(¯x) = 0.

On définit alors l"applicationMdeIRpdansIRpar : M(λ) = infx?IRnL(x,λ),pour toutλ?IRp.(3.65)

On peut donc remarquer queM(λ)réalise le minimum (enx) du problème sans contrainte, qui s"écrit, pour

λ?IRpfixé :

?x?IRn

Analyse numérique I, télé-enseignement, L3273Université d"Aix-Marseille, R. Herbin, 16 septembre 2016

3.5. ALGORITHMES D"OPTIMISATION SOUS CONTRAINTES CHAPITRE 3. OPTIMISATION

Lemme 3.46.L"applicationMdeIRpdansIRdéfinie par(3.65)est concave (ou encore l"application -Mest

convexe), c"est-à-dire que pour tousλ,μ?IRpet pour toutt?]0,1[on aM(tλ+ (1-t)μ)≥tM(λ) + (1-

t)M(u)

DÉMONSTRATION- Soitλ,μ?IRpett?]0,1[; on veut montrer queM(tλ+ (1-t)μ)≥tM(λ) + (1-t)M(μ).

Soitx?IRn,alors :

L(x,tλ+ (1-t)μ) =f(x) + (tλ+ (1-t)μ)g(x) =tf(x) + (1-t)f(x) + (tλ+ (1-t)μ)g(x).

On a doncL(x,tλ+ (1-t)μ) =tL(x,λ) + (1-t)L(x,μ).Par définition deM, on en déduit que pour toutx?IRn,

L(x,tλ+ (1-t)μ)≥tM(λ) + (1-t)M(μ)

Or, toujours par définition deM,

M(tλ+ (1-t)μ) = inf

x?IRnL(x,tλ+ (1-t)μ)≥tM(λ) + (1-t)M(μ). On considère maintenant le problème d"optimisation dit "dual" suivant : ?μ?C+,

M(μ)≥M(λ)?λ?C+.(3.67)

Définition 3.47.SoitL: IRn×IRp→IRet(x,μ)?IRn×C+. On dit que(x,μ)est un point selledeLsur

IR n×C+si

Proposition 3.48.Sous les hypothèses(3.62), soitLdéfinie parL(x,λ) =f(x) +λg(x)et(¯x,μ)?IRn×C+

un point selle deLsurIRn×C+. alors

1.¯xest solution du problème(3.63),

2.μest solution de(3.67),

3.¯xest solution du problème(3.66)avecλ=μ.

On admettra cette proposition.

Réciproquement, on peut montrer que (sous des hypothèses convenables surfetg), siμest solution de (3.67), et

si¯xsolution de (3.66) avecλ=μ, alors(¯x,μ)est un point selle deL, et donc¯xest solution de (3.63).

De ces résultats découlel"idéede basedes méthodesdedualité : onchercheμsolutionde(3.67). Onobtientensuite

une solution¯xdu problème (3.63), en cherchant¯xcomme solution du problème (3.66) avecλ=μ(qui est un

problème de minimisation sans contraintes). La recherche de la solutionμdu problème dual (3.67) peut se faire

par exemple par l"algorithme très classique d"Uzawa, que nous décrivons maintenant.

Algorithme d"UzawaL"algorithme d"Uzawa consiste à utiliser l"algorithme du gradient à pas fixe avec pro-

jection (qu"on a appelé "GPFK", voir page 271) pour résoudrede manière itérative le problème dual (3.67). On

cherche doncμ?C+tel queM(μ)≥M(λ)pour toutλ?C+. On se donneρ >0,et on notepC+la projection

sur le convexeC+(voir proposition 3.40 page 271). L"algorithme (GPFK) pourla recherche deμs"écrit donc :

Initialisation :μ0?C+

Itération :μk+1=pC+(μk+ρ?M(μk))

Pour définir complètement l"algorithme d"Uzawa, il reste à préciser les points suivants :

Analyse numérique I, télé-enseignement, L3274Université d"Aix-Marseille, R. Herbin, 16 septembre 2016

3.5. ALGORITHMES D"OPTIMISATION SOUS CONTRAINTES CHAPITRE 3. OPTIMISATION

1. Calcul de?M(μk),

2. calcul depC+(λ)pourλdansIRn.

On peut également s"intéresser aux propriétés de convergencede l"algorithme.

La réponse au point 2 est simple (voir exercice 132 page 267) :pourλ?IRp, on calculepC+(λ) =γavec

γ= (γ1,...,γp)ten posantγi= max(0,λi)pouri= 1,...,p, oùλ= (λ1,...,λp)t. La réponse au point 1. est une conséquence de la proposition suivante (qu"on admettra ici) :

Proposition 3.49.Sous les hypothèses(3.62), on suppose que pour toutλ?IRn, le problème(3.66)admet une

solution unique, notéexλet on suppose que l"application définie deIRpdansIRnparλ?→xλest différentiable.

AlorsM(λ) =L(xλ,λ),Mest différentiable enλpour toutλ, et?M(λ) =g(xλ).

En conséquence, pour calculer?M(λ), on est ramené à chercherxλsolution du problème de minimisation sans

contrainte (3.66). On peut dont maintenant donner le détailde l"itération générale de l"algorithme d"Uzawa :

Itération de l"algorithme d"Uzawa.Soitμk?C+connu;

1. On cherchexk?IRnsolution de?xk?IRn,

2. On calcule?M(μk) =g(xk)

3. μk+1=μk+ρ?M(μk) =μk+ρg(xk) = ((μk+1)1,...,(μk+1)p)t

4.μk+1=pC+(

μk+1), c"est-à-direμk+1= ((μk+1)1,...,(μk+1)p)tavec(μk+1)i= max(0,(μk+1)i)pour touti= 1,...,p. On a alors le résultat suivant de convergence de l"algorithme :

Proposition 3.50(Convergencede l"algorithme d"Uzawa).Sous les hypothèses(3.62), on suppose de plus que :

1. il existeα >0tel que(?f(x)- ?f(y))·(x-y)≥α|x-y|2pour tout(x,y)?(IRn)2,

Alors si0< ρ <2α

Mf2, la suite((xk,μk))k?IRn×C+donnée par l"algorithme d"Uzawa vérifie :

1.xk→¯xquandk→+∞,où¯xest la solution du problème(3.63),

2.(μk)k?INest bornée.

Remarque 3.51(Sur l"algorithme d"Uzawa).

1. L"algorithmeest très efficacesi les contraintessont affines: (i.e. sigi(x) =αi·x+βipourtouti= 1,...,p,

avecαi?IRnetβi?IR).

2. Pour avoir l"hypothèse 3 du théorème, il suffit que les fonctionsgisoient convexes. (On a dans ce cas

existence et unicité de la solutionxλdu problème(3.66)et existence et unicité de la solution¯xdu problème

(3.63).)

Analyse numérique I, télé-enseignement, L3275Université d"Aix-Marseille, R. Herbin, 16 septembre 2016

quotesdbs_dbs47.pdfusesText_47

[PDF] optimisation synonyme

[PDF] optimiser la recette

[PDF] Optimiser un cout de fabrication

[PDF] optimiser une recette

[PDF] Optimiser une recette (fonction carré Problèmes du 2nd degré)

[PDF] Optimiser une recette (transmath 2nde chapitre foction carré Problémes du 2nd degré ex 101 P 86)

[PDF] optimiser une recette d'un cinéma ( statistique, équation)

[PDF] optimiser une recette maths seconde

[PDF] Optimum de Pareto

[PDF] optimum de pareto exercice corrigé

[PDF] optimum de pareto graphique

[PDF] option art plastique bac 2017 candidat libre

[PDF] option art plastique bac candidat libre

[PDF] Option au bac

[PDF] option audiovisuel bac