[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

= 0quotesdbs_dbs1.pdfusesText_1

[PDF] exercices corrigés optique géométrique pdf

[PDF] exercices corrigés optique ondulatoire mp

[PDF] exercices corrigés orthogonalité dans l'espace

[PDF] exercices corrigés outlook 2010

[PDF] exercices corrigés pendule elastique

[PDF] exercices corrigés pert pdf

[PDF] exercices corrigés ph des solutions aqueuses

[PDF] exercices corrigés physique chimie terminale s

[PDF] exercices corrigés physique pcsi pdf

[PDF] exercices corrigés physique seconde forces et principe d'inertie

[PDF] exercices corrigés physique terminale s ondes

[PDF] exercices corrigés physique terminale s pdf

[PDF] exercices corrigés physique terminale sti2d

[PDF] exercices corrigés poo c# pdf

[PDF] exercices corrigés primitives terminale s pdf