[PDF] [PDF] Fiches doptimisation quadratique

[PDF] 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 27

[PDF] Convexité en optimisation, convexité forte

Si f est une fonction convexe définie sur un ouvert convexe Ω de V , alors f est continue sur Ω et Exemple 3 Convexité d'une fonction quadratique

[PDF] Sur la programmation quadratique convexe - Université de Bejaia

3 Méthodes de résolution en programmation quadratique convexe 22 concernant les fonction quadratiques,ainsi que la notion de la convexité Le deuxième 

[PDF] Fiches doptimisation 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 Les assertions suivantes 

[PDF] THESE Reformulations quadratiques convexes pour - Cedric-Cnam

L'optimisation d'une fonction quadratique de variables 0-1 sous contraintes convexe en un problème d'optimisation quadratique en 0-1 dont la fonction

[PDF] Fonctions convexes et conjuguées

Les fonctions affines de IRn sont bien sûr convexes (elles sont aussi concaves) Comme on le vérifiera plus loin, les fonctions quadratiques convexes de IRn 

[PDF] TP 1: Minimisation de fonctions quadratiques

En déduire que f est strictement convexe si et seulement si Q est définie positive 4 Soit Q une matrice définie positive (a) Montrer que la fonction qQ : x ↦→ 〈x  

[PDF] Cours Optimisation Mathématique - ENSIIE

Minimisation d'une fonction convexe 1 2 1 2 1 Matrice réelle symétrique et forme quadratique Définition forme quadratique indépendante de yı et de y2

[PDF] fonction racine carrée exercices corrigés

[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 agrosystème

[PDF] fonctionnement d'un groupe electrogene pdf

[PDF] fonctionnement d'un hacheur

[PDF] fonctionnement d'un sprinkler

Optimisation quadratique

Table des matières

1 Existence et unicité d"un minimum 1

1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.4 Convexité et unicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.4.1 Projection sur un convexe fermé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4.2 Propriété des fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 Conditions d"optimalité3

2.1 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.3 Contraintes d"égalité affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.4 Le lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.5 Fonctionnelle quadratique et contraintes d"égalité affines . . . . . . . . . . . . . . . . . . . . . . . .

4

2.6 Contraintes d"inégalité affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3 Algorithmes pour problèmes sans contraintes, fonctionnelle quadratique 5

3.1 Taux et vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2 Méthode de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2.1 Pas optimal - fonctionnelle quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2.2 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2.3 Gradient à pas fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2.4 Méthode du gradient à pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2.5 Gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2.6 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

4 Algorithme pour les problèmes contraints 9

4.1 Méthode du gradient projeté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.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 si

Dé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 global

Dans 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 convexes

Thé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écessairement

8v2K,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 localdeJsur

Ksi, 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é affines

La 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.5

2.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=0

De plus siJestconvexe, alors ceci est une conditionsuffisantede minimalité.3 Algorithmes pour problèmes sans contraintes, fonctionnelle quadra-

tique

On é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=b

Les 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 A1

Dé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.6

3.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)Principe

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,dki

3.2.2 RelaxationDéfinition :

d

0=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