of 42 /42
Optimisation sous contraintes Fabrice Rossi TELECOM ParisTech Décembre 2009/Janvier 2010

Optimisation sous contraintes - apiacoa.orgapiacoa.org/publications/teaching/optimization/contraintes-slides.pdf · Optimisation sous contraintes Fabrice Rossi TELECOM ParisTech Décembre

Embed Size (px)

Text of Optimisation sous contraintes -...

  • Optimisation sous contraintes

    Fabrice Rossi

    TELECOM ParisTech

    Dcembre 2009/Janvier 2010

  • Plan

    Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

    AlgorithmesIntroductionGradientPnalisationDualit

    2 / 32 F. Rossi

  • Plan

    Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

    AlgorithmesIntroductionGradientPnalisationDualit

    3 / 32 F. Rossi Rsultats thoriques

  • Forme gnrale

    un problme doptimisation (P) est dfini 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 dgalit (notes h(x) = 0) les gj sont les contraintes dingalit (notes g(x) 0) lensemble des contraintes est

    C = {x Rn|hi(x) = 0 ,1 i p et gj(x) 0 ,1 j q}

    ensemble des points admissibles ou ralisables

    4 / 32 F. Rossi Rsultats thoriques

  • Forme gnrale

    un problme doptimisation (P) est dfini 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 dgalit (notes h(x) = 0) les gj sont les contraintes dingalit (notes g(x) 0) lensemble des contraintes est

    C = {x Rn|hi(x) = 0 ,1 i p et gj(x) 0 ,1 j q}

    ensemble des points admissibles ou ralisables

    4 / 32 F. Rossi Rsultats thoriques

  • Consquences

    les contraintes changent les conditions doptimalitexemple : 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 6= 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 apparatre dans les conditionsdoptimalit

    5 / 32 F. Rossi Rsultats thoriques

  • Consquences

    les contraintes changent les conditions doptimalitexemple : 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 6= 0mais 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 apparatre dans les conditionsdoptimalit

    5 / 32 F. Rossi Rsultats thoriques

  • Consquences

    les contraintes changent les conditions doptimalitexemple : 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 6= 0mais 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 apparatre dans les conditionsdoptimalit

    5 / 32 F. Rossi Rsultats thoriques

  • Existence dun minimum

    cas gnral : (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 Rsultats thoriques

  • 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 fermsi J est strictement convexe et C est convexe, alors (P)admet au plus une solutionproblme convexe : J est convexe les hi sont affines les gj sont convexes et donc C est convexe

    7 / 32 F. Rossi Rsultats thoriques

  • Condition du premier ordre

    si J est Gteaux-diffrentiable en x solution de (P) et si Cest convexe, alors :

    x C, J(x),x x 0

    remarques : intuitivement : on ne peut sloigner du minimum que dans

    une direction de monte gnralisable : notion de direction admissible si x est un point intrieur de C alors J(x) = 0

    si J est convexe la condition est ncessaire et suffisante

    8 / 32 F. Rossi Rsultats thoriques

  • galits et ingalits

    Conditions ncessaires non qualifiescas particulier hi(x) = 0 et gj(x) 0 o tout est C1 (Jinclus)soit x une solution de (P), alors il existe = (1, . . . , p)et = (0,

    1, . . . ,

    q) tels que

    (,) 6= 0 hi(x) = 0, 1 i p (admissibilit en galit) gj(x) 0, 1 j q (admissibilit en ingalit) j 0, 0 j q j gj(x

    ) = 0, 1 j q (conditions de complmentarit) et

    0J(x) +p

    i=1

    i hi(x) +q

    j=1

    j gj(x) = 0

    9 / 32 F. Rossi Rsultats thoriques

  • Qualification

    condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

    trs nombreuses variantes plus ou moins sophistiques

    contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

    rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

    rgularit de Mangasarian-Fromowitz

    10 / 32 F. Rossi Rsultats thoriques

  • Qualification

    condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

    trs nombreuses variantes plus ou moins sophistiques

    contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

    rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

    rgularit de Mangasarian-Fromowitz

    10 / 32 F. Rossi Rsultats thoriques

  • Qualification

    condition utile si 0 6= 0problme de qualification des contraintes : conditions (locales) sur le problme qui garantissent que0 6= 0

    trs nombreuses variantes plus ou moins sophistiques

    contrainte active : gj est active (ou sature) en x sigj(x) = 0 ; I(x), ensemble des indices des contraintesactives en x

    rgularit : x est rgulier pour g et h si x est admissible les hi(x) sont linairement indpendants il existe d 6= 0 tel que hi(x),d = 0 pour tout i etgj(x),d < 0 pour tout j I(x) (ou gj(x),d = 0 sigj est affine)

    rgularit de Mangasarian-Fromowitz

    10 / 32 F. Rossi Rsultats thoriques

  • Conditions qualifiesConditions ncessaires qualifies du 1er ordre de KKT(Karush, Kuhn et Tucker)Hypothses : J, h et g C1 x solution de (P) x est rgulier 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

    i=1

    i hi(x) +q

    j=1

    j gj(x) = 0

    11 / 32 F. Rossi Rsultats thoriques

  • Cas convexe

    si le problme (P) est convexe, les conditions de KKT sontncessaires et suffisantes en un point x rgulierremarque : le caractre suffisant ne ncessite pas largularitconditions de qualification plus simples (de Slater) : ilexiste au moins un point strictement admissible g(x) < 0

    12 / 32 F. Rossi Rsultats thoriques

  • Lagrangien

    le Lagrangien du problme (P) est la fonction

    L(x,,) = J(x) +p

    i=1

    ihi(x) +q

    j=1

    jgj(x)

    quand J, h et g sont C1 les conditions de KKT sexprimentpar xL(x,,) = 0les i et les j sont les multiplicateurs de Lagrangeassocis aux contraintes

    13 / 32 F. Rossi Rsultats thoriques

  • Dualit

    fonction duale de Lagrange

    g(,) = infx

    L(x,,)

    g est toujours concavepour 0

    g(,) infxC

    J(x)

    problme dual (Q) associ au problme primal (P)

    maximiser sur Rp+q g(,)avec j 0 ,1 j q

    saut de dualit : infxC J(x)max0 g(,)

    14 / 32 F. Rossi Rsultats thoriques

  • Point sellesymtrisation du problme : (P) est quivalent

    infx

    sup,0

    L(x,,)

    le problme dual (Q) est

    sup,0

    infx

    L(x,,)

    point selle : minimal par rapport une variable, maximalpar rapport lautre(x,,) est un point selle du Lagrangien si pour tout(x,,) ( 0 et 0)

    L(x,,) L(x,,) L(x,,)

    15 / 32 F. Rossi Rsultats thoriques

  • Point sellesymtrisation du problme : (P) est quivalent

    infx

    sup,0

    L(x,,)

    le problme dual (Q) est

    sup,0

    infx

    L(x,,)

    point selle : minimal par rapport une variable, maximalpar rapport lautre(x,,) est un point selle du Lagrangien si pour tout(x,,) ( 0 et 0)

    L(x,,) L(x,,) L(x,,)

    15 / 32 F. Rossi Rsultats thoriques

  • Thorme de dualit

    (x,,) est un point selle avec 0 ssi x est unesolution de (P), (,) est une solution de (Q) et le sautde dualit est nulintrt : pour rsoudre le problme, on peut donc chercherun point selle du Lagrangien

    remarque : un point selle du Lagrangien vrifie lesconditions de KKT (sans hypothse autre que J, h et g C1)si le problme est convexe : point selle KKT

    16 / 32 F. Rossi Rsultats thoriques

  • Thorme de dualit

    (x,,) est un point selle avec 0 ssi x est unesolution de (P), (,) est une solution de (Q) et le sautde dualit est nulintrt : pour rsoudre le problme, on peut donc chercherun point selle du Lagrangienremarque : un point selle du Lagrangien vrifie lesconditions de KKT (sans hypothse autre que J, h et g C1)si le problme est convexe : point selle KKT

    16 / 32 F. Rossi Rsultats thoriques

  • Rgularit

    Condition plus forte que celle de Mangasarian-Fromowitz : x est admissible hi(x) et les gj(x) sont linairement indpendants pour

    j I(x)Contraintes fortement actives :

    I+(x) = {j | gj(x) = 0 et j > 0}

    si I(x) = I+(x) on a complmentarit stricte

    17 / 32 F. Rossi Rsultats thoriques

  • Conditions ncessaires du 2me ordre

    Hypothses : J, h et g C2 x solution de (P) et fortement rgulier

    alors il existe = (1, . . . , p) et = (1, . . . ,

    q) tels

    que les conditions de KKT sont vrifies et pour tout d vrifiant :

    hi(x), d = 0 pour 1 i p gj(x), d = 0 pour j I+(x) gj(x), d 0 pour I(x) \ I+(x)

    on a 2xxL(x,

    ,)d ,d 0

    18 / 32 F. Rossi Rsultats thoriques

  • Conditions suffisantes

    Hypothses : J, h et g C2 (x,,) vrifie les conditions KKT

    si la matrice 2xxL(x,,) est dfinie positive sur{d Rn | hi(x),d = 0, 1 i ,p

    etgj(x),d

    = 0, j I+(x)

    }alors x est un minimum local de J sur C

    19 / 32 F. Rossi Rsultats thoriques

  • Plan

    Rsultats thoriquesIntroductionExistence et unicitConditions doptimalitDualitSecond ordre

    AlgorithmesIntroductionGradientPnalisationDualit

    20 / 32 F. Rossi Algorithmes

  • Classes dalgorithmes

    quelques grandes classes dalgorithmes : gradient projet :

    descente de gradient projection sur C chaque tape

    pnalisation : optimisation sans contrainte de J+pnalit mthodes extrieures : on ramne progressivement le

    candidat minimum dans C mthodes intrieures : on relche progressivement les

    pnalits programmation quadratique successive : rsoudre des

    approximations quadratiques du problme

    principe sous-jacent : rsoudre une srie de problmessans contrainte (ou plus simple)

    21 / 32 F. Rossi Algorithmes

  • Projection

    outil important : projection sur un convexe ferm soit C un convexe ferm et non vide de Rn pour tout x alors

    C(x) = arg minyCx y2

    existe et est uniqueproprits : C(x) est lunique lment de C tel que

    y C, x C(x),y C(x) 0

    ou encore tel que

    y C, C(x) y,y x 0

    22 / 32 F. Rossi Algorithmes

  • Projection

    C est une contraction :

    x,y, C(x) C(y) x y

    preuve simple : on a

    x C(x), C(y) C(x) 0y C(y), C(x) C(y) 0

    soit

    x y, C(y) C(x)+ C(x) C(y)2 0

    et on termine par Cauchy-Schwartz

    23 / 32 F. Rossi Algorithmes

  • Gradient projet

    minimisation de J sur C convexe fermalgorithme :

    1. point initial x02. pour k 1 croissant

    2.1 calculer yk+1 = xk kJ(xk )2.2 puis xk+1 = C(yk+1)2.3 tester la convergence et quitter la boucle le cas chant (par

    ex. xk+1 xk < )

    formulation simple mais mise en oeuvre potentiellementdlicate : si C est simple (par ex., li xi ui ), pas de problme sinon le calcul de C(yk+1) est un problme doptimisation

    sous contraintes

    24 / 32 F. Rossi Algorithmes

  • Gradient projet

    minimisation de J sur C convexe fermalgorithme :

    1. point initial x02. pour k 1 croissant

    2.1 calculer yk+1 = xk kJ(xk )2.2 puis xk+1 = C(yk+1)2.3 tester la convergence et quitter la boucle le cas chant (par

    ex. xk+1 xk < )formulation simple mais mise en oeuvre potentiellementdlicate : si C est simple (par ex., li xi ui ), pas de problme sinon le calcul de C(yk+1) est un problme doptimisation

    sous contraintes

    24 / 32 F. Rossi Algorithmes

  • Convergence

    si J est C1, -convexe et de drive M-lipschitzienneet si k [1, 2] avec 0 < 1 < 2 < 2M2alors lalgorithme du gradient projet converge : preuve trs proche de celle du cas sans contrainte si x est loptimum, on a pour tout

    x = C(x J(x))

    donc par contraction de C

    xk+1 x2 (xk kJ(xk )) (x kJ(x))2

    ce qui nous ramne au cas sans projection

    25 / 32 F. Rossi Algorithmes

  • Pnalisation

    ide principale : remplacer un problme avec contraintespar un problme sans contrainte dont la fonction objectif dcourage les points non admissiblessolution nave : on dfinit

    (x) ={

    + x 6 C0 x C

    alors trouver arg minxC J(x) est quivalent trouverarg minxRn J(x) + (x)

    solutions ralistes : utiliser une fonction rgulire (C1 aumoins) petite sur C et grande en dehors

    26 / 32 F. Rossi Algorithmes

  • Mthodes de point extrieur

    vrifie : est continue sur Rn (x) 0 (x) = 0 x C

    Exemples : h(x) = 0 est reprsente par (x) = h(x)2 g(x) 0 est reprsente par (x) = g+(x)2

    on considre la famille de problmes (Pr ) pour r > 0dfinis par

    minxRn

    (J(x) + r(x))

    mthodes de point extrieur : on ne peut pas garantirxr C

    27 / 32 F. Rossi Algorithmes

  • Mthodes de point intrieurmme principe, mais avec des points lintrieur de Cpour les contraintes dingalit seulement est une barrire et vrifie : est continue sur

    C

    x 6 C (x) =pour les contraintes g(x) 0, on prend gnralement

    q

    j=1

    log(gj(x))

    comme pour les mthodes de point extrieur, on considreles problmes (Pr ) pour r > 0 dfinis par

    minxRn

    (J(x) + r(x))

    ici, on a toujours xr C

    28 / 32 F. Rossi Algorithmes

  • Pnalisation

    minimisation de J sur C convexe fermalgorithme (pour une suite (rk )k croissante) :

    1. point initial x02. pour k 1 croissant

    2.1 rsoudre le problme (Prk )

    minxRn

    (J(x) + rk(x))

    en partant de la solution xk12.2 tester la qualit du point obtenu xk et quitter la boucle le cas

    chant

    fonctionne trs bien en pratique pour le cas du pointintrieur (on rsout (Prk ) par une mthode de(quasi)Newton avec contraintes dgalits)lefficacit vient du redmarrage depuis un bon candidat

    29 / 32 F. Rossi Algorithmes

  • Pnalisation

    minimisation de J sur C convexe fermalgorithme (pour une suite (rk )k croissante) :

    1. point initial x02. pour k 1 croissant

    2.1 rsoudre le problme (Prk )

    minxRn

    (J(x) + rk(x))

    en partant de la solution xk12.2 tester la qualit du point obtenu xk et quitter la boucle le cas

    chant

    fonctionne trs bien en pratique pour le cas du pointintrieur (on rsout (Prk ) par une mthode de(quasi)Newton avec contraintes dgalits)lefficacit vient du redmarrage depuis un bon candidat

    29 / 32 F. Rossi Algorithmes

  • Convergence

    on suppose J continue et coercitive, et C ferm et non videon considre une mthode de point extrieurrsultat : pour tout r > 0, (Pr ) possde au moins une solution toute famille (xr )r>0 de solutions est borne les valeurs dadhrence de toute famille (xr )r>0 de

    solutions sont des solutions de (P)

    preuve (x est une solution de (P)) : Jr (x) = J(x) + r(x) est coercitive et continue xr solution de (Pr ), J(xr ) Jr (xr ) Jr (x) = J(x), donc

    (xr )r>0 est borne comme (xr ) 1r (J(x

    ) J(xr )), on a limr+ (xr ) = 0 et donc pour toute valeur dadhrence x, J(x) J(x)

    30 / 32 F. Rossi Algorithmes

  • Convergence

    on suppose J continue et coercitive, et C ferm et non videon considre une mthode de point extrieurrsultat : pour tout r > 0, (Pr ) possde au moins une solution toute famille (xr )r>0 de solutions est borne les valeurs dadhrence de toute famille (xr )r>0 de

    solutions sont des solutions de (P)preuve (x est une solution de (P)) : Jr (x) = J(x) + r(x) est coercitive et continue xr solution de (Pr ), J(xr ) Jr (xr ) Jr (x) = J(x), donc

    (xr )r>0 est borne comme (xr ) 1r (J(x

    ) J(xr )), on a limr+ (xr ) = 0 et donc pour toute valeur dadhrence x, J(x) J(x)

    30 / 32 F. Rossi Algorithmes

  • Algorithme dUzawa

    ide : chercher directement un point selle du Lagrangienalgorithme (paramtre > 0) :

    1. valeurs initiales des multiplicateurs 1,12. pour k 1 croissant

    2.1 trouver xk solution du problme (sans contrainte)

    minxRn

    L(x,k ,k )

    2.2 mettre jour (k ,k ) par

    k+1i = ki + hi(xk )

    k+1j = max(0, kj + gj(xk ))

    2.3 tester la convergence et quitter la boucle le cas chant (parex. xk+1 xk < )

    31 / 32 F. Rossi Algorithmes

  • Algorithme dUzawa

    on peut montrer que lalgorithme dUzawa est un gradientprojet sur le problme dual : on montre que g(,) = (,)T on maximise g(,), ce qui explique le signe dans la mise

    jour des multiplicateurs intressant parce que la projection est triviale

    Convergence : si J est C1, -convexe, h affine et g convexe et Mg

    lipschitzienne et si L possde un point selle (x,,) alors lalgorithme converge vers x pour tout choix de

    dans ]0, 2M2g +M2h[

    32 / 32 F. Rossi Algorithmes

    Rsultats thoriquesIntroductionExistence et unicitConditions d'optimalitDualitSecond ordre

    AlgorithmesIntroductionGradientPnalisationDualit