[PDF] RO04/TI07 - Optimisation non-linéaire

View - Download RO04/TI07 - Optimisation non-linéaire

Previous PDF

Next PDF

RO04/TI07 - Optimisation non-linéaireStéphane Mottelet, Mohamed ElbagdouriUniversité de Technologie de Compiègne

Faculté des Sciences Semlalia MarrakechAutomne 20005

SommaireConceptsNotionsExemplesExercicesDocuments2IISommaireI Motivations et notions fondamentales5I.1 Motivations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6I.2 Formes quadratiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14I.3 Rappels de calcul différentiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . .20I.4 Notions sur la convexité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26I.5 Résultats d"existence et d"unicité. . . . . . . . . . . . . . . . . . . . . . . . . . .34I.6 Conditions nécessaires d"optimalité (sans contrainte). . . . . . . . . . . . . . . .38Exemples du chapitre I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41Exercices du chapitre I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49II Les méthodes de gradient54II.1 Les méthodes de descente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55II.2 Les méthodes de gradient. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58Exemples du chapitre II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63III La méthode du gradient conjugué66III.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67III.2 La méthode du gradient conjugué. . . . . . . . . . . . . . . . . . . . . . . . . . .73

SommaireConceptsNotionsExemplesExercicesDocumentsJJ3IIIII.3 Interprétation de la méthode du gradient conjugué. . . . . . . . . . . . . . . . .78IV Méthodes de recherche linéaire83IV.1 introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84IV.2 Caractérisation de l"intervalle de sécurité. . . . . . . . . . . . . . . . . . . . . . .87V Méthodes de Quasi-Newton97V.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98V.2 Les méthodes de quasi-Newton. . . . . . . . . . . . . . . . . . . . . . . . . . . .104V.3 Méthodes spécifiques pour les problèmes de moindres carrés. . . . . . . . . . .117VI Conditions d"optimalité en optimisation avec contraintes121VI.1 Les conditions de Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122VI.2 Les conditions de Kuhn et Tucker. . . . . . . . . . . . . . . . . . . . . . . . . . .134VI.3 Exemples de problèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142VI.4 Conditions suffisantes d"optimalité. . . . . . . . . . . . . . . . . . . . . . . . . .149VII Méthodes primales155VII.1 Contraintes d"égalité linéaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . .156VII.2 Contraintes d"inégalité linéaires. . . . . . . . . . . . . . . . . . . . . . . . . . . .165VII.3 Méthodes de pénalisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169VII.4 Méthodes par résolution des équations de Kuhn et Tucker. . . . . . . . . . . . .177Exemples du chapitre VII. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183VIII Méthodes utilisant la notion de dualité185VIII.1 Elements sur la dualité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .186VIII.2 Methodes duales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193

SommaireConceptsNotionsExemplesExercicesDocumentsJJ4A Documents197A.1 Documents du chapitre I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .198A.2 Documents du chapitre II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .207A.3 Documents du chapitre III. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210A.4 Documents du chapitre V. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .216

SommaireConceptsNotionsExemplesExercicesDocumentssuivantI5Chapitre I

Motivations et notions fondamentalesI.1 Motivations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6I.2 Formes quadratiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14I.3 Rappels de calcul différentiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . .20I.4 Notions sur la convexité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26I.5 Résultats d"existence et d"unicité. . . . . . . . . . . . . . . . . . . . . . . . . . .34I.6 Conditions nécessaires d"optimalité (sans contrainte). . . . . . . . . . . . . . . .38Exemples du chapitre I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41Exercices du chapitre I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

SommaireConceptsNotionsExemplesExercicesDocumentschapitreNsection suivanteI6I.1 MotivationsFormulation générale des problèmes d"optimisation non linéaire. . . . . .7Un exemple en régression non-linéaire. . . . . . . . . . . . . . . . . . . .9Un exemple en mécanique. . . . . . . . . . . . . . . . . . . . . . . . . . .11

SommaireConceptsNotionsExemplesExercicesDocumentssectionNsuivantI7IIFormulation générale des problèmes d"optimisation non linéaire

La forme générale d"un problème d"optimisation est la suivante : (PC)8 >>>>>>>:min x2Rnf(x);(I.1.1)sous les contraintes

