[PDF] Optimisation sous contraintes Optimisation sous contraintes. Fabrice Rossi

View - Download Optimisation sous contraintes

Previous PDF

Next PDF

Optimisation sous contraintes

Fabrice Rossi

TELECOM ParisTech

Décembre 2009/Janvier 2010

Plan

Résultats théoriques

Introduction

Existence et unicité

Conditions d"optimalité

Dualité

Second ordre

Algorithmes

Introduction

Gradient

Pénalisation

Dualité

2 / 32F. Rossi

Plan

Résultats théoriques

Introduction

Existence et unicité

Conditions d"optimalité

Dualité

Second ordre

Algorithmes

Introduction

Gradient

Pénalisation

Dualité

3 / 32F. RossiRésultats théoriques

Forme générale

un problème d"optimisation(P)est défini par minimiser surRnJ(x) avechi(x) =0;1ip g j(x)0;1jqrappel de vocabulaire : leshisont lescontraintes d"égalité(notéesh(x) =0) lesgjsont lescontraintes d"inégalité(notéesg(x)0) l"ensemble des contraintesest

C=fx2Rnjhi(x) =0;1ipetgj(x)0;1jqg

ensemble des points admissiblesouréalisables4 / 32F. RossiRésultats théoriques

Forme générale

un problème d"optimisation(P)est défini par minimiser surRnJ(x) avechi(x) =0;1ip g j(x)0;1jqrappel de vocabulaire : leshisont lescontraintes d"égalité(notéesh(x) =0) lesgjsont lescontraintes d"inégalité(notéesg(x)0) l"ensemble des contraintesest

C=fx2Rnjhi(x) =0;1ipetgj(x)0;1jqg

ensemble des points admissiblesouréalisables4 / 32F. RossiRésultats théoriques

Conséquences

les contraintes changent les conditions d"optimalité exemple :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =4x2y20 surR2, on étudieraitrJ=2(x;y)T mais ici, le minimum vaut 4 et est atteint sur le cercle x

2+y2=4 sur lequelrJ6=0mais pas toujours :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =x2+y240

le minimum est atteint en(0;0), avecrJ=0les contraintes doivent donc apparaître dans les conditions

d"optimalité

5 / 32F. RossiRésultats théoriques

Conséquences

les contraintes changent les conditions d"optimalité exemple :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =4x2y20 surR2, on étudieraitrJ=2(x;y)T mais ici, le minimum vaut 4 et est atteint sur le cercle x

2+y2=4 sur lequelrJ6=0mais pas toujours :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =x2+y240

le minimum est atteint en(0;0), avecrJ=0les contraintes doivent donc apparaître dans les conditions

d"optimalité

5 / 32F. RossiRésultats théoriques

Conséquences

les contraintes changent les conditions d"optimalité exemple :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =4x2y20 surR2, on étudieraitrJ=2(x;y)T mais ici, le minimum vaut 4 et est atteint sur le cercle x

2+y2=4 sur lequelrJ6=0mais pas toujours :

J(x;y) =x2+y2à minimiser sous la contrainte

g(x;y) =x2+y240

le minimum est atteint en(0;0), avecrJ=0les contraintes doivent donc apparaître dans les conditions

d"optimalité

5 / 32F. RossiRésultats théoriques

Existence d"un minimum

cas général :(P) :minJ(x);x2 C Rnon suppose :

Jcontinue

etCfermé et non videalors : si :

Cest borné

ou siJest coercitive alors(P)admet au moins une solution6 / 32F. RossiRésultats théoriques

Existence et unicité

remarque : si

C=x2Rnjhi(x) =0;1ipetgj(x)0;1jq

avec deshietgjcontinues, alorsCest fermésiJest strictement convexe etCest convexe, alors(P) admetau plusune solutionproblème convexe :

Jest convexe

leshisont affines lesgjsont convexes et doncCest convexe7 / 32F. RossiRésultats théoriques

Condition du premier ordre

siJest Gâteaux-différentiable enxsolution de(P)et siC est convexe, alors :

8x2 C;hrJ(x);xxi 0remarques :

intuitivement : on ne peut s"éloigner du minimum que dans une direction de montée généralisable : notion de direction admissible

sixest un point intérieur deCalorsrJ(x) =0siJest convexe la condition est nécessaire et suffisante8 / 32F. RossiRésultats théoriques

Égalités et inégalités

