[PDF] Optimisation non linéaire : correction des TD

View - Download Optimisation non linéaire : correction des TD

Previous PDF

Next PDF

Optimisation non linéaire : correction des TD

Grégory Bonnet

Rémi Douvenot

Nicolas Fezans

Emmanuel Rachelson

Stéphanie Roussel

17 janvier 2008

TD 1: Généralités

Exercice 1: étude des fonctions quadratiques

Les fonctions quadratiques sont très souvent rencontrées dans les problèmes d"optimisation car il s"agit d"une formestandardd"énergie. SoientQune matrice deRnn,bun vecteur deRnetf:Rn7!Rla fonction définie parf(x) = 12 xTQx+bTx,x2Rn.

Différentiabilité au sens de Fréchet

fest différentiable au sens de Fréchet en^xsi9f0F(^x)2 L(Rn;R)tel que

8v2Rn,f(^x+v) =f(^x) +f0F(^x)(v) +o(v)aveclimv7!0jjo(v)jjjjvjj= 0.

Il nous faut donc exhiberf0F(^x)et il suffit de poser l"équation précédente et de la développer: f(x+v) =12 (x+v)TQ(x+v) +bT(x+v) 12 xT+12 vT)(Qx+Qv) +bTx+bTv 12 xTQx+12 xTQv+12 vTQx+12 vTQv+bTx+bTv =f(x) +12 xTQv+12 vTQx+12 vTQv+bTv Nous pouvons remarquer quexTQvest un scalaire (c"est-à-direxTQv2R). Or un scalaire est égal à sa transposée, doncxTQv= (xTQv)T= (vTQTx). f(x+v) =f(x) +12 xTQv+12 (vTQx)T+12 vTQv+bTv =f(x) +12 xTQv+12 xTQTv+12 vTQv+bTv =f(x) + (12 xT(Q+QT) +bT)v+12 vTQv Les équations précédentes nous conduisent alors à poser: f

0F(^x)(v) = (12

xT(Q+QT) +bT)veto(v) =12 vTQv 1 Il nous faut alors vérifier quef0F(^x)(v)est linéaire env(ce qui est trivial); et il faut nous assurer quelimv7!0jjo(v)jjjjvjj= 0

En posantqm= maxi;j2f1;:::;ngqij:jjo(v)jj=jj12

vTQvjj=j12 vTQvj j12 qmjjvjj2j

Nous avons donc:0jjo(v)jjjjvjj jqmjjjvjj2

Orlimv!0jqmjjjvjj2= 0. Donclimv!0jjo(v)jjjjvjj= 0. fest donc différentiable au sens de Fréchet (et par conséquent au sens de

Gâteaux) etf0F(^x)(v) =@f@x

(^x)v; et par identification: @f@x (^x) =12 ^xT(Q+QT) +bT

Calcul du Hessien

Calculer le Hessien defest fondé sur le principe précédent, appliqué au gradient def. En effet, montrer quefest deux fois différentiable revient à montrer quef0F(:)(v)est différentiable; donc quef0F(^x+w)(v) =f0F(^x)(v) + f

00(^x)(v)(w) +o(w)avecf00(^x)(v)(:)2 L(Rn;R)etlimw!0jjo(w)jjw

= 0. f

0F(^x+w)(v) =@f@x

(^x+w)v @f@x (^x+w) =12 (^x+w)T(Q+QT) +bT 12 ^xT(Q+QT) +bT+12 wT(Q+QT) @f@x (^x) +12 wT(Q+QT)

On pose alorsf00(^x)(v)(w) =12

wT(Q+QT)eto(w) = 0. Il faut alors s"assurer quef00(^x)(v)(w)est linéaire enw(ce qui est trivial) et quelimw!0jjo(w)jjjjwjj= 0(ce qui est trivial aussi); ainsi le Hessien defest 2f@x 2=12 (Q+QT)

L"expression def00(x)(v)(v)est<@2f@x

2v;v >=12

vT(Q+QT)v

Convexité

Si l"on supposeQsymétrique alorsQ=QT; et@f@x

=xTQ+bTet@2f@x 2=Q. Rappelons qu"une matrice est définie positive (resp. semi-définie positive) si et seulement si ses valeurs propres sont toutes strictement positives (resp. positives ou nulles). Pour montrer quefest convexe, deux méthodes sont proposées. Une fonction est strictement convexe (resp. convexe) si son Hessien est défini positif (resp. semi-défini positif). Dans notre application, le Hessien estQet, donc,fest strictement convexe (resp. convexe) siQest défini positive (resp. semi-défini positive). 2 En utilisant la proposition donnée dans l"exercice, nous pouvons vérifier ceci d"une autre manière. On pose:

A(x;y) =f(y)f(x)@f@x