g(x)0;(I.1.2)h(x) = 0;(I.1.3)où les fonctionsf,gethsont typiquement non-linéaires (c"est l"objet de cette deuxième partie du

cours). L"équation (VI.1.2) désigne ce que nous apelleront descontraintes d"inégalitéet l"équation

(VI.1.3) descontraintes d"égalité.

L"objet de ce cours est la présentation de techniques permettant de résoudre le problème(PC),

ainsi que des problèmes où soit un seul des deux types de contraintes est présent, soit des problèmes

n"y a pas de contraintes du tout. Nous noterons ces types de problèmes ainsi :(PC)problème général, avec contraintes d"inégalité et d"égalité,

(PCE)problème avec contraintes d"égalité, (PCI)problème avec contraintes d"inégalité, (P)problème sans contraintes.

Il va de soi que la plupart des problèmes réels ou industriels ne sont pas initialement sous une des

formes proposées. C"est pourquoi un des premiers travaux consiste en général à mettre le problème

générale des problèmes d"optimisation non linéaireinitial sous une forme standard. Par exemple, un problème donné sous la forme max x2Rng(x); se mettra sous la forme standard(P)en posantf(x) =g(x)! Cependant, la mise sous forme

standard nécéssite en général un peu plus de travail, comme nous allons le voir dans les exemples qui

suivent.

SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNsuivantI9IIUn exemple en régression non-linéaire020406080100

-1.0-0.6-0.20.20.61.0 O O O OOOO O OO O O O O O O OOOO O OOO O O O OOO OOO OOOO O

OOOOOOO

O

OOOOOOOOOOOOOO

O OO O OO O OO OO OO OO OOOO OOO O OOO OOOOO O OOOOOOOOOn considère un problème d"identification des paramètresa;b;cetcd"un signal du type f(t) =aexp(bt)cos(ct+d);

à partir d"échantillons[ti;yi]i=1:::mdu signalf(t)(ces échantillons sont représentés par les ronds sur

la figure ci-dessus). SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNsuivantIJJ10Un exemple en régression non-linéaireOn propose de faire cette identification en minimisant la fonction

J(a;b;c;d) =12m

X i=1(yif(ti))2; 12m X i=1(yiaexp(bti)cos(cti+d))2:

Le choix d"élever au carré la distance entreyietf(ti)est bien sûr arbitraire : on aurait pu prendre

la valeur absolue, mais le carré permet d"obtenir une fonctionJdifférentiable (ceci sera bien sûr

clarifié dans la suite). Si nous n"ajoutons pas de conditions sur les paramètresa;b;c;dle problème

posé est donc du type(P), avecx= [a;b;c;d]>2R4. Ce problème est communément appelé un problème de moindres carrés (non linéaire).

SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionN11IIUn exemple en mécaniqueu(x)

v(x)On considère une corde horizontale de longueur1tendue à ses deux extrémités, avec une tension

. La déviation éventuelle de la corde par rapport à sa position d"équilibre est désignée paru(x),

pourx2[0;1]. Les extrémités étant fixées, on aura toujoursu(0) =u(1) = 0. On négligera le

poids propre de la corde par rapport à la tension, cela permet d"affirmer qu"en l"absence d"action

extérieure, la corde est au repos et on a doncu(x) = 0;8x2[0;1]. Supposons maintenant que la corde est écartée de sa position d"origine. Alors on peut montrer que l"énergie potentielle associée à cette déformation (supposée petite) est

E(u) =12Z

1 0 dudx 2

dx:(I.1.4)En l"absence d"obstacle, la position de reposu(x) = 0minimise cette énergie. Il peut alors être

intéressant d"étudier un problème où un obstacle empèche la corde de prendre la position triviale

u(x) = 0. Intuitivement, on voit bien que la corde va toucher l"obsctale en certains points, mais pas

forcément en tous les points de l"intervalle[0;1](cela va dépendre de la forme de l"obstacle) SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNJJ12IIUn exemple en

mécaniqueSupposons par exemple que cet obstacle peut être représenté par une fonctionv(x)0. Alors la

présence de l"obstacle se traduit par la condition

