[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

quotesdbs_dbs19.pdfusesText_25

[PDF] exercices avec corrigés de comptabilité nationale sur le tee et le tes

[PDF] exercices axe corporel

[PDF] exercices beton arme avec leurs solutions pdf

[PDF] exercices biologie générale

[PDF] exercices calculs commerciaux bac pro commerce

[PDF] exercices calculs d aires cap

[PDF] exercices chimie kc

[PDF] exercices chimie organique 1ere année pharmacie pdf

[PDF] exercices cinématique terminale s

[PDF] exercices classes grammaticales 6ème

[PDF] exercices concept de base de la comptabilité générale

[PDF] exercices concept de base de la comptabilité générale pdf

[PDF] exercices conjugaison 6ème imparfait passé simple

[PDF] exercices conjugaison 6eme imprimer

[PDF] exercices conjugaison tous les temps pdf