Optimisation non-linéaire
Exercice I.4 Calculer le gradient et la matrice Hessienne des fonctions suivantes : f(xy) = x3 + 3xey
RO04/TI07 - Optimisation non-linéaire
Exercices. Documents section ? suivant ?. 7. ??. Formulation générale des problèmes d'optimisation non linéaire. La forme générale d'un problème
Optimisation non linéaire : correction des TD
17 jan. 2008 Dans cet exercice nous chercherons à optimiser la fonction sans contrainte puis nous vérifierons a posteriori que l'optimum se trouve dans le ...
TD 1 Optimisation non linéaire : Généralités
Optimisation non linéaire : Généralités. Exercice 1 :Étude des fonctions quadratiques. Soient Q une matrice de Rn×n b un vecteur de Rn et f : Rn ? R la
LICENCE 3 MATHEMATIQUES – INFORMATIQUE
systèmes non linéaires optimisation). Pour chaque semaine
RO04/TI07 - Optimisation non-linéaire
Exercices. Documents chapitre ? section suivante ?. 5. I.1 Motivations. I.1.1. Formulation générale des problèmes d'optimisation non linéaire .
1 Les conditions de Kuhn-Tucker
Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... cas de la programmation linéaire ces conditions sont réalisée car une fonction.
Optimisation Non Linéaire Travaux Pratiques I Optimisation sans
Optimisation Non Linéaire. Travaux Pratiques I. Mehmet Ersoy. Optimisation sans contraintes : algorithmes. Le but de ce TP est de tester différentes
Exercices sur le cours “Optimisation et programmation dynamique” 1
“Optimisation et programmation dynamique” o`u s et c sont des vecteurs de Rn non nuls. ... 1.3.2 Programmation linéaire et algorithme du simplexe.
Méthodes numériques pour loptimisation non linéaire déterministe.
f(xk). Démonstration. En exercice. d. Théorème 1.1 f est convexe si et seulement si son épigraphe epi(f) =
RO04/TI07 - Optimisation non-linéaireStéphane Mottelet, Mohamed ElbagdouriUniversité de Technologie de Compiègne
Faculté des Sciences Semlalia MarrakechAutomne 20005SommaireConceptsNotionsExemplesExercicesDocuments2IISommaireI 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 IMotivations 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 contraintesg(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 formestandard 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 OOOOOOOO
OOOOOOOOOOOOOOO
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 fonctionJ(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) estE(u) =12Z
1 0 dudx 2dx:(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 enmé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 conditionu(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 formestandard. 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 finisPuisque 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 queE(uN) =12U>AU;
oùAest la matrice (définie positive) A=N20 BBBBB@21 0
1 21 1 21 01 21 CCCCCA:
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 formequadratiqueCette 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 uneforme 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 deA^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éfiniespositivesDé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éfiniespositivespuisque 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.quotesdbs_dbs18.pdfusesText_24[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