u(x)v(x);x2]0;1[:(I.1.5)Si on veut connaître la déformationu(x)de la corde lorsque l"obstacle est présent, on peut donc

penser qu"il est raisonnable de considérer le problème 8>>< >:min u12Z 1 0 dudx 2 dx; u(0) =u(1) = 0;

u(x)v(x); x2]0;1[:(I.1.6)Il s"agit, techniquement parlant, d"un problème de calcul des variations, et donc l"inconnue est

une fonction (la fonctionu(x)). Il parait donc pour l"instant impossible de le mettre sous forme

standard. Cependant, on peut essayer de résoudre un problème approché, en utilisant la méthode des

éléments finis :

Approximation avec la méthode des éléments finis

Puisque l"on est en dimension 1 d"espace, la méthode est très simple à mettre en oeuvre. D"une

part, on discrétise l"intervalle[0;1]: on considère les abscisses x k=kN; k= 0:::N:

On considère le vecteurU= [U1;:::;UN1]>, ainsi que la fonctionuN(x)définie par :uN(xk) =Uk,uN(0) =uN(1) = 0, de plusuNest continue et affine par morceaux.

SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNJJ13Un exemple en mécaniqueOn peut alors montrer que

E(uN) =12U>AU;

oùAest la matrice (définie positive) A=N20 B

BBBB@21 0

1 21 1 21 01 21 C

CCCCA:

On peut donc proposer la version approchée du problème (I.1.6) : minU12U>AU;

v(xk)Uk0;k= 1:::N1:(I.1.7)Il s"agit donc d"un problème se mettant assurément sous la forme(PCI). De plus la fonction

f(U) =12U>AUest assez particulière : il s"agit d"une forme quadratique (nous y reviendrons plus tard). La fonctiongpermettant d"exprimer les contraintes d"inégalité, définie par g(U) =0 B @v(x1)U1... v(xN1)UN1)1 C A; est de pluslinéaire. Nous aborderons des méthodes tenant compte de ces particularités.

SommaireConceptsNotionsExemplesExercicesDocumentsJsection précédentechapitreNsection suivanteI14I.2 Formes quadratiquesDéfinition d"une forme quadratique. . . . . . . . . . . . . . . . . . . . . .15Propriétés des formes quadratiques définies positives. . . . . . . . . . . .17

SommaireConceptsNotionsExemplesExercicesDocumentssectionNsuivantI15IIDéfinition d"une forme quadratiqueCours:exemple en mécaniqueL"exempleprécédentnousdonneuneidée,àpartird"unproblèmeparticulier,delaformequepeut

prendre la fonctionf. Une telle fonction s"appelle une forme quadratique. Nous allons maintenant

étudier leurs propriétés.Définition I.2.1SoitAune matrice symétriquennetb2Rn. On appelle forme quadratique la

fonctionf:Rn!Rdéfinie par f(x) =12x>Axb>x:

Lorsque la matriceApossède certaines propriétés, la fonctionfpeut prendre un nom particulier. La

propriété à laquelle nous allons nous intéresser est la positivité :Définition I.2.2SoitAune matrice symétriquennetb2Rn. On dit queAest semi-définie

positive et on noteA0, quand x >Ax0;8x2Rn: On dit queAest définie positive et on noteA >0, quand x >Ax >0;8x2Rn; x6= 0: d"une forme

quadratiqueCette définition peut être reliée aux valeurs propres de la matriceA:Propriété I.2.3SoitAune matrice symétriquenn. On notefigi=1:::nses valeurs propres

(réelles). On a les équivalences suivantes :

A0()i0; i= 1:::n;

A >0()i>0; i= 1:::n:

Lorsque la matriceAest définie positive (resp. semi-définie positive), on dira quef(x)est une

forme quadratique définie positive (resp. semi-définie positive). Dans le cas oùAest définie positive

la fonctionfpossède un certain nombre de propriétés. Nous nous intéressons dans un premier temps

aux surfacesf(x) =coùc2R.

SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionN17IIPropriétés des formes quadratiques définies positivesExemples:Exemple I.1Propriété I.2.4SoitAune matrice symétriquenn, définie positive etb2Rn. Considérons la

