DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- Optimisation
Fonction quadratique = polynôme de degré 2 Fonctions quadratiques à une variable ... Une fonction f définie sur S convexe est convexe si pour toute.
Convexité en optimisation convexité forte
fonction convexe définie sur ? ? V est différentiable presque partout (au sens de la mesure Exemple 3 Convexité d'une fonction quadratique.
COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin
2.2.2 Exemples des fonctions convexes strictement convexes et fortement convexes . 3.1.2 Cas particulier des fonctions quadratiques .
Résolution dun problème quadratique non convexe avec
24 mai 2018 2.2.3 Cas des fonctions convexes : conditions nécessaires et suffi- ... matrice Hessienne d'une fonction quadratique est indépendante du ...
MAT 2410: Optimisation
Soit A une matrice symétrique définie-positive de format n × n. Proposition: La fonction quadratique f (x)=(Ax x) est strictement convexe. Preuve: Posons x2.
La programmation quadratique en variables entières
f : Rn ? R deux fois différentiable dans Rn et soit u un minimum local de f
Optimisation en nombres entiers de fonctions quadratiques non
o`u la fonction objectif est soit linéaire soit quadratique et convexe. Nous aborderons donc différentes méthodes de résolution de cette catégorie de.
THESE Reformulations quadratiques convexes pour la
reformulation de ce programme par un programme quadratique en variables. 0-1 dont la fonction objectif est convexe les contraintes restant linéaires.
Optimisation quadratique
1.4.2 Propriété des fonctions convexes. Théorème : Soit J une fonctionnelle différentiable sur un sous-ensemble K convexe non vide.
Cours doptimisation ENSAI Rennes
15 mars 2019 1.4.3 Propriétés d'une fonction convexe . ... 6.6 Fonction quadratique et contraintes linéaires d'égalité . . . . . 40.
Optimisation quadratique
Table des matières
1 Existence et unicité d"un minimum 1
1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.4 Convexité et unicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.4.1 Projection sur un convexe fermé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21.4.2 Propriété des fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22 Conditions d"optimalité3
2.1 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32.2 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32.3 Contraintes d"égalité affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42.4 Le lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42.5 Fonctionnelle quadratique et contraintes d"égalité affines . . . . . . . . . . . . . . . . . . . . . . . .
42.6 Contraintes d"inégalité affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53 Algorithmes pour problèmes sans contraintes, fonctionnelle quadratique 5
3.1 Taux et vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2 Méthode de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2.1 Pas optimal - fonctionnelle quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2.2 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2.3 Gradient à pas fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73.2.4 Méthode du gradient à pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73.2.5 Gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73.2.6 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84 Algorithme pour les problèmes contraints 9
4.1 Méthode du gradient projeté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94.2 Méthode d"UZAWA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9
1 Existence et unicité d"un minimum
1.1 Notations
On considèreEl"espace vectorielRn,kun sous-ensemble non vide deEetJunefonctionnelle continuedéfinie
surKà valeur dansR.1.2 ProblèmeTrouveru2K, tel queJ(u) =infv2KJ(v).
1.3 ExistenceDéfinition : Minimum local-global
ÐÐÐÐÐÐÐÐÐÐÐu2Kest unpoint de minimum localdeJsurKsi, et seulement si
u2Kest unminimum globaldeJsurKsi, et seulement siDéfinition : Suite minimisante
ÐÐÐÐÐOn dit qu"une suite(uk)k2Nd"éléments deKest unesuite minimisantesi et seulement si
lim k!+1J(uk) =infv2KJ(v)Théorème : (rappel) SiKestcompactetJ continuesurK, alorsJatteint sesextrema.Définition : ÐÐÐÐÐOn dit qu"un fonctionnelleJestinfine à l"infinisi, et seulement si : pour toute suite(un)n2Kn, limn!+1 vn = +1 )limn!+1J(vn) = +1Théorème : Existence d"un minimum globalDans le cas oùE=Rn, siKest un fermé, et siJestcontinueetinfinie à l"infinidansK, alors elle admet
un minimum globalsurK. De plus, de toute suite minimisante, on peut extraire unesous-suitequi converge vers un point de minimum.1.4 Convexité et unicitéDéfinition : Ensemble convexe
ÐÐÐÐÐÐOn dit qu"un sous-ensembleKdeEest convexe si, et seulement si, pour tout couple d"éléments(u,v),
le segment[u,v]est inclus dansK:8(u,v)2K2,8t2[0, 1],tv+(1t)u2KDéfinition : Fonctionnelle convexe
ÐÐÐÐÐÐÐÐÐÐSoitJune fonctionnelle définie sur un sous-ensemble convexe non videKdeE, à valeurs dansR. On
dit queJestconvexesi et seulement si :Dans le cas d"une inégalité stricte, on dit que la fonctionnelle eststrictementconvexe.uvθu+(1-θ)vθJ(u)+(1-θ)J(v)J(θu+(1-θ)v)2
Propriété
SoitJune fonctionnelle convexe définie sur un convexe non videK: Êsiuetvsont deux points de minimum locaux, alorsJ(u) =J(v); Ësi en plus,Jest strictement convexe alorsu=v.Théorème : SoitJune fonctionnelle convexe définie sur un convexe non videKdeE: Êtout point de minimum local est un point de minimum globale;Ësi de plusJeststrictementconvexe, le point de minimum, s"il exite, estunique.1.4.1 Projection sur un convexe fermé
Définition :
ÐÐÐÐÐPour toutwdeE, on définit sa projection sur un convexe ferméK PK(w)comme l"élémentutel que :
kwuk=minv2KkwvkPropriété SiKest un convexe fermé, alors tout élémentwdeEadmet une projectionunique PK(w)surK. DE lus l"applicationw7!PK(w)estcontractante.1.4.2 Propriété des fonctions convexesThéorème :
SoitJune fonctionnelle différentiable sur un sous-ensembleK convexe non vide.Les assertions suivantes sont équivalentes :
ÊJestconvexesurK.
Ë8(u,v)2K2,u6=v:
J(v)¾J(u)+hrJ(u),vui.
Ì8(u,v)2K2,u6=v:
hrJ(u)rJ(v),uvi¾0.Pour la stricte convexité, on a des inégalité strictes.Théorème : classeC2SoitJune fonctionnelle deEdansRde classeC2. AlorsJestconvexesi, et seulement si,
2.1 Cas général
3 Définition : Cône des directions admissiblesÐÐÐSoitKun sous-ensemble non vide deE, etvun point deK. On appelle cône des directions admissibles
l"ensembleTKdes tangentes envaux chemins inclus dansKet commençants env.Théorème : SoientKun sous-ensemble non vide deE,uun point deKetJune fonctionnelle deKdansR. On suppose queJest FRECHET-différentiableenu. Siuest un point de minimum local deJsurK, on a nécessairement :8w2 TK,hrJ(u),wi¾0Propriété
SiK=Eou si le minimumuest intérieur àKalors l"inéquation ci-dessus devient : rJ(u) =02.2 Cas convexe Ici onse place dans le cas oùKest convexe.Théorème : Inéquation d"Euler SoientKun sous-ensemble convexe non vide deE,uun point deKetJune fonctionnelle deKdans R. On suppose queJest différentiable enu. Siuest unpoint de minimum localdeJsurK, on a nécessairement8v2K,hrJ(u),vui¾0Théorème :JconvexeSoientKun sous-ensemble convexe non vide deE,uun point deKetJune fonctionnelle deKdans
R. On suppose queJestconvexeet différentiable enu. Siuest unpoint de minimum localdeJsurKsi, et seulement si
8v2K,hrJ(u),vui¾02.3 Contraintes d"égalité affines
On suppose ici que l"ensembleKest défini par :
K=v2RnCv=f
oùCest une matricepnetfun élément deRp(on supposeK6=0). On remarque queKest unconvexe non vide.Théorème : (Karush, Kuhn et Tucker) SoitC2 Mp,n(R)etf2Rp,Kle sous-espace défini parK=fv2Rn=Cv=fg,uun point deKetJ une fonctionnelle différentiable enu. Siuest un point deminimum localdeJsurK, on anécessairement:92Rp,rJ(u)+tC=0
Cuf=04
2.4 Le lagrangien
Définition : Le lagrangien
ÐÐÐÐÐÐÐÐOn définit la fonctionnelle (appelée lelagrangiendu système) :
8(v,)2eRp,L(v,u) =J(v)+
Cvf Les élémentdeRpsont appelés lesmultiplicateurs de LAGRANGE.Propriété SoitC2 Mp,n(R)etf2Rp,Kle sous-espace défini parK=fv2Rn=Cv=fg,uun point deKetJ une fonctionnelle différentiable enu. Siuest un point deminimum localdeJsurK, on anécessairement:92Rp, tel quervL(u,) =0
r L(u,) =02.5 Fonctionnelle quadratique et contraintes d"égalité affinesLa fonctionnelle est ici quadratique env2Rn:
8v2Rn,J(v) =12
hAv,vihb,vi+c oùAest une matricasymétriquedeRnn,bun vecteur deRnetc2R. On considère ses variations sur l"espace affine :K=v2RpCv=f
oùC2Rpn, etfun éléments deRp. D"après les théorèmes précédents, on a siuest un point de minimum deJsurK:92Rp, tel queAu+tC=b
Cu=fPropriété
SoitJetKdéfinis ci-dessus. Siuest un point de minimum deJsurK, alors il existe2Rptel que le couple(u,)deRnRpsoit solution du syste=ème linéaire : AtC C0 u =b fThéorème : SiAestsymétrique positive, le vecteuruest un point de minimum deJsurKsi, et seulement si, il existe un élémetdeRptel que le couple(u,)soit solution de : AtC C0 u =b f Si de plusAestdéfinie-positiveetCestsurjectivealors le système linéaire admet unesolution unique.52.6 Contraintes d"inégalité affines
Dans cette section on considère que l"ensemble descontraintesKest donné par : On considèreKdéfini ci-dessus etJune fonctionnelledifférentiablesurEdansR. Siu2Kest un minimum local deJsurKalors :92Rp,¾0,8
:rJ(u)+tC=0 iCuf i=0De plus siJestconvexe, alors ceci est une conditionsuffisantede minimalité.3 Algorithmes pour problèmes sans contraintes, fonctionnelle quadra-
tiqueOn étudie ici les algorithmes qui permettent de calculernumériquementla solution du problème de minimi-
sation :Trouveru2Rntel queJ(u) =minv2RnJ(v). Avec ici,Jle fonctionnelle qui àvassocieJ(v) =12 hAv,vi hb,vi, avecAune matricesymétrique définie- positivedeRnnetbun vecteur quelconque deRn. Dans ce cas, la solution existe et estunique, et elle vérifie le système linéaire : Au=bLes algorithmes suivants consistent tous à choisir une condition initialeu0puis à construire une suite(uk)k¾1.
Ces algorithmes doivent vérifier les deux propriétés suivantes :La convergence de la suite 5uk)est assurée quel que soit le vecteur initiale.
La convergence doit être " suffisament rapide ».3.1 Taux et vitesse de convergenceDéfinition :
ÐÐÐÐÐÐÐSoitk.kune norme matricielleinduite. On appelleconditionnementd"une matrice réelleinversible
A2Rnn,relatif à cette norme, la valeur définie par : cond(A) =kAk A1Définition :
ÐÐÐÐÐSoit une méthode numérique produisant une suite d"itérés(uk). SoitC>0 la pluspetiteconstante
telle que, pour toutk¾0 : uk+1u uku .Cest appelétaux de convergence. On appellera vitesse de convergenceR=logC.63.2 Méthode de descente
Supposons l"itéréukconnu, onchoisitune direction dite dedescentedk6=0, et unpas de descentek. On construit alors l"itéréuk+1par la formule : u k+1=uk+kdk Remarque :Le choix deketdkse fait de manière à assurer queJ(uk+1)3.2.1 Pas optimal - fonctionnelle quadratique
Dans le cas où la fonctionnelle estquadratique, on obtient une formule du pas optimal : k=hrJ(uk),dkihAdk,dki3.2.2 RelaxationDéfinition :
d0=e1,...,dn=e1,..., etc. et ainsi de suite. On choisit lepas optimaldéfini ci dessus. L"algorithme est
alors :Soitl¾0, on choisituo2Rnet une tolérance.Pourk=nl+i1, on prend :
Êdk=ei
Ëk=hrJ(uk),dkihAdk,dki
Ìuk+1=uk+keiPropriété
SiAestsymétrique définie positivealors la méthode de relaxation estconvergente.3.2.3 Gradient à pas fixe
Définition :
ÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐIci, on cherche la direction dans laquelle la convergence sera la plus rapide.
Soitu02Rnune condition initiale,un pas fixe.
quotesdbs_dbs1.pdfusesText_1[PDF] fonction ressources humaines dans l'entreprise
[PDF] fonction ressources humaines définition
[PDF] fonction ressources humaines pdf
[PDF] fonction statistique excel
[PDF] fonction variable complexe exercices corrigés
[PDF] fonction varoma thermomix tm5
[PDF] fonction word 2010
[PDF] fonctionnement boite de vitesse automatique pdf
[PDF] fonctionnement clé token
[PDF] fonctionnement d internet schéma
[PDF] fonctionnement d'un groupe electrogene pdf
[PDF] fonctionnement d'un hacheur
[PDF] fonctionnement d'un sprinkler
[PDF] fonctionnement d'une banque pdf