Conditions nécessaires non qualifiées

cas particulierhi(x) =0 etgj(x)0 où tout estC1(J inclus)soitxune solution de(P), alors il existe= (1;:::;p) et= (0;1;:::;q)tels que (;)6=0 hi(x) =0;1ip(admissibilité en égalité) gj(x)0;1jq(admissibilité en inégalité) j0;0jq jgj(x) =0;1jq(conditions de complémentarité) et

0rJ(x) +pX

i=1 irhi(x) +qX j=1 jrgj(x) =09 / 32F. RossiRésultats théoriques

Qualification

condition utile si06=0problème dequalification des contr aintes: conditions (locales) sur le problème qui garantissent que 06=0

très nombreuses variantes plus ou moins sophistiquéescontrainte active: gjestactive(ou saturée) enxsi

g j(x) =0;I(x), ensemble des indices des contraintes actives enxrégularité: xest régulier pourgethsi xest admissible lesrhi(x)sont linéairement indépendants il existed6=0 tel quehrhi(x);di=0 pour toutiet hrgj(x);di<0 pour toutj2I(x)(ouhrgj(x);di=0 si g jest affine) régularité de Mangasarian-Fromowitz10 / 32F. RossiRésultats théoriques

Qualification

condition utile si06=0problème dequalification des contr aintes: conditions (locales) sur le problème qui garantissent que 06=0

très nombreuses variantes plus ou moins sophistiquéescontrainte active: gjestactive(ou saturée) enxsi

g j(x) =0;I(x), ensemble des indices des contraintes actives enxrégularité: xest régulier pourgethsi xest admissible lesrhi(x)sont linéairement indépendants il existed6=0 tel quehrhi(x);di=0 pour toutiet hrgj(x);di<0 pour toutj2I(x)(ouhrgj(x);di=0 si g jest affine) régularité de Mangasarian-Fromowitz10 / 32F. RossiRésultats théoriques

Qualification

condition utile si06=0problème dequalification des contr aintes: conditions (locales) sur le problème qui garantissent que 06=0

très nombreuses variantes plus ou moins sophistiquéescontrainte active: gjestactive(ou saturée) enxsi

g j(x) =0;I(x), ensemble des indices des contraintes actives enxrégularité: xest régulier pourgethsi xest admissible lesrhi(x)sont linéairement indépendants il existed6=0 tel quehrhi(x);di=0 pour toutiet hrgj(x);di<0 pour toutj2I(x)(ouhrgj(x);di=0 si g jest affine) régularité de Mangasarian-Fromowitz10 / 32F. RossiRésultats théoriques

Conditions qualifiées

Conditions nécessaires qualifiées du 1er ordre de KKT

Karush, Kuhn et Tucker

)Hypothèses :

J,hetgC1

xsolution de(P) xest régulier pourgethAlors il existe= (1;:::;p)et= (1;:::;q)tels que hi(x) =0;1ip gj(x)0;1jq j0;1jq jgj(x) =0;1jq et rJ(x) +pX i=1 irhi(x) +qX j=1 jrgj(x) =011 / 32F. RossiRésultats théoriques

Cas convexe

si le problème(P)est convexe, les conditions de KKT sont nécessaires et suffisantes en un point xrégulierremarque : le caractère suffisant ne nécessite pas la régularitéconditions de qualification plus simples (deSlater ) : il existe au moins un point strictement admissibleg(x)<012 / 32F. RossiRésultats théoriques

Lagrangien

le

Lag rangien

du prob lème(P)est la fonction

L(x;;) =J(x) +pX

i=1 ihi(x) +qX j=1 jgj(x)quandJ,hetgsontC1les conditions de KKT s"expriment parrxL(x;;) =0lesiet lesjsont lesm ultiplicateursde Lag range associés aux contraintes

13 / 32F. RossiRésultats théoriques

Dualité

fonction duale de Lag range g(;) =infxL(x;;)gest toujours concavepour0 g(;)infx2CJ(x)problème dual(Q)associé au problème primal(P) maximiser surRp+qg(;) avecj0;1jqsaut de dualité: inf x2CJ(x)max0g(;)14 / 32F. RossiRésultats théoriques

Point selle

symétrisation du problème :(P)est équivalent à inf xsup ;0L(x;;)le problème dual(Q)est sup ;0infxL(x;;)point selle : minimal par rapport à une variable, maximal par rapport à l"autre(x;;)est un point selle du Lagrangien si pour tout (x;;)(0 et0) L(x;;)L(x;;)L(x;;)15 / 32F. RossiRésultats théoriques

Point selle

symétrisation du problème :(P)est équivalent à inf xsup ;0L(x;;)le problème dual(Q)est sup ;0infxL(x;;)point selle : minimal par rapport à une variable, maximal par rapport à l"autre(x;;)est un point selle du Lagrangien si pour tout (x;;)(0 et0) L(x;;)L(x;;)L(x;;)15 / 32F. RossiRésultats théoriques

Théorème de dualité

(x;;)est un point selle avec0 ssixest une solution de(P),(;)est une solution de(Q)et le saut de dualité est nulintérêt : pour résoudre le problème, on peut donc chercher un point selle du Lagrangienremarque: un point selle du Lag rangienvér ifieles

conditions de KKT (sans hypothèse autre queJ,hetgC1)si le problème est convexe : point selle,KKT16 / 32F. RossiRésultats théoriques

Théorème de dualité

(x;;)est un point selle avec0 ssixest une solution de(P),(;)est une solution de(Q)et le saut de dualité est nulintérêt : pour résoudre le problème, on peut donc chercher un point selle du Lagrangienremarque: un point selle du Lag rangienvér ifieles

conditions de KKT (sans hypothèse autre queJ,hetgC1)si le problème est convexe : point selle,KKT16 / 32F. RossiRésultats théoriques

Régularité

Condition plus forte que celle de Mangasarian-Fromowitz : xest admissible rhi(x)et lesrgj(x)sont linéairement indépendants pour j2I(x)Contraintesf ortementactiv es: I

+(x) =fjjgj(x) =0 etj>0gsiI(x) =I+(x)on a complémentarité stricte17 / 32F. RossiRésultats théoriques

Conditions nécessaires du 2ème ordre

Hypothèses :

J,hetgC2

xsolution de(P)et fortement régulieralors il existe= (1;:::;p)et= (1;:::;q)tels que les conditions de KKT sont vérifiées et pour toutdvérifiant : hrhi(x);di=0 pour 1ip hrgj(x);di=0 pourj2I+(x) hrgj(x);di 0 pourI(x)nI+(x) on a r2xxL(x;;)d;d018 / 32F. RossiRésultats théoriques

Conditions suffisantes

Hypothèses :

J,hetgC2

(x;;)vérifie les conditions KKTsi la matricer2xxL(x;;)est définie positive sur n d2Rnj hrhi(x);di=0;1i;p et rgj(x);d=0;j2I+(x)o alorsxest un minimum local deJsurC19 / 32F. RossiRésultats théoriques Plan

Résultats théoriques

Introduction

Existence et unicité

Conditions d"optimalité

Dualité

Second ordre

Algorithmes

Introduction

Gradient

Pénalisation

Dualité

20 / 32F. RossiAlgorithmes

Classes d"algorithmes

quelques grandes classes d"algorithmes : gradient projeté : descente de gradient projection surCà chaque étape pénalisation : optimisation sans contrainte deJ+pénalité méthodes extérieures : on ramène progressivement le candidat minimum dansC méthodes intérieures : on relâche progressivement les pénalités programmation quadratique successive : résoudre des

approximations quadratiques du problèmeprincipe sous-jacent : résoudre une série de problèmes

sans contrainte (ou plus simple)

21 / 32F. RossiAlgorithmes

Projection

outil important : projection sur un convexe fermé soitCun convexe fermé et non vide deRnquotesdbs_dbs47.pdfusesText_47

[PDF] optimisation synonyme

[PDF] optimiser la recette

[PDF] Optimiser un cout de fabrication

[PDF] optimiser une recette

[PDF] Optimiser une recette (fonction carré Problèmes du 2nd degré)

[PDF] Optimiser une recette (transmath 2nde chapitre foction carré Problémes du 2nd degré ex 101 P 86)

[PDF] optimiser une recette d'un cinéma ( statistique, équation)

[PDF] optimiser une recette maths seconde

[PDF] Optimum de Pareto

[PDF] optimum de pareto exercice corrigé

[PDF] optimum de pareto graphique

[PDF] option art plastique bac 2017 candidat libre

[PDF] option art plastique bac candidat libre

[PDF] Option au bac

[PDF] option audiovisuel bac