forme quadratique f(x) =12x>Axb>x: On considère la famille de surfaces définie par c=fx2Rn; f(c) =cg; pourc2R, et on définit le vecteur^xsolution de

A^x=b:

Alors cest définie de la façon suivante :-Sic < f(^x)alors c=;.-Sic=f(^x)alors c=f^xg.-Sic > f(^x)alors cest un ellipsoïde centré en^x. SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNJJ18IIPropriétés des formes quadratiques définies

positivesDémonstration :La matriceAétant diagonalisable, il existe une matriceP(la matrice des vecteurs

propres) orthogonale telle que P >AP=D; oùD=diag(1;:::;n)aveci>0. On fait le changement de variabley=x^x: cela donne f(^x+y) =f(^x) + (A^xb)>y+12y>Ay; et puisqueA^x= 0, on a f(x) =f(^x) +12(x^x)>A(x^x): On fait maintenant le changement de variable(x^x) =Pz, ce qui donne f(x) =f(^x) +12z>P>APz; =f(^x) +12z>Dz; =f(^x) +12n X i=1 iz2i:

La surface

cest donc définie par c=( z2Rn;12n X i=1 iz2i=cf(^x)) Sicf(^x)<0il est clair qu"il n"y a pas de solution à l"équation 12n X i=1 iz2i=cf(^x); SommaireConceptsNotionsExemplesExercicesDocumentsJprécédentsectionNJJ19Propriétés des formes quadratiques définies

positivespuisque le second membre est toujours positif! Sic=f(^x)la seule solution estz= 0, c"est à dire

x= ^x. Sic > f(^x)l"équation définit bien un ellipsoïde, puisque lesisont positifs.

Nous avons en fait démontré un résultat très intéressant qui caractérise la valeur minimale prise

parf(x)quandxparcourtRn:Théoreme I.2.5SoitAune matrice symétriquenndéfinie positive etb2Rn, et soitfla forme

quadratique associée, définie par f(x) =12x>Axb>x: Soit^xle vecteur (unique) vérifiantA^x=b, alors^xréalise le minimum def, c"est à dire f(^x)f(x);8x2Rn: Ce résultat est une conséquence directe de la propriétéI.2.4.

SommaireConceptsNotionsExemplesExercicesDocumentsJsection précédentechapitreNsection suivanteI20I.3 Rappels de calcul différentielDéfinition de la différentiabilité. . . . . . . . . . . . . . . . . . . . . . . . .21Calcul de la dérivée première. . . . . . . . . . . . . . . . . . . . . . . . .23Dérivée seconde. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25

SommaireConceptsNotionsExemplesExercicesDocumentssectionNsuivantI21IIDéfinition de la différentiabilité

DansRnon notexle vecteur colonne

x=0 B @x 1... x n1 C A; et la notationk:kdésignera, sauf indication du contraire, la norme euclidienne kxk= nX k=1x 2k! 12

Avant de donner la définition de la différentiabilité, il est important de rappeller celle de laconti-

nuité:Définition I.3.1Soitf:Rn!Rm, on dit quefest continue au pointa2Rnsi pour tout réel >0il existe >0tel que kxak< ) kf(x)f(a)k< :

Voici maintenant la définition de la différentiabilité :Définition I.3.2Soitf:Rn!Rmreprésentée dans la base canonique deRmpar le vecteur

f(x) =0 B @f 1(x) f m(x)1 C

A;(I.3.8)

SommaireConceptsNotionsExemplesExercicesDocumentssectionNsuivantIJJ22Définition de la

différentiabilitécontinue ena2Rn. On dit quefest différentiable enas"il existe une application linéaire, notée

f

0(a), telle que pour touth2Rnon ait

quotesdbs_dbs1.pdfusesText_1

[PDF] exercices corrigés methodes itératives

[PDF] exercices corrigés microéconomie 1ère année

[PDF] exercices corrigés microéconomie équilibre général

[PDF] exercices corrigés mitose

[PDF] exercices corrigés mouvement des satellites

[PDF] exercices corrigés mouvement seconde

[PDF] exercices corrigés ondes seconde

[PDF] exercices corrigés ondes terminale s

[PDF] exercices corrigés optimisation non linéaire

[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