(x)(yx) yTQy2 +bTyxTQx2 bTxxTQ(yx)bT(yx) yTQy2 xTQx2 +xTQxxTQy yTQy2 +xTQx2 xTQy

OrxTQy=xTQy2

+xTQy2

T=xTQy2

+yTQx2

DoncA(x;y) =12

(yx)TQ(yx)et doncA(x;y)0siQest semi-définie positive (A(x;y)>0siQest définie positive).

Exercice 2: Approximation de fonction

Dans cet exercice, nous cherchons un polynômehqui approxime la fonction gau sens des moindres carrés. Cela signifie quehdoit minimiser la grandeur suivante: f=mX i=1[g(xi)h(xi)]2

Résolution générale du problème

Cet exercice se prête bien à un traitement matriciel. On pose: H=2 6

4h(x1)

h(xm)3 7 5=2 6 4x

01xn1......

x

0mxnm3

7 52
6 4a 0... a n3 7

5=XaetG=2

6

4g(x1)

g(xm)3 7 5

On a alors:

f=(HG)T(HG) =HTH+GTG2GTH(carGTGest un scalaire) =aTXTXa+GTG2GTXa Par définition,XTXest une matrice symétrique; et en posantQ= 2XTX etb=2XTG, on se ramène à la fonction quadratique de l"exercice prédécent. Donc: @f@a (a) =aTQ+bT 3

La condition du premier ordre nous donne:

a

TQ+bT= 0 =)a=bTQ1=QTb

La matriceXTXest diagonalisable. En effet,Q=XTX:

Q=2 6 4x

01x0m......

x n1xnm3 7 52
6 4a 0... a n3 7 52
6 4x

01xn1......

x

0mxnm3

7 52
6 4a 0... a n3 7 5

Doncqij=mP

k=1xi+j2 k:Qest bien symétrique. Par ailleurs,8v2Rn+1, v

TQv=vTXTXv= (Xv)T(Xv) =jjXvjj 0.

DoncXTXest semi-définie positive; doncQest semi-définie positive (car Q= 2XTX). L"optimumatrouvé est donc bien un mimimum au sens des moindres carrés.

Application numérique

Dans l"application:

X=2 41 1
1 2 1 33 5 etG=2 48
25
523
5

On obtient:

X

TX=3 6

6 14 etXTG=85 214

Nous cherchonsa=QTb, doncQ1etb:

Q

1= (2XTX)1=112

146
6 3 =QTetb= 2XTG=170 428

Par conséquent:

a= (2XTX)1(2XTG) =473 22

Donc,h(x) = 22x473

Nous pouvons vérifier la validité de cette approximation carh(1) = 6;33, h(2) = 28;33eth(3) = 50;33pourg(1) = 8,g(2) = 25etg(3) = 52.

Exercice 3: Production

Remarques d"ordre général pour l"optimisation Dans cet exercice, nous cherchons à maximiser une quantité. Notre problème peut donc être modélisé de la façon suivante: max x i0qh(x1:::xn)nX i=1p ixi 4 Nous négligerons les contraintes de positivité; et nous les vérifieronsa poste- riori. En effet, chaquexiest nécessairement positif car il représente une quantité de matière première. La condition du premier ordre pour trouver un optimum est d"annuler le gradient.

8i2 f1;:::;ng;@f@x

i(x1;:::;xn) =q@h(x1:::xn)@x ipi La condition du second ordre est d"avoir un Hessien semi-défini négatif (resp. défini négatif) afin d"avoir un maximum (resp. strict). Ici, 2f@x 2=q2 6 64@
2h@x

2:::@2h@x

1xn......

2h@x nx1:::@2h@x 2n3 7 75

Application 1

Soith(x1;x2) =x13

1x13

2. La condition du premier ordre nous donne:

@f@x q3 x23 1x13 2p1 q3 x13 1x23 2p2# = 0

Il nous faut résoudre le système:

q3 x23 1x13 2p1=0 q3 x13 1x23

2p2=0()8

:x 13

2=3p1x23

1q x 13

1=3p2x23

