Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Optimisation sous contraintes Fabrice Rossi TELECOM ParisTech Décembre 2009/Jan

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 / 32 F. Rossi Plan Résultats théoriques Introduction Existence et unicité Conditions d’optimalité Dualité Second ordre Algorithmes Introduction Gradient Pénalisation Dualité 3 / 32 F. Rossi Résultats théoriques Forme générale un problème d’optimisation (P) est déﬁni par minimiser sur Rn J(x) avec hi(x) = 0 , 1 ≤i ≤p gj(x) ≤0 , 1 ≤j ≤q 4 / 32 F. Rossi Résultats théoriques Forme générale un problème d’optimisation (P) est déﬁni par minimiser sur Rn J(x) avec hi(x) = 0 , 1 ≤i ≤p gj(x) ≤0 , 1 ≤j ≤q rappel de vocabulaire : • les hi sont les contraintes d’égalité (notées h(x) = 0) • les gj sont les contraintes d’inégalité (notées g(x) ≤0) • l’ensemble des contraintes est C = {x ∈Rn|hi(x) = 0 , 1 ≤i ≤p et gj(x) ≤0 , 1 ≤j ≤q} ensemble des points admissibles ou réalisables 4 / 32 F. Rossi Ré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) = 4 −x2 −y2 ≤0 • sur R2, on étudierait ∇J = 2(x, y)T • mais ici, le minimum vaut 4 et est atteint sur le cercle x2 + y2 = 4 sur lequel ∇J ̸= 0 5 / 32 F. Rossi Ré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) = 4 −x2 −y2 ≤0 • sur R2, on étudierait ∇J = 2(x, y)T • mais ici, le minimum vaut 4 et est atteint sur le cercle x2 + y2 = 4 sur lequel ∇J ̸= 0 mais pas toujours : • J(x, y) = x2 + y2 à minimiser sous la contrainte g(x, y) = x2 + y2 −4 ≤0 • le minimum est atteint en (0, 0), avec ∇J = 0 5 / 32 F. Rossi Ré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) = 4 −x2 −y2 ≤0 • sur R2, on étudierait ∇J = 2(x, y)T • mais ici, le minimum vaut 4 et est atteint sur le cercle x2 + y2 = 4 sur lequel ∇J ̸= 0 mais pas toujours : • J(x, y) = x2 + y2 à minimiser sous la contrainte g(x, y) = x2 + y2 −4 ≤0 • le minimum est atteint en (0, 0), avec ∇J = 0 les contraintes doivent donc apparaître dans les conditions d’optimalité 5 / 32 F. Rossi Résultats théoriques Existence d’un minimum cas général : (P) : min J(x), x ∈C ⊂Rn on suppose : • J continue • et C fermé et non vide alors : • si : • C est borné • ou si J est coercitive • alors (P) admet au moins une solution 6 / 32 F. Rossi Résultats théoriques Existence et unicité remarque : si C = x ∈Rn|hi(x) = 0 , 1 ≤i ≤p et gj(x) ≤0 , 1 ≤j ≤q avec des hi et gj continues, alors C est fermé si J est strictement convexe et C est convexe, alors (P) admet au plus une solution problème convexe : • J est convexe • les hi sont afﬁnes • les gj sont convexes • et donc C est convexe 7 / 32 F. Rossi Résultats théoriques Condition du premier ordre si J est Gâteaux-différentiable en x∗solution de (P) et si C est convexe, alors : ∀x ∈C, ⟨∇J(x∗), x −x∗⟩≥0 remarques : • intuitivement : on ne peut s’éloigner du minimum que dans une direction de montée • généralisable : notion de direction admissible • si x∗est un point intérieur de C alors ∇J(x∗) = 0 si J est convexe la condition est nécessaire et sufﬁsante 8 / 32 F. Rossi Résultats théoriques Égalités et inégalités Conditions nécessaires non qualiﬁées cas particulier hi(x) = 0 et gj(x) ≤0 où tout est C1 (J inclus) soit x∗une solution de (P), alors il existe λ∗= (λ∗ 1, . . . , λ∗ p) et µ∗= (µ∗ 0, µ∗ 1, . . . , µ∗ q) tels que • (λ∗, µ∗) ̸= 0 • hi(x∗) = 0, 1 ≤i ≤p (admissibilité en égalité) • gj(x∗) ≤0, 1 ≤j ≤q (admissibilité en inégalité) • µ∗ j ≥0, 0 ≤j ≤q • µ∗ j gj(x∗) = 0, 1 ≤j ≤q (conditions de complémentarité) • et µ∗ 0∇J(x∗) + p X i=1 λ∗ i ∇hi(x∗) + q X j=1 µ∗ j ∇gj(x∗) = 0 9 / 32 F. Rossi Résultats théoriques Qualiﬁcation condition utile si µ0 ̸= 0 problème de qualiﬁcation des contraintes : • conditions (locales) sur le problème qui garantissent que µ0 ̸= 0 • très nombreuses variantes plus ou moins sophistiquées 10 / 32 F. Rossi Résultats théoriques Qualiﬁcation condition utile si µ0 ̸= 0 problème de qualiﬁcation des contraintes : • conditions (locales) sur le problème qui garantissent que µ0 ̸= 0 • très nombreuses variantes plus ou moins sophistiquées contrainte active : gj est active (ou saturée) en x∗si gj(x∗) = 0 ; I(x∗), ensemble des indices des contraintes actives en x∗ 10 / 32 F. Rossi Résultats théoriques Qualiﬁcation condition utile si µ0 ̸= 0 problème de qualiﬁcation des contraintes : • conditions (locales) sur le problème qui garantissent que µ0 ̸= 0 • très nombreuses variantes plus ou moins sophistiquées contrainte active : gj est active (ou saturée) en x∗si gj(x∗) = 0 ; I(x∗), ensemble des indices des contraintes actives en x∗ régularité : x∗est régulier pour g et h si • x∗est admissible • les ∇hi(x∗) sont linéairement indépendants • il existe d ̸= 0 tel que ⟨∇hi(x∗), d⟩= 0 pour tout i et ⟨∇gj(x∗), d⟩< 0 pour tout j ∈I(x∗) (ou ⟨∇gj(x∗), d⟩= 0 si gj est afﬁne) • régularité de Mangasarian-Fromowitz 10 / 32 F. Rossi Résultats théoriques Conditions qualiﬁées Conditions nécessaires qualiﬁées du 1er ordre de KKT (Karush, Kuhn et Tucker) Hypothèses : • J, h et g C1 • x∗solution de (P) • x∗est régulier pour g et h Alors il existe λ∗= (λ∗ 1, . . . , λ∗ p) et µ∗= (µ∗ 1, . . . , µ∗ q) tels que • hi(x∗) = 0, 1 ≤i ≤p • gj(x∗) ≤0, 1 ≤j ≤q • µ∗ j ≥0, 1 ≤j ≤q • µ∗ j gj(x∗) = 0, 1 ≤j ≤q • et ∇J(x∗) + p X i=1 λ∗ i ∇hi(x∗) + q X j=1 µ∗ j ∇gj(x∗) = 0 11 / 32 F. Rossi Résultats théoriques Cas convexe si le problème (P) est convexe, les conditions de KKT sont nécessaires et sufﬁsantes en un point x∗régulier remarque : le caractère sufﬁsant ne nécessite pas la régularité conditions de qualiﬁcation plus simples (de Slater) : il existe au moins un point strictement admissible g(x) < 0 12 / 32 F. Rossi Résultats théoriques Lagrangien le Lagrangien du problème (P) est la fonction L(x, λ, µ) = J(x) + p X i=1 λihi(x) + q X j=1 µjgj(x) quand J, h et g sont C1 les conditions de KKT s’expriment par ∇xL(x∗, λ∗, µ∗) = 0 les λi et les µj sont les multiplicateurs de Lagrange associés aux contraintes 13 / 32 F. Rossi Résultats théoriques Dualité fonction duale de Lagrange g(λ, µ) = inf x L(x, λ, µ) g est toujours concave pour µ ≥0 g(λ, µ) ≤inf x∈C J(x) problème dual (Q) associé au problème primal (P) maximiser sur Rp+q g(λ, µ) avec µj ≥0 , 1 ≤j ≤q saut de dualité : infx∈C J(x) −maxµ≥0 g(λ, µ) 14 / 32 F. Rossi Résultats théoriques Point selle symétrisation du problème : (P) est équivalent à inf x sup λ,µ≥0 L(x, λ, µ) le problème dual (Q) est sup λ,µ≥0 inf x L(x, λ, µ) 15 / 32 F. Rossi Résultats théoriques Point selle symétrisation du problème : (P) est équivalent à inf x sup λ,µ≥0 L(x, λ, µ) le problème dual (Q) est sup λ,µ≥0 inf x L(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 et µ ≥0) L(x∗, λ, µ) ≤L(x∗, λ∗, µ∗) ≤L(x, λ∗, µ∗) 15 / 32 F. Rossi Résultats théoriques Théorème de dualité (x∗, λ∗, µ∗) est un point selle avec µ∗≥0 ssi x∗est une solution de (P), (λ∗, µ∗) est une solution de (Q) et le saut de dualité est nul intérêt : pour résoudre le problème, on peut donc chercher un point selle du Lagrangien 16 / 32 F. Rossi Résultats théoriques Théorème de dualité (x∗, λ∗, µ∗) est un point selle avec µ∗≥0 ssi x∗est une solution de (P), (λ∗, µ∗) est une solution de (Q) et le saut de uploads/Voyage/contraintes-slides.pdf