Optimisation linéaire & convexité
II.3 Analyse des problèmes d'optimisation quadratique . On récrit le sous-système des contraintes d'égalité sous la forme (on choisit l'ordre des.
Résolution dun problème quadratique non convexe avec
24 mai 2018 L'optimisation d'une fonction quadratique de variables binaires (BQP) sous contraintes linéaires ou sans contraintes a fait l'objet d'une ...
Résolution dun Problème de Minimisation Quadratique Convexe
C'est une théorie au- tonome de l'optimisation non linéaire dans lequel on minimise (ou maximise) une forme quadratique sous des contraintes linéaires.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- Optimisation
Master MIMSE - Année 2. Optimisation Quadratique. Optimisation quadratique avec contraintes On veut optimiser une fonction sous des contraintes.
Optimisation quadratique
2.5 Fonctionnelle quadratique et contraintes d'égalité affines . On dit qu'un sous-ensemble K de E est convexe si et seulement si
Optimisation et contrôle
8 févr. 2022 3.6.2 Optimisation sous contrainte de modèle et état adjoint . ... Exemple 1.2.3 (optimisation quadratique à contraintes linéaires) Soit A.
MTH8415: Optimisation non linéaire: Applications
Optimisation quadratique. ? Cas particulier de l'optimisation non linéaire sous contraintes linéaires. ? Contraintes linéaires.
Méthodes Numériques : Optimisation
7.3.2 Optimisation quadratique sous contraintes d'inégalités linéaires . . . . . . . . . 64. 8 Pénalisation des contraintes.
Problèmes dOptimisation Non Linéaire avec Contraintes en
28 févr. 2020 Problèmes d'Optimisation Non Linéaire avec Contraintes en ... 8.1 Minimisation d'une fonction quadratique sous contraintes de borne : état.
Introduction à lOptimisation 1
27 avr. 1998 1.4 Projection sur un sous -espace paramétré . ... 2.2 Fonction quadratique avec contraintes d'égalités linéaires .
[PDF] Optimisation quadratique
Si de plus A est définie-positive et C est surjective alors le système linéaire admet une solution unique 5 Page 6 2 6 Contraintes d'inégalité affines Dans
[PDF] Optimisation sous contraintes
Optimisation sous contrainte Formes quadratiques sous contraintes 2 1 2 Soit lv la forme linéaire représentée par le vecteur v suivant lv(x) = ?v
[PDF] Optimisation linéaire & convexité
On appelle problème d'optimisation quadratique sans contrainte tout problème de la forme (II 1) pour lequel la fonction coût est une fonction polynômiale de
[PDF] DRAFT -- DRAFT -- Optimisation Quadratique Optimisation
Optimisation Quadratique Optimisation quadratique sans contraintes Contient la Programmation Linéaire On peut écrire f sous la forme f(x) =
[PDF] Techniques doptimisation
Techniques d'optimisation 25 Max CERF 2018 1 1 3 Modèle quadratique-linéaire Problème avec contraintes égalité Fonction modèle
[PDF] optimisationpdf
différentiabilité opt non différentiable • déterminisme opt stochastique Introduction – p 37 Définition du problème min x?Rn f(x) sous contraintes
[PDF] aspects théoriques numériques et algorithmes
4 Quelques algorithmes pour l'optimisation sans contraintes pour être notamment implémentés sous le logiciel de calcul scientifique Matlab
[PDF] OPTIMISATION SOUS CONTRAINTES
Comment optimiser sous contrainte une fonction à plusieurs variables ? La difficulté réside dans le fait que nous sommes confrontés à plus d'une variable La
[PDF] 34 Optimisation sous contraintes
10 nov 2015 · Avec un tel ensemble de contraintes K si de plus f est linéaire qu'on a affaire ùn problème de “programmation quadratique"
[PDF] Méthodes numériques pour loptimisation non linéaire déterministe
4 4 1 Méthode de Newton avec recherche linéaire 58 5 Algorithmes pour l'optimisation diérentiable sous contrainte
Comment optimiser une fonction sous contrainte ?
Comment optimiser, sous contrainte, une fonction à plusieurs variables ? La difficulté réside dans le fait que nous sommes confrontés à plus d'une variable. La résolution d'un tel problème fait appel à la méthode dite de substitution, le résultat étant la réduction du nombre de variables.Quelles sont les méthodes d'optimisation ?
Techniques de l'optimisation combinatoire
la théorie des graphes (chemin optimal dont le problème du voyageur de commerce)la théorie des jeux (stratégies performantes)la théorie du contrôle, de la régulation et de l'automatique (cf Catégorie:Automatique)l'optimisation multidisciplinaire.Comment on minimise une fonction ?
Produit une liste contenant la valeur minimale de la fonction, le point minimum, le gradient au point minimum ainsi qu'une évaluation de la qualité de l'itération (de 1 à 5). Produit aussi sur demande la matrice hessienne au point minimum: hessian = T. ?l(?, ?) #on change le signe pour minimiser- L'avantage le plus évident mais pourtant essentiel des solveurs d'optimisation est d'améliorer la performance opérationnelle, à savoir la capacité à atteindre vos objectifs avec une utilisation optimale des ressources à votre disposition. En d'autres termes, « faire plus et mieux, en consommant moins de ressources ».
Licence de mathématiques/Licence d"économie
Parcours Math-Éco
2015-2016
Optimisation sous contrainte
Laurent Guillopé
Laboratoire de mathématiques Jean Leray
Département de mathématiques, UFR Sciences et techniquesUniversité de Nantes
www.math.sciences.univ-nantes.fr/˜guillope/l3-oscVersion: 2 mars 2020 1Table des matières
Chapitre 1. Prologue
2Chapitre 2. Optimisation différentiable
51. Fonctions différentiables et différentielles
52. Optimisation sans contrainte
73. Optimisation avec contraintes d"égalité
114. Optimisation avec contraintes d"inégalité
26Chapitre 3. Programmation convexe
351. En guise d"introduction : la moyenne arithmético-géométrique
352. Parties convexes
373. Fonctions convexes
384. Convexité et régularité
445. Fonctions quasi-convexes
516. Programmation convexe
57Chapitre 4. Optimisation vectorielle
621. Ordres de Pareto et optima
622. Scalarisation
65Annexe A. Formes quadratiques
681. Matrices symétriques et formes quadratiques
682. Formes définies et hyperboliques
693. Formes quadratiques sous contraintes
71Annexe. Bibliographie
75Table des figures
76Annexe. Index
77Index général
77Index des noms
782
Table des matières 1
Chapitre 1
Prologue
Étant donnée une fonctionJ, ditefonction d"objectifs,fonction de coûts,fonction d"utilitéou encorefonction de production, à valeurs numériques, l"optimisation consiste en la recherche des valeursminimumou demaximum, soit de manière indifférenciée d"extremum, (1)minx2EJ(x);maxx2EJ(x): ainsi que le ou les points1où la fonctionJatteint ces extrema
argmin x2EJ(x) =fy2E;J(y) = minx2E(J(x))g;argmaxx2EJ(x) = argminx2E(J(x)): SIJest à valeurs vectorielles,i. e.dansRp;p1, le problème1 garde un sens dèsqu"un ordre (processus de comparaison entre vecteurs) a été choisi. Ce thème, associé à
l"économiste Pareto, sera abordé à la fin du cous. La variablexest appelée parfoisvariable de choix, au pluriel sixest considéré comme unn-upletx= (x1;:::;xn)2ERnoù en généralEest un domaine (par- tie ouverte connexe), une adhérence d"un domaine à bord régulier ou des domaines de courbes, surfaces ou hypersurfaces2. La fonctionsJexprime le résultat d"une production,
de charges, de profit, d"utilité,.... Elle est définie sur un ensembleEdont les éléments,
ditsréalisablesouadmissiblesmodélisent desintrants: produits manufacturés, matières premières, unités de travail, capital, charges sociales,... Le domaine de définition de la fonctionJest souvent une partie du quadrantf(x1;:::;xn);xi= 0;i= 1;:::;ngdans les applications économiques. L"étude d"un problème d"optimisation est appeléprogramme, la dénomination depro- grammationétant diversement qualifiée pour signifier un cadre spécifique, avec ses condi- tions et méthodes particulières :programmation linéairequand les fonctions à l"oeuvre sont affines,programmation convexepour des fonctions, ou leurs opposées, convexes,...3. Remarquons tout de suite que la recherche d"un minimum pourJest équivalente à la recherche d"un maximum pour la fonction opposéeJ minx2EJ(x) =maxx2E(J(x));maxx2EJ(x) =minx2E(J(x)):1. Les fonctionsargminetargmaxsont des fonctions à valeur dans l"ensemble des parties du domaine
de définition de la fonction d"objectifs.2. Les exemples rencontrés suffiront à expliquer ces termes : la partieEne sera jamais un ensemble
discret, en bijection dans une partie deZn, ce cours ne s"occupant pas de programmation discrète.3. Le termeprogrammationne réfère pas à la programmation informatique, bien que les ordinateurs
soient largement utilisés de nos jours pour résoudre desprogrammes mathématiques: il vient de l"usage
du motprogrammedans les années 1940 par les forces armées américaines pour établir des horaires de
formation et des choix logistiques, que Dantzig, le créateur de l"algorithme du simplexe en program-
mation linéaire étudiait à l"époque. L"emploi du termeprogrammationavait également un intérêt pour
débloquer des crédits en une époque où la planification devenait une priorité des gouvernements,cf.
21. PROLOGUE 3
Beaucoup d"énoncés ne seront formulés que pour la recherche de minimum. La recherche de bornesinfx2EJ(x);supx2EJ(x)est différente du problème (1) puisque les bornes ne sont pas nécessairement atteintes. Ce cours ne s"interrogera pas sur l"existence de op- tima : celle-ci provient parfois d"un argument de compacité à la Bolzano-Weierstrass ou de coercivité. .Exemples1.1. 1.1 .1 La fonction (x;y;z)!x7+sinhy+sin(z3+x2)admet un minimum sur la boule ferméefk(x;y;z)(1;3;)k 3g. 1.1 .2 La fonction (x;y)2R27!x2+ 3y2+ sin2(x+y3)tend vers+1lorsque k(x;y)k !+1: elle est coercive. Elle admet un minimum surR2. 1.1 .3 Soit Jdéfinie surE= [0;1)parJ(x) = 1=xsix2[1;1)etJ(x) = 1sinon. Alors min x2EJ(x) = 0;maxx2EJ(x) = 1;argmaxJ= [0;1];argminJ=;:/Rappelons quelques définitions
Définition1.1:SoitJdéfinie surEà valeurs réelles. (i) L ep ointx0est unminimum strictdeJsiJ(x0)< J(x)pourx2En fx0g. (ii) L ep ointx0est unminimum globaldeJsiJ(x0)J(x)pourx2E. (iii) L ep ointx0est unminimum local(resp.local strict) deJs"il existe un voisinage Vdex0tel queJ(x0)J(x)pourx2V(resp.J(x0)< J(x)pourx2Vnfx0g). Définition1.2:SoientJ;g1;:::;gn;h1;:::;hpdéfinies surEà valeurs numériques. Le problème d"optimisation avec les contraintes d"égalitégi(x) = 0;i= 1;:::;net les contraintes d"inégalitéhj(x)0;j= 1;:::;pest la recherche du minimum (2)minfJ(x) :x2E;gi(x) = 0;i= 1;:::;n;hj(x)0;j= 1;:::;pg:4Remarque1.1.La contrainte d"égalitég(x) = 0peut s"exprimer comme une double
contrainte d"inégalitég(x)0;g(x)0. Inversement, une contrainte d"inégalité h(x)0peut s"exprimer comme la contrainte d"égalitéh(x)s= 0après introduction de la variable de choix supplémentaire, ditevariable d"écart,ssoumise à la contrainte s0. Les contraintes (2) peuvent s"exprimer comme une seule contrainte numériqueG(x) = 0avec
G(x) =nX
i=1jgi(x)j+pX j=1jhj(x)s2jj qui a l"inconvénient d"utiliser une fonction non différentiable sur l"ensemble des points admissiblesG= 0ouG(x) =nX
i=1g i(x)2+pX j=1(hj(x)s2j)2 qui a celui d"une différentielle non régulière surG= 0(oùdGs"annule).5 Ces notes sont consacrées donc à étudier la recherche de minimum (valeur ou point l"atteignant) telle que posée de manière générale dans ( 2 ) et dont seuls quelques cas par- ticuliers seront abordés : programmes sans ou avec contraintes, fonctionJdifférentiable, convexe,.... L"illustration graphique en basse dimension (une ou deux variables de décision) per- met de préciser ou d"anticiper certains résultats analytiques, heuristiques ou approchés :4 1. PROLOGUE
siJ:E(R2)!Rest une fonction de deux variables, on peut considérer (cf.Figure I.1 des lignes de niv eau4Lv=fJ(x;y) =v;(x;y)2Egpour un ensemble de valeurs
v1;:::;vN,
le graphe GJ=f(x;y;J(x;y))2R3;(x;y)2Egde la fonction qui est une surface dansR3,sur lesquels on peut repérer des extrema, points selle, voire les points critiques.Figure I.1.Les courbes de niveau de la fonction d"objectifsJ(x;y) =
x3+y36xysur le carré[1;3]2et la surface de son graphe.
Le logicielsagepermet aisément de faire certains tracés ou des calculs algébriques formels (par ex. le déterminant ( 18 )); le logicielR(qu"on peut appeler d"ailleurs à partir desage) est d"un usage aisé, avec un ensemble riche de bibliothèques en calcul statistique et numérique. Ces deux outils, développés par la communauté scientifique, sont librement utilisables, avec des versions sur les différents systèmes communs (linux,windows,MacOsnotamment) : à utiliser sans modération!4. Les courbes de niveau d"une fonction de production sont appeléesisoquantes, celles d"une fonction
d"utilitécourbes d"indifférencesChapitre 2
Optimisation différentiable
1. Fonctions différentiables et différentielles
Dans ce chapitre, les fonctions sont toujours supposées différentiables à tout ordre. Si fest définie surURnet à valeurs réelles, sa différentielle enx2Uest l"application linéaire notéedfx1 f(x+h) =f(x) +dfx(h) +khk"(h): Cette différentielle est représentée par le vecteur gradient 2 rfx=rf(x) = (@x1f(x);:::;@xnf(x)) avec 3 df x(h) =dfx(h1;:::;hn) =@x1f(x)h1+:::+@xnf(x)hn=hrf(x);hiRn Le produit scalaireh;iRnest le produit canonique surRn, qui sera le plus souvent noté simplementh;i. En termes matriciels, l"expressiondfx(h)s"obtient comme le produit matriciel du vecteur ligne(@x1f(x);:::;@xnf(x))des coordonnées de la formedxfdans la base(dx1;:::;dxn), alors que l"expressionhrxf;hiest le produit scalaireXTYdes deux vecteurs colonneX;Ydes coordonnées des vecteursrxfethresp. Définition2.1:Soitf:x2U(Rn7!f(x)2Rdifférentiable de classeC2. La matrice hessienne4Hess(f)xdefau pointxest la matrice5
Hess xf=@2ijf(x)=0211f(x)::: @21nf(x)......
2n1f(x)::: @2nnf(x)1
A des dérivées partielles secondes. Il lui est associée6la forme quadratique
h= (h1;:::;hn)2Rn7!Hess(f)x[h] =nX i;j=1@2ijf(x)hihj
.Exemples2.1.1. ... oudxf,df(x),f0(x);dxf(x0),Jf(x): les notations varient, parfois sans raison véritable autre
que certaines habitudes, parfois en insistant sur la variable de dérivation ou sur l"évaluation de la différen-
tielle en un point. Les mêmes variations ont lieu pour la hessienne :Hessxf,Hessf(x),...2. En statistique, le gradient de la log-vraisemblance est appelé lescore.
3.@xfdénote la dérivée partielle@f@x
4. On ne confondra pas la matrice hessienne d"une fonctionf:2URn!Rde la jacobienne
JF(x)d"une transformationF:x2URn7!F(x) = (F1(x);:::;Fp(x))2Rpdéfinie parJF(x) =@xjFi(x): c"est la matrice de la différentielledF(x)relativement aux bases canoniques deRnetRp
resp.. SiF=rf, alorsdFs"identifie à la matrice (symétrique)Hessf.5. En statistique, l"opposée de la hessienne de la log-vraisemblance est appeléeinformation observée.
6. À la matriceA= (aij)carrée d"ordrenet symétrique correspond la forme quadratiqueqA:x2
R n7! hAx;xi 2R. Cette correspondance est bijective vu2aij=qA(ei+ej)qA(ei)qA(ej)où la famille (ei)est la base canonique deRn. 56 2. OPTIMISATION DIFFÉRENTIABLE
2.1 .1 La hessienne de la fonction p olynomialeP(x;y) =ax2+2bxy+cy2+dx+ey+f est la matrice (indépendante dex;y)Hess(f)(x;y)= 2a b
b c 2.1 .2 Soit `vla forme linéaire représentée par le vecteurvsuivant`v(x) =hv;xiet q Ala forme quadratique associée à la matrice symétriqueA. r`v(x) =v;Hess`v(x) = 0;rqA(x) =Ax;HessqA(x) = 2A: On établit ces formules soit en prenant des coordonnées et effectuant le calcul de dérivées partielles, soit en identifiant les termes développements de`v(x+h)et q A(x+h)à ceux du développement de Taylor (3) rappelé ci-dessous./Rappelons la formule de Taylor à l"ordre 2 :
Proposition2.1:Soitx2Rn,Uxun ouvert contenantxetf:Ux7!Rdifféren- tiable. Alors (3)f(x+h) =f(x) +hrfx;hi+Hessfx[h]2 +khk2"(h); x+h2Ux avec"(h)!0lorsqueh!0. SoitH:R!Rstrictement croissante et :V(Rn)!Rnune bijection deV surU= (V). SieJ=HJ, les deux programmesminv2VeJ(v)etminu2UJ(u) sont équivalents, avecminu2UJ(u) = minv2VeJ(v)etargminJ= (argmineJ). Comme exemple, on peut citer diverses fonctions dérivées de la fonction de Cobb-Douglas :Q iuii,P iiloguietP iivi. Le lemme suivant sert à établir l"équivalence de certains critères d"optimisation vis a vis de ces compositions de fonctions.Lemme2.1:SoitH:R!R, :V(Rm)!Rn,J:U(Rn)!R,eJ=HJ,
ep2Vetp= (ep). Alors d epeJ=H0(J(p))dpJdep r eJ(ep) =H0(J(p))T0(ep)[rJ(p)]; Hess epeJ=H00(J(p))(dpJdep)2+H0(J(p))HesspJ[dep] +J0(p)(d00ep[ev]): En particulier, sip= (ep)est un point critique deJ,epest aussi un point critique deeJ avec relation entre les hessiennes Hess epeJ[ev] =H0(J(p))HesspJ[dep(ev)];ev2Rn de telle sorte que siH;sont des applications inversibles au voisinage deej=J(p);ep resp., alors les hessiennesSign(H0(J(p))HessepeJetHesspJont même indice. Démonstration.La matrice hessienne et le gradient sont déterminés par le développe- ment de Taylor à l"ordre 2. Ainsi (ep+ev) = (ep) +dep(ev) +d00ep[ev]2 +o(kevk2)2. OPTIMISATION SANS CONTRAINTE 7
puis (J)(ep+ev) =J (ep) +dep(ev) +d00ep[ev]2 +o(kevk2) =J((ep)) +J0((ep)) d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 +o(kevk2) et donc eJ(ep+ev) =h(J(ep+ev))
=hJ((ep)) +J0((ep))
d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 +o(kevk2) eJ(ep) +h0(J(p)) J 0(p) d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 h00(J(p))[J0(p)[dep(ev)]]22 +o(kevk2) eJ(ep) +h0(J(p))J0(p)(dep(ev)) h0(J(p))J0(p)d00ep[ev] + HesspJ[dep(ev)]+h00(J(p))[J0(p)(dep(ev))22 +o(kevk2) et donc les formules sur le gradient et le hessien de la fonction eJ.2. Optimisation sans contrainte
Un problème d"optimisation sans contrainteconsidéré ici est du type inf x2 J(x) où est un ouvert7d"un espace vectoriel, en général de dimension finie, etJune fonction (au moins continue, de classeC1en général). Définition2.2:SoitJ:U(Rn)7!Rdifférentiable. Le pointx2Uest unpoint critiquedeJsidJx= 0ou de manière équivalenterJ(x) = 0. Théorème2.1 (Euler-Fermat):SiJ:U(Rn)!Rest minimum enx2U, alorsx est point critique deJ. Démonstration.Sixest minimum deJ, alors, pourh2RNett >0avecthassez petitJ(x+th)J(x)t
0; d"où dJ x(h) +khk"(th)0 et doncdJx(h)0en faisantt!0. S"ensuit aussidJx(h) =dJx(h)0et donc dJ x(h) = 0pour tout vecteurh, soit la nullité de la différentielledJx. .Exemples2.2.7. L"ouvert peut être défini par une fonctionJsous la forme =fF >0g: cette inégalité," ouverte », n"est pas considérée comme une contrainte, au contraire des inégalités larges des sections
suivantes.8 2. OPTIMISATION DIFFÉRENTIABLE
2.2 .1 La fonction Jdéfinie parJ(x;y) =x2y2a0comme point critique : l"origine0est un minimum global strict deJ+, alors queJn"a ni minimum, ni maximum
(local ou global). 2.2 .2 La fonction J(x;y) = cosx+y2a comme gradientrJ(x;y) = (sinx;2y): sespoints critiques sont les(k;0)pourk2Z.Figure II.1.Les courbes de niveau de la fonction d"objectifsJ(x;y) =
cosx+y2.Théorème2.2:SoitJ:U(Rn)!Rcritique enx.
(i) Sixest un minimum (maximum resp.) local deJ, la hessienneHess(J)xest une forme quadratique positive8(négative resp.).
(ii) Si la hessienneHess(J)xest une forme quadratique définie positive (négative resp.) etxpoint critique deJ, alorsxest un minimum (maximum resp.) local deJ. .Exemples2.3. 2.3 .1 Soit la fonction d"ob jectifJdéfinie parJ(x;y) =x2y4: avec (unique) point critiquex= (0;0)la fonctionJa au pointx= (0;0)a comme hessienneHessJ(x) =1 0
01 , définie positive pourJ+et de signature(1;1)pourJ. Le pointxest minimum global deJ+, point selle pourJ. 2.3 .2 Reprenan tla fonction J(x;y) = cosx+y2de l"exemple précédent, on a au voisinage demk= (k;0)aveck2Z,J(k+u;y) =y2+ (1)kcosu= (1)k+y2(1)ku22
+ (u2+y2)"(juj+jyj): Sikest impair, le pointmkest un minimum local strict, alors que sikest pair, c"est un point de minimum local le long de la verticalef(k;y);y2("1;"1)g et de maximum local le long de l"horizontalef(k+u;0);u2("2;"2)g,i. e. m kest un point selle9. On peut éviter le développement limité en introduisant le changement de variableu7!t(u) =p2sin(u=2)pouruvoisin de0(et aussit) de telle sorte que, pour(u;y)et(t;y)proches de(0;0),J(k+u;y) =y2+ (1)kcosu=y2+ (1)k(12sin2(u=2)) =J(mk) +y2+ (1)kt(u)28. On parle parfois de matricesemi-définiepositive ousemi-définienégative.
9. Le point critiquexde la fonctionUen est un point selle si en restriction à un arc issu dexla
fonctionUcroît alors que suivant d"autres arcs issus dexelle décroît.2. OPTIMISATION SANS CONTRAINTE 9
avec un minimum local sikpair et un point selle sikimpair. En conclusion, cette fonctionJn"est pas bornée supérieurement (faire tendrey! 1), a une infinité de minima globaux constituant la partie((1+2Z);0), aucun autre minimum local et pas plus de maxima locaux, la partie(2Z;0)contenant tous les autres points critiques, chacun de type selle. 2.3 .3 Soit Aune matrice symétrique d"ordren,bun vecteur deRnetcune constante.La fonctionJdéfinie par
J(x) =12
hAx;xi+hb;xi+c; x2Rn a comme différentielledJx(h) =hAx;hi+hb;hisoitrJx=Ax+bet hessienne Hess(J)x=A. Les points critiquesxdeJsont caractérisés donc par l"équation Ax+b= 0: siAest inversible,Ja un unique point critiquex=A1b.D"après le théorème
2.2 , c"est un minimum local siAest définie positive. On peut même dans ce cas montrer que c"est un minimum global : en effet, pour h2Rn,J(x+h) =12
hA(x+h);x+hi+hb;x+hi+c 12 hAx;xi+hAx;hi+12 hAh;hi+hb;x+hi+c 12 hAx;xi+hb;xi+c+12 hAh;hi+hAx+b;hi =J(x) +12 hAh;hi et le pointxest clairement un minimum global strict. SiAest définie négative, x est pareillement un maximum global strict. Le cas général (Anon inversible, avec des valeurs propres positives et négatives) nécessite des développements plusétoffés./
Démonstration du théorème
2.2 .Soitxminimum deJ. Vu querJxest nul, la formule de Taylor à l"ordre 2 s"écrit, pourhdonné ettassez petit0J(x+th)J(x) =Hess(J)x[th]2
+kthk2"(th) =t2Hess(J)x[h]2 +khk2"(th) soit, en divisant part2>0,0Hess(J)x[h]2
+khk2"(th) et par suiteHess(J)x[h])0pour touthen faisant tendret!0: voilà la première assertion démontrée. Pour la seconde, la matrice hessienne étant définie positive, il existe10une constante
C=Cxtelle que
Hess(J)x[h]2Ckhk2; h2Rn10. Pour la matriceA= HessJx, il existe une base orthonormée(vi)de vecteurs propres avec valeurs
propres associéesiresp., toutes strictement positives. Soitx=x1v1++xnvnla décomposition de xdans la base orthonormée(vi):hAx;xi=P i;jxixjhAvi;vji=P ix2iiinfiikxk2: on peut donc prendreC= infii.10 2. OPTIMISATION DIFFÉRENTIABLE
Ainsi,
J(x+h)J(x) =Hess(J)x[h]2
+khk2"(h)(C j"(h)j)khk2C2 khk2>0 pourhnon nul suffisamment petit de telle sorte quej"(h)j C=2: on a bien montré que xétait un minimum local strict deJ.
4Remarque2.1.Une autre condition suffisante de minimum pour un point critique
est la positivité locale : il existe une bouleB(x;)sur laquelleHessxJest positive. Cela résulte de la formule de Taylor avec reste intégral 11J(x+h) =J(x) +hrxJ(x);hi+Z
1 0J(1t)Hessx+thJ[h]dt
et donnexcomme minimum local (non nécessairement strict). Cet énoncé s"applique bien à la fonctionJ(x;y) =x2+y4, dont la hessienne vautHessx;yJ=2 00 12y2
.5 Une caractérisation du caractère (défini) positif ou négatif d"une matriceAest don- née par les signes des mineurs principaux dominants deA(cf.Appendice 1) : Proposition2.2:SoitAmatrice (réelle) symétrique d"ordren. (i) La forme quadratiqueqAest définie positive (resp. négative) si et seulement si lesnmineurs principaux dominantsAm= (aij)1i;jm,m= 1;:::;nsont strictement positifs (alternent de signe, avecA1négatif resp.). (ii) la formeqAest positive (négative resp.) si et seulement si chaque déterminant d m= detAm;m= 1;:::;n;2Snest positif ou nul (du signe de(1)mresp.) pour m= 1;:::;n. Iciest une permutation de[1;n]etAest obtenue deApar permutation des lignes et des colonnes deA(resp. des colonnes deB) suivant. .Exemple2.4.Pour un programme avec fonction d"objectifsJet deux variables de décision, la condition pour une hessienne définie négative induisant un maximum local strictxest donc 2 u2J <0;@2 u2J @2uvJquotesdbs_dbs8.pdfusesText_14[PDF] fonction convexe plusieurs variables
[PDF] modélisation et simulation d'un moteur ? courant continu matlab
[PDF] modélisation mcc
[PDF] simulation mcc simulink
[PDF] asservissement et regulation de vitesse d'un moteur a courant continu
[PDF] modélisation d'un moteur ? courant continu
[PDF] equation differentielle moteur courant continu
[PDF] schéma bloc moteur ? courant continu
[PDF] commande pid d'un moteur ? courant continu pdf
[PDF] modélisation machine asynchrone simulink
[PDF] onduleur triphasé matlab
[PDF] cours de modélisation financière sous excel
[PDF] modélisation financière pdf
[PDF] fiche de lecture les misérables victor hugo pdf