2q ()(x

2=27p3

1x2 1q 3(1) x

1=27p3

2x2 2q 3(2)

On injecte (1) dans (2):

x

1=27p32(27p31x211q

3)21q 3 =27p32(272p61x411q 6)1q 3 =27

3p61p32x411q

18 x

31=q1827

3p61p32()x1=q327p21p2

Le raisonnement est identique pourx2; et avecp1=p2= 1,x1=x2=q327

La condition du second ordre nous donne:

2f@x 2=" q9 (2x53 1x13 2)q9 (x23 1x23 2) q9 (x23 1x23 2)q9 (2x13 1x53 2)# 5

Au point^xconsidéré, le Hessien est:

2f@x

2(^x) =9q

3 2 1 12 Ici, le déterminant est positif (il vaut3) et la trace est négative (elle vaut4); donc le produit des valeurs propres est positif et leur somme est négative. Par conséquent les deux valeurs propres sont du même signe et de somme négative: les deux valeurs propres sont négatives. Si l"on veut s"en convaincre par le calcul, le polynôme caractéristique vaut:

P() =21

12 = (2 +)21 = (+ 1)(+ 3)

Application 2

Soith(x1;x2) =x21+x22. La condition du premier ordre nous donne: @f@x =2qx1p1

2qx2p2

= 0

Nous avons doncx1=p12qetx2=p22q.

La condition du second ordre nous donne:

2f@x 2=2q0 0 2q Or, le Hessien est défini positif. Nous avons trouvé un minimum alors que nous cherchions un maximum. Dans cette application, le bon sens peut nous permettre de trouver directe- ment ce résultat. En effet, on peut produire indifféremment le produit final avec du produit1ou du produit2. Or le produit2coûte moins cher: on ne va donc utiliser que du produit2. De plus, avecp2= 1etq= 1, on a un bénéfice dex22x2. Or cette quantité est décroissante et bornée sur[0;1]tandis qu"elle est croissante sur[1;+1[et limx2!1x22x2=1. Plus on augmente la production, plus on augmente le bénéfice. Le maximum est atteint enx2= +1. Il n"y a donc pas de maximum réel au problème. Cela traduit graphiquement le fait que l"on cherche le maximum d"une fonction convexe (coercive): il est en+1. On ne peut trouver des maxima dansRque pour des fonctions (localement) concaves. 6

TD 2: Qualification

Exercice 1: directions et cônes admissibles

Premier domaine

=f(x;y)2R2: (x1)2+y21 = 0etx2+ (y1)21 = 0g11 (Approche graphique)Qu"est-ce qu"une direction admissible? Considé- rons un domaine dansRnet un point donné^xde ce domaine, une direction est admissible si l"on peut se déplacer dans cette direction à partir du point^xsans sortir du domaine. L"ensemble des directions admissibles en un point est noté D ^x(

Pour notre exercice, nous pouvons remarquer que

=f(0;0)(1;1)g. Ainsi au voisinage de(0;0), le domaine est vide. Il est donc impossible de se déplacer sur le domaine dans une direction autre que le vecteur nul. AinsiD(0;0)( ) =f(0;0)g. En effet, le vecteur nul est toujours une direction admissible (il est toujours possible de ne pas se déplacer). (Approche par la définition)Bien entendu, une direction admissible est définie formellement. Définition 1(Direction admissible).Soit un domaine

Rnet un point^x

de ce domaine. Le vecteurv2Rnest une direction admissible si et seulement si9'2 C1(R+;Rn)telle que: -'(0) = ^x -'0(0) =v -9 >0;80< t < ;'(t)2 7 Si l"on se considère au point(0;0), par définition'(0) = (0;0). Comme' est continue et que, pourtpetit,'(t)2 , la seule fonction'respectant ces deux propriétés est'(t) = (0;0). On peut s"en convaincre en raisonnant par l"absurde: Supposons qu"il existe une direction admissiblev6= (0;0). La formule de Taylor appliquée au'correspondant nous indique que'(t) ='(0) +'0(0):t+ o(t). Or'(t)2 . Donc'(t) = (0;0); par conséquentvt+o(t) = (0;0). On sait quelimt!0o(t)t = (0;0). Oro(t)t =vetv6= (0;0)par hypothèse. C"est absurde: il n"existe donc pas de direction admissible non nulle. Un raisonnement identique peut être tenu si l"on se considère au point(1;1) (Approche par la régularité)La notion de régularité ne s"applique qu"aux contraintes égalités. On dit que les contraintes sont régulières en un point^x si et seulement si leurs gradients en ce point forment une famille libre. Si l"on considère des contraintes régulières alorsD^x( ) = ker(rg(^x))oùgest le vecteur des contraintes égalitésgi. Dans notre exercice, nous avons deux contraintes: g

1(x;y) = (x1)2+y21etg2(x;y) =x2+ (y1)21. Les gradients des

contraintes sont: rg1(x;y) =2(x1) 2y etrg2(x;y) =2x 2(y1) et au point considéré: rg1(0;0) =2 0 etrg2(0;0) =0 2 Comme il y a indépendance linéaire entre ces deux vecteurs, les contraintes sont régulières; donc:quotesdbs_dbs33.pdfusesText_39

[PDF] optimisation convexe exercices corrigés

[PDF] fonction strictement convexe

[PDF] optimisation quadratique sous contrainte linéaire

[PDF] optimisation convexe pdf

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab