[PDF] MAT 2410: Optimisation Chapitre 4. Optimisation différentiable

View - Download MAT 2410: Optimisation

Previous PDF

Next PDF

MAT 2410:

Optimisation

Robert Guénette

Département de Mathématiques et de Statistique

Chapitre 4

Optimisation différentiable avec contraintes

Références

Condition d"optimalité: cas convexe

Dualité

Lagrangien et point de selle

Fonction indicatrice

ContraintesBx=c

ContraintesBxc

Cône des directions admissibles

Méthodes numériques

contraintes d"égalité

Références:

Notes de cours: chapitre 4, sections 4.1 et 4.2.

Livre de M. Delfour: chapitre 4.

Problèmes de minimisation avec contraintes

Soitf:U!Rune fonction numérique définie sur un ensemble deRn. Il s"agit de déterminer le pointa2Uqui vérifie f(a) =minx2Uf(x) En généralUest définie par l"intersection d"une famille de contraintes de la forme: I g(x)0, I h(x) =0, I

BxcoùBest une matrice etcun vecteur,

I

Cx=doùCest une matrice etdun vecteur,

I lbxuboù leslbetubsont des bornes sur la solutionx, i.e.lbixiubi8i

Problèmes avec contraintes (suite)

Le type de problème que nous allons considérer par la suite, s"écrira de manière plus compact min g(x)0 h(x) =0f(x) oùg= (g1;g2;:::;gm)sont les contraintes d"inégalité (en incluant les bornes sur x) eth= (h1;h2;:::;hp)les contraintes d"égalité. Cette écriture inclut aussi les contraintes linéaires.

Remarques:

I U=fxjg(x)0 eth(x) =0gn"est pas convexe en général. I Si lesgisont convexes et leshjlinéaires, alorsUest convexe. Condition d"optimalité du premier ordre: cas convexe Théorème:Condition nécessaire d"optimalité du premier ordre Soitf:U!Rune fonction numérique de classeC1définie sur un ensembleconvexeferméURn. Sia2Uest un point minimisant def, f(a) =minx2Uf(x); alors (rf(a);xa)08x2U

Preuve:a;x2U=)a+t(xa)2UcarUest convexe pour

0t1. Par hypothèse, on a que

f(a+t(xa))f(a)0 lim t!0f(a+t(xa))f(a)t 0 (rf(a);xa))0

Condition d"optimalité (suite)

Remarques:

I Géométriquement parlant, la condition(rf(a);xa)0 s"interprète en disant que l"angleentre le vecteurrf(a)etxa est dans l"intervalle =2=2: I SiU=Rn, on retrouve la condition d"optimalité sans contrainte: rf(a) =0. I Si le point minimisantase trouve à l"intérieur deU, on a aussi rf(a) =0. En effet il suffit de prendrex=ar ypourrsuffisamment petit et y2Rnquelconque. On introduit ce point dans la condition d"optimalité(rf(a);xa)0. Ceci implique (rf(a);y)0=)(rf(a);y) =08y=) rf(a) =0:

Condition d"optimalité cas convexe (suite)

Théorème:Condition nécessaire et suffisante d"optimalité du premier ordre Soitf:U!Rune fonction numérique convexe de classeC1définie sur un ensemble convexe ferméURn.

On a la caractérisation suivante:

a2Uest un point minimisant defsi et seulement si (rf(a);xa)08x2U

Preuve:Il suffit de montrer(=

Par le critère de convexité du premier ordre, on a f(x)f(a) + (rf(a);xa)8x2U:

Mais(rf(a);xa)0. On obtient

f(x)f(a) + (rf(a);xa)f(a)8x2U:

Choix particuliers deU

I Uest un sous-espace linéaire deRn. Dans ce cas, la condition d"optimalité s"écrit sous la forme (rf(a);y) =08y2U:

C"est-à-dire querf(a)2U?.

I Uest un sous-espace affine deRn, i.e.U=x0+WavecWun sous-espace linéaire. La condition d"optimalité s"écrit sous la forme (rf(a);w) =08w2W: ourf(a)2W?ou encore (rf(a);xa) =08x2U:

Exemple

Considérons le problème de calculer la projection du point(2;2)sur un polygone convexe. Le problème s"écrit sous la forme min x

1+2x23

x

10;x20(x12)2+ (x22)2

Ce problème admet une solution unique.

Selon le dessin, le gradient doit être dans

la direction du vecteur normal à la droitex1+2x2=3. (x12;x22) =t(1;2) pourt0. On trouve t=3=5=)x1=7=5;x2=4=5:

Orthogonalité

SoitEun sous-espace linéaire deRn. On définit le sous-espace orthogonal par E ?=fy2Rnj(y;x) =08x2Eg

Propriétés:

I

E?est un sous-espace linéaire deRn,

I dimE+dimE?=n, I

E??=E,

I

EF=)F?E?,

I SiB:Rn!Rmest une application linéaire (matrice), on a (Ker B)?=ImBt oùKer B=fxjBx=0g. Rappel: le rang deBest égal àrg(B) =dim(ImB)et on a rg(B) =rg(Bt) =dim(ImBt).

Cône dual

Notion de cône:CRnest un cône de sommet 0 si x2C; 0=)x2C

Un cône convexe est caractérisé par

I

8x;y2C=)x+y2C

I

80;8x2C=)x2C

Exemple important de cône convexe:U=fxjBx0goùBest une matrice de formatnm. Cône dual:soitURnquelconque. On définit le cône dual par U =fyj(y;x)08x2Ug

Propriétés:

I

Uest toujours un cône convexe fermé.

I

UV=)VU

I

U=UsiUest un cône convexe fermé.

Lagrangien et point de selle

SoientARnetBRmdeux ensembles non vide et

L:AB!R

une fonction appellée lagrangien. Définition:Un point(x;y)2ABest un point de selle du lagrangien Lsi

L(x;y)L(x;y)L(x;y)8x2A;8y2B:

Exemple:Le point(0;0)est un point de selle de la fonction

L(x;y) =x2y2avecA=B=Rcar

L(0;y) =y20=L(0;0)x2=L(x;0)8x;y2R:

Théorème du min-max

Théorème:Si(x;y)est un point de selle deL, alors max y2Bminx2AL(x;y) =minx2Amaxy2BL(x;y) =L(x;y) Autrement dit, on peut inverser l"ordre du min et du max.

Démonstration:Montrons en premier que

max y2Bminx2AL(x;y)minx2Amaxy2BL(x;y):

En effet, on a que

min x2AL(x;y)L(x;y)maxy2BL(x;y) Le membre de gauche est une fonction de y seulement. De même, pour le membre de droite qui est une fonction de x uniquement. Ceci implique max y2Bminx2AL(x;y)maxy2BL(x;y);8x2A et, en prenant le minimum par rapport àx, max y2Bminx2AL(x;y)minx2Amaxy2BL(x;y); d"où le résultat.

Théorème du min-max (suite)

En deuxième, montrons que

min x2Amaxy2BL(x;y)L(x;y): En effet, selon la définition du point de selle, on a max y2BL(x;y) =L(x;y) =)L(x;y)minx2Amaxy2BL(x;y):

De même, on a

min x2AL(x;y) =L(x;y) =)L(x;y)maxy2Bminx2AL(x;y):

En recollant les morceaux, on obtient

d"où le résultat final.

Condition d"optimalité du lagrangien

SoientU;VRndeux sous-ensembles convexes et fermés. On fera les hypothèses suivantes: I

Pouryfixé, la fonctionL:x!L(x;y)est convexe.

I Pourxfixé, la fonctionL:y!L(x;y)est concave (Lest convexe). Au point-selle(x;y)du lagrangienL, la condition d"optimalité du minimumL(x;y)L(x;y)8x2Us"écrit @L@x(x;y);xx)08x2U De même, la condition d"optimalité du maximum

L(x;y)L(x;y)8y2Vs"écrit

@L@y(x;y);yy)08y2V où @L@xest le gradient de la fonctionL(x;y)pouryfixé.

Fonction indicatrice

SoitKRnun sous-ensemble quelconque et non vide.

Definition:La fonction indicatrice de l"ensembleKest définie par I

K(x) =0 six2K,

1sinon.

La fonction indicatrice sert à enlever les contraintes. Pour un problème de minimisation, on a évidemment la relation min x2Kf(x) =minxf(x) +IK(x) Pour un problème de maximisation, on a plutôt max x2Kf(x) =maxxf(x)IK(x)

Contraintes de la forme:Bx=c

Appliquons la dualité lagrangienne au problème (primal) min

Bx=cf(x)

oùBest une matrice de formatmnetc2Rm. Ce problème a un sens seulement sic2ImBou encore que le rang deBest maximal (ImB=Rm). Lemme:La fonction indicatrice deK=fx2RnjBx=cgest donnée par I

K(x) =max2Rm(;Bxc)

Démonstration:en effet, siBx6=c, on peut prendre =r(Bxc) =)(;Bxc) =rkBxck2! 1sir! 1

Le maximum sera1.

Au contraire, siBx=c, on a que(;Bxc) =082Rmde

maximum 0.

Contraintes de la forme:Bx=c(suite)

Par conséquent, on peut écrire

min

Bx=cf(x) =minxf(x) +IK(x) =minxf(x) +max2Rm(;Bxc)

Ceci suggère la fonction lagrangienne

L(x;) =f(x) + (;Bxc)8x2Rn;82Rm:

ce qui transforme le problème primal en un problème de point-selle min

Bx=cf(x) =minx2Rnmax2RmL(x;)

La condition d"optimalité du lagrangien sera

8>< :@L@x=0() rf(x) +Bt=0 @L@ =0()Bx=c

Point de vue des cônes duaux:Bx=c

La condition d"optimalité du problèmef(a) =minBx=cf(x)s"écrit (rf(a);xa)08x2U=fxjBx=cg: Sachant quec2ImB, on a queU=x0+Ker BoùBx0=c. Ce qui implique queUest un sous-espace affine et dans ce cas, la condition d"optimalité correspond à rf(a)2(Ker B)?=ImBt=) 92Rmrf(a) =Bt: Ceci fournit les conditions en disant queaetsont solutions du système rf(x) +Bt=0; Bx=c: Ce sont les mêmes conditions que celles obtenues par la méthode de

Lagrange.

Contraintes de la forme:Bxc

Appliquons la dualité lagrangienne au problème (primal) min

Bxcf(x)

oùBest une matrice de formatmnetc2Rm. Lemme:La fonction indicatrice deK=fx2RnjBxcgest donnée par I

K(x) =max0(;Bxc)

Démonstration:en effet, siBx>c, on peut prendre =r(Bxc)0=)(;Bxc) =rkBxck2! 1sir! 1:

Le maximum sera1.

Au contraire, siBxc, on a que(;Bxc)080

carBxc0. Donc le maximum sera 0.

Contraintes de la forme:Bxc(suite)

Par conséquent, on peut écrire

min

Bxcf(x) =minxf(x) +IK(x) =minxf(x) +max0(;Bxc)

Ceci suggère la fonction lagrangienne

L(x;) =f(x) + (;Bxc)8x2Rn;80 et2Rm:

ce qui transforme le problème primal en un problème de point-selle min

Bxcf(x) =minx2Rnmax0L(x;)

Contraintes de la forme:Bxc(suite)

La condition d"optimalité du lagrangien sera

I (@L@x;xx)08x2Rnce qui donne @L@x=0() rf(x) +Bt=0 I (@L@ ;)080 . Etant donné quef0gforme un cône convexe, on obtient les conditions suivantes @L@ ;) = (Bxc;)080=)Bxc0()Bxc @L@ ;) =0()(Bxc;) =0

Conditions KKT pour les contraintes:Bxc

A partir des conditions d"optimalité du lagrangienL(x;), on peut écrire les conditions dites de Karush-Kuhn-Tucker (KKT) pour le problème min

Bxcf(x)

Observons que(Bxc;) =0 avec0 signifie quei(Bxc)i=0 pour tous lesi=1;:::;m.

Les conditions KKT s"écrivent sous la forme:

8>>>>><

>>>>:rf(x) +Bt=0; i0;8i=1;:::;m; (Bx)ici;8i=1;:::;m; i(Bxc)i;=08i=1;:::;m:

