Introduction aux Méthodes dOptimisation sans Gradient pour l
Les algorithmes génétiques diffèrent des autres méthodes d'optimisation car ils utilisent un codage des variables de contrôle plutôt que les variables de
Introduction à loptimisation aspects théoriques et numériques
Méthodes de type gradient. 2. Algorithmes pour l'optimisation SANS contrainte. Les méthodes de Newton en dimension supérieure. 3. Introduction `a
Introduction à lOptimisation Numérique
2.3.1 Algorithmes de gradient à pas fixe/pas optimal . solution de problèmes d'optimisation sans contrainte (cf chapitre 2) puis avec contraintes (cf.
Introduction à loptimisation Aspects théoriques et numériques
III.3 Méthodes de gradient . III.4 Les méthodes de Newton et quasi-Newton . ... Si K = V on dit que (I.1) est un problème d'optimisation sans ...
Méthodes Numériques : Optimisation
La première et principale partie du cours concerne les problèmes d'optimisation sans contraintes. Nous abordons les algorithmes de type descente de gradient
Introduction à loptimisation Aspects théoriques et numériques
III.3 Méthodes de gradient . III.4 Les méthodes de Newton et quasi-Newton . ... Si K = V on dit que (I.1) est un problème d'optimisation sans ...
Introduction à lOptimisation Numérique
Ces informations sont fournies en “boite noire” i.e. par un sous-programme indépendant de l'algorithme d'optimisation choisi : routine de calcul du gradient
Comparaison de différentes méthodes doptimisation sans
Dans ce TP d'introduction `a l'optimisation pour l'image nous allons introduire un gradient comment chercher le minimum d'une fonction par descente de ...
Méthodes numériques : optimisation
Apr 19 2015 chapitre portera sur les méthodes de gradient conjugué
Notes de cours - Préparation à lagrégation - Introduction à l
3 Conditions d'optimalité - optimisation sans contrainte L'interpolation de Lagrange et les algorithmes de gradients seront étudiés ultérieurement au.
[PDF] Introduction aux Méthodes dOptimisation sans Gradient pour l - Inria
Introduction aux Méthodes d'Optimisation sans Gradient pour l'Optimisation et le Contrôle en Mécanique des Fluides R Duvigneau
[PDF] Méthodes doptimisation sans gradient pour des probl`emes
18 avr 2013 · Méthodes d'optimisation sans gradient pour des probl`emes inverses en ingénierie pétroli`ere Laurent DUMAS avec F Delbos D Ding (IFPEN)
[PDF] Introduction à lOptimisation Numérique
Dans les chapitres suivants nous entrons dans le vif du sujet en nous intéressant à la ré- solution de problèmes d'optimisation sans contrainte (cf chapitre 2)
[PDF] Cours-Optimisationpdf
L'optimisation consiste en la recherche du minimum (ou du maximum) d'une cer- taine quantité appelée coût ou objectif Dans ce cours on supposera que le
[PDF] Méthodes Numériques : Optimisation - ceremade
La première et principale partie du cours concerne les problèmes d'optimisation sans contraintes Nous abordons les algorithmes de type descente de gradient
[PDF] Méthodes numériques : optimisation - ceremade
19 avr 2015 · chapitre portera sur les méthodes de gradient conjugué et s'il reste un pour résoudre des problèmes d'optimisation avec contraintes
[PDF] optimisationpdf
Plan du cours • Introduction • Analyse de la fonction objectif • Conditions d'optimalité sans contrainte • Résolution d'équations • Optimisation sans
[PDF] aspects théoriques numériques et algorithmes
1 3 6 Le gradient d'un champ scalaire 4 Quelques algorithmes pour l'optimisation sans contraintes 4 6 Les méthodes de Newton et quasi-Newton
[PDF] Introduction à loptimisation Aspects théoriques et numériques
Même pour le gradient à pas optimal qui est en principe la meilleure de ces méthodes d'un point de vue de la rapidité de convergence celle-ci peut être lente
[PDF] Résumé dOptimisation
Et donc le gradient de f en uk+1 lui est orthogonal 5 2 Méthode de Newton Si f est une fonction réguli`ere dont on sait calculer le gradient et la matrice
Resume d'Optimisation
MI5 Master Pro 1ere annee
Jean-Pol Guillement
Departement de Mathematiques
Nantes 2010/2011
2Table des matieres
Introduction5
1 Rappels7
1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Condition d'ordre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1Equation d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Conditions d'ordre 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Condition de Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Condition susante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Extrema lies, multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Programmation lineaire 9
2.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Probleme sous forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Caracterisation des sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Methode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Programmation en dimension 1 11
3.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Interpolation quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Methode par decoupage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Prise en compte de la convexite 13
4.1 Condition necessaire de minimum sur un convexe . . . . . . . . . . . . . . . . . . . . . 13
4.2 Caracterisation des fonctions convexes derivables . . . . . . . . . . . . . . . . . . . . . 13
4.3 Minimum des fonctions convexes sur un convexe . . . . . . . . . . . . . . . . . . . . . 13
4.4 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5 Notation : probleme (P) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.6 Existence de minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.7 Fonctionnelles elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.8 Caracterisation des fonctionnelles elliptiques . . . . . . . . . . . . . . . . . . . . . . . . 14
4.9 Minimum des fonctions elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.10 Fonctionnelles quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.11 Resolution des systemes lineaires au sens des moindres carres . . . . . . . . . . . . . . 15
4.12 Projection sur un convexe ferme non vide . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Optimisation sans contrainte 17
5.1 Methodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1.1 Methode de la relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1.2 Methode de la plus profonde descente (methode du gradient) . . . . . . . . . . 17
5.2 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3 Methode de la metrique variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.4 Methode du gradient conjugue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.4.1 Cas des fonctionnelles quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.4.2 Cas des fonctionnelles non quadratiques . . . . . . . . . . . . . . . . . . . . . . 19
4TABLE DES MATIERES6 Optimisation avec contraintes 21
6.1 Relations de Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.1.1 Cas des contraintes non convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.1.2 Cas des contraintes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2 Interpretation des relations de Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . 22
6.3 Point-selles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.4 Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.5 Point-selle du Lagrangien et solution du probleme (P) . . . . . . . . . . . . . . . . . . 23
6.6 Probleme dual du probleme (P) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.7 Methode d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.7.1 Demarche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.7.2 Calcul dek+1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.7.3 Calcul derGk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.7.4 Condition susante de convergence de la methode d'Uzawa . . . . . . . . . . . 24
Bibliographie24
Introduction
Ceci un resume des principaux resultats du cours d'optimisation. Il est autorise aux contr^oles.6Introduction
Chapitre 1
Rappels
1.1 Notations
Sifest une fonction reguliere deE=Rn!R, on note sa derivee enx0parf0x0ouf0(x0)(2 L(E;R)),
sa derivee seconde enx0parf00x0ouf00(x0)(2 B(E;R)), son gradient enx0parrfx0ourf(x0)(2E),
sa matrice hessienne parr2fx0. La matrice Hessienne peut ^etre vue comme une matrice symetrique nn, comme un operateur lineaire deEdansEou comme une forme bilineaire symetrique surE.1.2 Formules de Taylor
([3, p.151-146]) Les formules de Taylor dierent selon l'ordre, l'ecriture du reste, l'utilisation des derivees ou du gradient et de la matrice Hessienne. En voici deux exemples :Sifest deux fois derivable on a :
f(x0+h) =f(x0) +f0(x0)h+12 f"(x0)(h;h) +"(h)khk2:Sifest de classeC2on a :
f(x0+h) =f(x0) +ht:rfx0+12 ht:r2fx0:h+Z 1 0 (1t)ht:r2f(x0+th):h dt1.3 Condition d'ordre 1
1.3.1Equation d'Euler
([3, p.146]) Soit un ouvert deEet soitf: !R:Sifadmet un extremum local enx2 et sifest derivable enxalors (equation d'Euler) f0(x) = 0
1.4 Conditions d'ordre 2
1.4.1 Condition de Legendre
([3, p.152]) Soit un ouvert deEet soitf: !R. Sifadmet un minimum local enx2 et sifest deux fois derivable enxalors (condition de Legendre) f"(x) est une forme bilineaire symetrique positive.8Rappels1.4.2 Condition susante
([3, p.152]) Soit un ouvert deEet soitf= !R. Sifest deux fois derivable sur , sif0(x) = 0 et sif"(x) est positive dans un voisinage dex2 , alorsfa un minimum local enx:1.5 Extrema lies, multiplicateurs de Lagrange
([3, p.148]) Soit un ouvert deE, soitf: !R, soient'i: !R;i= 1;::;m:On suppose que les'i2 C1(
Soitx2K=fx2
;'i(x) = 0;i= 1:::mgtel que les derivees'0i(x) soient lineairement independantes (dansL(E;R)) et tel quefsoit derivable enx. Alors sifadmet un extremum local relativement aKenx, il existe1;:::;muniques (multiplicateurs de Lagrange) tels que rf(x) +1r'1(x) +:::+mr'm(x) = 0Chapitre 2
Programmation lineaire
Pas enseigne cette annee. (Voir [3], [5], [7], [9]).2.1 Generalites
2.2 Probleme sous forme standard
2.3 Caracterisation des sommets
2.4 Methode du simplexe
10Programmation lineaire
Chapitre 3
Programmation en dimension 1
3.1 Generalites
3.2 Methode de Newton
3.3 Interpolation quadratique
3.4 Methode par decoupage
12 Programmation en dimension 1
Chapitre 4
Prise en compte de la convexite
4.1 Condition necessaire de minimum sur un convexe
([3, p.153])SoitKun convexe dans
ouvert deE. Soitf: !R: Sifadmet un minimum relativement aKenx, et sifest derivable enxalors (Inequation d'Euler) f0(x)(xx)08x2K
4.2 Caracterisation des fonctions convexes derivables
([3, p.154-155]))SoitKun convexe dans
ouvert deE. Soitf: !Rderivable sur1.fest convexe surKsi et seulement si
f(x)f(x0) +f0(x0)(xx0)8x;x02K2.fest strictement convexe surKsi et seulement si
f(x)> f(x0) +f0(x0)(xx0)8x;x02K; x6=x03. On suppose quefest deux fois derivable dans
. Alorsfest convexe surKsi et seulement si f"(x)(yx;yx)0;8x;y2K4. On suppose quefest deux fois derivable dans
. Si f"(x)(yx;yx)>0;8x;y2K;x6=y alorsfest strictement convexe surK.4.3 Minimum des fonctions convexes sur un convexe
([3, p.156-175])SoitKun convexe dans
ouvert deE, soitf: !Rconvexe surK.1. Sifadmet un minimum local enx2K, relativement aK, ce minimum est un minimum global.
2. Sifest strictement convexe surK;fadmet au plus un minimum local relativement aK(qui
est aussi un minimum strict et global)3. Sifest derivable enx2K, alorsfadmet un minimum par rapport aKenxsi et seulement
si (Inequation d'Euler) f0(x)(xx)08x2K
ou, en terme de gradient (rfx;xx)0;8x2K:14 Prise en compte de la convexite
4. SiKest un sous espace vectoriel l'inequation d'Euler est equivalente a
f0(x)(x) = 0;8x2K:
ou, en terme de gradient rfx?K5. SiKest ouvert, l'inequation d'Euler est equivalente a la condition d'Euler
f0(x) = 0
4.4 Fonctions coercives
([3, p.175])Une fonctionf:E!R, est dite coercivesi lim
kxk!1f(x) = +14.5 Notation : probleme(P)
Dans la suite, quand on parle du probleme (P), il s'agit de la recherche dextel que (P)(f(x) = infx2KEf(x) x 2K4.6 Existence de minimum
([3, p. 175])1. SiKest un ferme borne non vide deE, sifest continue alors le probleme (P) a au moins une
solution.2. SiKest ferme non borne deE, sifest continue et coercive, alors le probleme (P) a au moins
une solution.3. SiKest un convexe ferme non vide deE, sifest continue, coercive, strictement convexe sur
K, alors le probleme (P) a une solution et une seule.4.7 Fonctionnelles elliptiques
([3, p. 183]) Une fonctionf:E!R, de classeC1est dite elliptiques'il existe >0 tel que (rfx rfy;xy)kxyk28x;y2E4.8 Caracterisation des fonctionnelles elliptiques
Une fonctionf:E!R, deux fois derivable, est elliptique si et seulement si il existe >0 tel que (r2fx0x;x)kxk2;8x;x02E4.9 Minimum des fonctions elliptiques
SoitKest un convexe ferme non vide deEetf:E!Relliptique.1.fest strictement convexe, coercive, et verie
f(x)f(x0)(rfx0;xx0) +2 kxx0k28x;x02E2. Le probleme (P) a une solution et une seule.
4.10 Fonctionnelles quadratiques 15
3.x2Kest solution de (P) si et seulement si
(Inequation d'Euler) (rfx; xx)0;8x2K:4. On suppose queK=E. Alorsxest solution de (P) si et seulement si
rfx= 04.10 Fonctionnelles quadratiques
Ce sont les fonctions de la forme
f(x) =12 (Ax;x)(b;x) +c Aetant un matrice symetrique (operateur deE!E); b2E; c2R.Elles sont de classeC1;rf=Axb;r2f=A:
Elles sont elliptiques si et seulement si la plus petite valeur propre deAest>0 et dans ce cas, si K=E, le probleme (P) a une solution et une seule, qui est aussi la solution deAx=b:4.11 Resolution des systemes lineaires au sens des moindres
carresMest une matrice amlignes etncolonnes,v2Rm:
Il s'agit de trouverx2Etel quekMxvk2soit minimal, ou encore de resoudre le probleme (P)f(x) = infx2Ef(x) avecf(x) =12 kMxvk212 kvk2: fse met sous la forme d'une fonctionnelle quadratique avecA=MtM;etb=Mtv: Le probleme (P) a au moins une solution. Ses solutions sont caracterisees par (Equations normales) M tMx=Mtv Si le rang deMestn, le probleme (P) a une solution et une seule. La solution peut se calculer par resolution du systeme triangulaireRx=PQtv
ouQetRsont les matrices de la decomposition QR de la matriceM,M=QR, etPla projection deRmsurRn f0gmn.4.12 Projection sur un convexe ferme non vide
SoitKun convexe ferme non vide deE. Soitx2E.
Il existePx2K, unique, tel qued(x;K) =kxPxk:La projectionPxest caracterisee par (xPx;yPx)0;8y2K:L'applicationx!Pxest contractante
kPxPyk kxyk16 Prise en compte de la convexite
Chapitre 5
Optimisation sans contrainte
Il s'agit de resoudre numeriquement le probleme (P) (P)(trouverx2E=Rn f(x) = infx2Ef(x) Les algorithmes operent generalement pour des fonctionnelles assez generales, mais la convergence (theorique) n'est assuree que pour des fonctionnelles de classeC1ouC2, convexes ou elliptiques. Les solutions de (P) etant aussi solution derfx= 0, les algorithmes peuvent se voir comme des algorithmes de resolution de cette equation.5.1 Methodes de descente
Elles sont iteratives. Pour passer deukauk+1, on se donne une direction de descentedket on minimise fle long de cette direction, c'est-a-dire que l'on cherchektel quef(uk+kdk) = inf2Rf(uk+dk):A defaut d'un telkon peut se contenter d'avoirf(uk+kdk)< f(uk).5.1.1 Methode de la relaxation
([3, p. 185]) On descend de facon cyclique le long de chacun des axes de coordonnees.La convergence est assuree sifest elliptique.
NoteSifest une fonctionnelle quadratiquef(x) =12
(Ax;x)(b;x) dont la matriceAest symetriquedenie positive, la methode de la relaxation converge et ses iterations sont identiques a celles de la
methode de Gauss-Seidel pour la resolution de l'equationAx=b:5.1.2 Methode de la plus profonde descente (methode du gradient)
La direction choisie estrfukqui correspond a la direction de plus grande decroissance def:On peut en eet ecrire : f(x)f(x0) = (rfx0;xx0) +"(x)kxx0k et remarquer qu'akxx0kconstant, (rfx0;xx0) est minimal pourxx0=trfx0; t >0:Description
On part deu0quelconque. Connaissantuk, on calculerfuketuk+1=ukkrfukavecksolution def(ukkrfuk) = inf(ukrfuk). En principe on trouvek>0.18 Optimisation sans contrainte
Condition susante de convergence
([3, p. 188]) Sif:E!Rest elliptique, la methode de la plus profonde descente est convergente.Remarque
Cette methode ne peut pas ^etre optimale car le cheminement desukest celui d'une ligne brisee faisant
des angles droits. En eet, deux gradients consecutifs sont orthogonaux caruk+1correspondant au minimum def(ukrfuk);la derivee defdans cette direction s'annule enuk+1. Et donc le gradient defenuk+1lui est orthogonal.5.2 Methode de Newton
Sifest une fonction reguliere dont on sait calculer le gradient et la matrice hessienne, on peut tirer
partie du fait qu'en un pointuk;fest localement voisine de son developpement de Taylor quadratique, c'est-a-dire que f(uk+d)'f(uk) +dt:rfuk+12 dt:r2fuk:d Si en plus,r2fukest denie positive, l'approximation quadratique a un minimum qui verie r2fukdk=rfuk
Ceci permet de calculer la direction de descentedket de denir l'iteration par u k+1=uk+dk On demontre, comme pour la methode de Newton pour la resolution des equations'(x) = 0, que si le point de departu0est assez voisin dex, et sir2fest denie positive, alors la methode converge versx, et ceci de facon quadratique.Sir2fn'est pas denie positive, cette methode supporte certains amenagements (methode de Newton modiee,
[5, p. 106]). Quand le calcul der2fne peut ^etre fait, on peut aussi remplacerr2fukdans l'approximation de Taylor par une matriceHkqui se calcule iterativement (methode de quasi Newton, [5, p. 116])Remarque
Cette methode est penalisante pour les grands systemes du fait de la necessite de calculerr2f, de la stocker, et de resoudre le systeme r2fukdk=rfuk
5.3 Methode de la metrique variable
- On peut facilement observer que sif(x) =12 kxk2(b;x), la methode de la plus profonde descente converge en une seule iteration. - Qu'il en est de m^eme sifest la fonctionnelle quadratiquef(x) =12 (Ax;x)(b;x); a la condition de remplacer la metriquekxk2parkjxkj2= ((x;x)) = (Ax;x). - L'idee de la metrique variable, appliquee a une fonctionnelle non necessairement quadratique, consiste lors de chaque iteration de la plus profonde descente a choisir une metrique denie par la matrice hessienne de la fonctionnelle, permettant une acceleration de la convergence. Mais il y a un prix a payer. Le calcul du gradient necessite la connaissance d'une base orthogonale; on peut l'obtenir par exemple par orthogonalisation de Grahm-Schmidt. La methode du gradient conjugue reprend cette idee.5.4 Methode du gradient conjugue
([3, p. 194][5, p. 144]) Cette methode presente, sur la methode de Newton, l'avantage de ne pas necessiter le calcul der2f,et sur la methode de la plus profonde descente, celui de denir des directions de descente successives
coherentes.5.4 Methode du gradient conjugue 19
5.4.1 Cas des fonctionnelles quadratiques
f(x) =12 (Ax;x)(b;x); Aetant symetrique denie positive.Description generale
On part deu0quelconque. On suppose qu'a l'etapek, on a calculeu1;:::;uktels querful6= 0; l=0;:::;k. (sinon on a trouve la solution derfx=Axb= 0). On pose
G k= [rfu0;:::;rfuk]: On denituk+1comme le minimum de la restriction defauk+Gk:Ceuk+1existe, est unique. Il se trouve qu'il correspond au minimum defdans une direction calculabledk. Les directionsdksont conjuguees par rapport a la matriceA((Adk;dl) = 0 ). Tout se calcule par des formules iteratives economiques, sans resolution de systeme lineaire. A chaque etape,Gks'accro^t d'une dimension. Au bout d'au plusniterations, la solution est theoriquement trouvee. Numeriquement, avec les erreurs d'arrondi, cela peut ^etre dierent.Formules d'iterations
On part deu0quelconque. On posed0=rf(u0).
Sid0= 0, c'est termine, on ax=u0.
Sinon on pose
0=(rfu0;d0)(Ad0;d0)
et u1=u00d0:
De facon generale, siu1;d1;:::;uk;dksont calcules, alors ou bienrf(uk) = 0, et alors c'est termine, x =uk, ou alors on pose :8>>< >:d k=rfuk+krfukk2krfuk1k2dk1 k=(rfuk;dk)(Adk;dk) u k+1=ukkdk5.4.2 Cas des fonctionnelles non quadratiques
([3, p. 200][5, p. 147]) Le minimum defsur le sous-espaceuk+Gkne peut plus ^etre donne par une formule simple. On calculedkcomme precedemment ou selon une variante (Polak-Ribiere) d k=rfuk+(rfuk;rfuk rfuk1)krfuk1k2dk1 et on obtientken optimisant numeriquement !f(ukdk) La methode ne converge plus en un nombre ni d'iterations.20 Optimisation sans contrainte
Chapitre 6
Optimisation avec contraintes
La diculte du probleme depend de la nature des contraintes. On peut distinguer : . les variables bornees,ixii . les contraintes anes egalites,Cx=b . les contraintes anes inegalites,Cxb . les contraintes convexes ,'i(x) = 0; 'i(x)0; 'iconvexes . les contraintes generales,'i(x) = 0; 'j(x)0 Dans tous les cas on se ramene a la resolution de problemes sans contrainte. Mais la reduction est plus ou moins aisee.Regardons les cas des contraintes inegalites.
6.1 Relations de Kuhn-Tucker
Les relations de Kuhn-Tucker expriment que si la ou les solutions d'un probleme avec contraintes i(x)0 est a l'interieur du domaine des points admissibles, le gradient defs'annule comme c'estle cas pour les problemes sans contrainte, et que si la ou les solutions sont sur le bord, il y a, comme
pour le cas des contraintes egalites, colinearite du gradient defet des gradients des'i.6.1.1 Cas des contraintes non convexes
([3, p. 216])Soitf:
E=Rn!R, derivable enx2Kavec
ouvert, K=fx2 ;'i(x)0;i= 1;:::;mg 6=; i:quotesdbs_dbs5.pdfusesText_9[PDF] Introduction aux microcontrôleurs et à leur assembleur Illustration - Gestion De Projet
[PDF] Introduction aux mondes de l`Islam
[PDF] Introduction aux Neurosciences Cognitives Licence 1ère année de - Avantages Et Compensation
[PDF] Introduction aux nombres complexes - Commercial Et Industriel
[PDF] Introduction aux Objets et à Java - Espèces En Voie De Disparition
[PDF] Introduction aux objets répartis Java RMI - membres - Espèces En Voie De Disparition
[PDF] Introduction aux outils CAO en architecture - Moodle
[PDF] Introduction aux PDA - De L'Automobile Et Des Véhicules
[PDF] Introduction aux pompes à chaleur géothermique
[PDF] Introduction aux principales théories des organisations
[PDF] Introduction aux problèmes philosophiques du langage - Parcs Nationaux
[PDF] Introduction aux réseaux de neurones artificiels
[PDF] INTRODUCTION AUX REVÊTEMENTS DE NYLON Prétraitement du
[PDF] Introduction aux Sciences de la Terre et de l`Univers - Assurance-Vie