Point de vue des cônes duaux:Bxc

Le problèmef(a) =minBxcf(x)est équivalent à min

Bxcf(x)

De nouveau, on fait l"hypothèse quec2ImBdonc il existex0tel que Bx

0=c. Ceci implique

U=fxjBxcg=fxj Bx cg

=fxj B(xx0)0g=x0+fBx0g=x0+W oùW=fBx0gest le cône positif. La condition d"optimalité du problème s"écrit (rf(a);xa)08x2U=)(rf(a);y)08y2W; autrement ditrf(a)2W. MaisW=Bt+avec+=f0g. Ceci montre l"existence du multiplicateurvérifiantrf(a) +Bt=0.

Point de vue des cônes duaux: (suite)

Mais il y a une autre condition que l"on peut tirer de la condition (rf(a);xa)0. Il s"agit de la condition (rf(a);ax0) =0=)(Bt;ax0) =0=)(;BaBx0) = (;Bac) =0: En effet, il suffit de prendrex=x0etx=x0+2(ax0)dans le condition ci-dessus. En combinant toutes les conditions ci-dessus, on obtient exactement le même système KKT que doit vérifier la solutionaet le multiplicateur

8>>>>><

>>>>:rf(x) +Bt=0; i0;8i=1;:::;m; (Bx)ici;8i=1;:::;m; i(Bxc)i=0;8i=1;:::;m:

Cas général: contraintesg(x) =0

Appliquons la méthode de Lagrange au problème min g(x)=0f(x) oùg= (g1;g2;:::;gm)désignemcontraintes scalaires. En général, l"ensemble des contraintes n"est pas convexe.

On prend la fonction lagrangienne

L(x;) =f(x) + (;g(x)) =f(x) +mX

i=1 igi(x)8x2Rn;82Rm: Ceci transforme le problème primal en un problème de point-selle min g(x)=0f(x) =minx2Rnmax2RmL(x;)

La condition d"optimalité du lagrangien sera

8>>< >:@L@x=0() rf(x) +mX i=1 irgi(x) =0; @L@=0()gi(x) =0;8i=1;:::;m: Point de vue des cônes duaux: cas général

Cône des directions admissiblesCU(x):

SoitURnun sous-ensemble fermé. Fixons un pointx2U. On dira queh2CU(x)est direction admissible s"il existe une courbex(t)2U définie localement pour des valeurs positives det0 et passant par le pointx=x(0)de sorte que dxdt (0) =lim t!0 t>0x(t)xt =h

Propriétés deCU(x):

I CU(x)est un cône fermé de sommet 0 (pas nécessairement convexe) I

SiUest convexe,CU(x)est un cône convexe et

C

U(x) =la fermeture def(yx)jy2U;0g

Condition d"optimalité du premier ordre: cas général Théorème:Condition nécessaire d"optimalité du premier ordre Soitf:U!Rune fonction numérique de classeC1définie sur un ensemble ferméURn. Sia2Uest un point minimisant def, f(a) =minx2Uf(x); alors

8h2CU(a) =)(rf(a);h)0() rf(a)2CU(a)

Preuve:h2CU(a) =) 9x(t)2Utel quex(0) =a;dxdt

(0) =h.

On a que

f(x(t))f(a)0 =)f(x(t))f(x(0))t 08t>0 =)limt!0f(x(t))f(x(0))t 0 (rf(a);dxdt(0))0=)(rf(a);h)0() rf(a)2CU(a)

Contraintes d"égalité

Soientg1;g2;:::;gmm fonctions numériques de classeC1. On pose

U=fx2Rnjg1(x) =g2(x) ==gm(x) =0g

En généralUn"est pas convexe mais toujours fermé. Il est commode d"introduire l"application g:Rn!Rm x!(g1(x);g2(x);:::;gm(x)) Définition:La matrice jacobienne au pointxest définie par (Dg(x))ij=@gi@xj(x) qui est de formatmn. Définition:Un pointxest dit régulier sirg(Dg(x)) =m. Théorème:Sixest un point régulier deg, alors le cône des directions admissibles est donné par C

U(x) =Ker Dg(x)

Contraintes d"égalité (suite)

Appliquons ce résultat au problème

f(a) =ming(x)=0f(x) oùg= (g1;g2;:::;gm)désignemcontraintes scalaires. Condition nécessaire d"optimalité du premier ordre est

8h2CU(a) (rf(a);h)0() rf(a)2CU(a)

OrCU(a) = (Ker Dg(a))= (Ker Dg(x))?=Im(Dg(a))t. On obtient ainsi rf(a)2Im(Dg(a))t

Autrement dit, il existe2Rmtel que

rf(a) +mX i=1 irgi(a) =0:

Contraintes d"égalité (suite)

En résumé, le pointa2Udoit vérifier le système non linéaire 8>< :f(x) +mX i=1 irgi(x) =0; g i(x) =0;8i=1;:::;m: qui correspond à la condition d"optimalité du lagrangien

L(x;) =f(x) + (;g(x)) =f(x) +mX

i=1 igi(x)8x2Rn;82Rm:

Contraintes de la forme:g(x)0

Appliquons la dualité lagrangienne au problème (primal) min g(x)0f(x) oùg(x) = (g1(x);g2(x);:::;gm(x)). Lemme:La fonction indicatrice deK=fx2Rnjg(x)0gest donnée par I

K(x) =max0(;g(x))

Démonstration:en effet, sigi(x)>0, on peut prendre=0 sauf pour la composantei i=r(gi(x))>0=)(;g(x)) =r gi(x)2! 1sir! 1:

Le maximum sera1.

Au contraire, sig(x)0, on a que(;g(x))080

carg(x)0. Donc le maximum sera 0.

Contraintes de la forme:g(x)0 (suite)

Par conséquent, on peut écrire

min g(x)0f(x) =minxf(x) +IK(x) =minxf(x) +max0(;g(x))

Ceci suggère la fonction lagrangienne

L(x;) =f(x)+(;g(x)) =f(x)+mX

i=1 igi(x)8x2Rn;80 et2Rm: ce qui transforme le problème primal en un problème de point-selle min g(x)0f(x) =minx2Rnmax0L(x;)

Contraintes de la forme:g(x)0 (suite)

La condition d"optimalité du lagrangien sera

I (@L@x;xx)08x2Rnce qui donne @L@x=0() rf(x) +mX i=1 irgi(x) =0 I (@L@ ;)080 . Etant donné quef0gforme un cône convexe, on obtient les conditions suivantes @L@ ;) = (g(x);)080=)g(x)0 @L@ ;) =0()(g(x);) =0

Conditions KKT pour les contraintes:g(x)0

A partir des conditions d"optimalité du lagrangienL(x;), on peut écrire les conditions dites de Karush-Kuhn-Tucker (KKT) pour le problème min g(x)0f(x) Observons que(g(x);) =0 avec0 signifie queigi(x) =0 pour tous lesi=1;:::;m.

Les conditions KKT s"écrivent sous la forme:

8>>>>>>><

>>>>>>:rf(x) +mXquotesdbs_dbs23.pdfusesText_29

[PDF] Circulaire du 26 janvier 2017 concernant les budgets primitifs 2017

[PDF] Conditions tarifaires de location de Véhicules RENT A CAR au 1er

[PDF] Exemple conducteur emission

[PDF] conducteurs en equilibre electrostatique - usthb

[PDF] Travaux dirigés : Conductance et Conductivité - Lycée Gustave

[PDF] Ch3 - EXERCICES Courant électrique dans les solutions aqueuses

[PDF] TRANSFERTS DE CHALEUR - Exercices de références - Doc 'INSA

[PDF] Vapeur - ThermExcel

[PDF] La Conductivité thermique de quelques matériau de construction

[PDF] Propriétés thermiques des matériaux et références métrologiques

[PDF] fimo / fco - Pardessuslahaie

[PDF] Conduire en France avec un permis étranger et son échange I

[PDF] conduite ? tenir devant une femme ayant une cytologie - Aly Abbara

[PDF] Scorpion - Centre AntiPoison et de Pharmacovigilance du Maroc

[PDF] PDF 241 ko Gestion de projet - FOAD