Optimisation quadratique successive

Optimisation quadratique successive

L’algorithme OQS et sa convergence locale Nous présentons l’algorithme OQS comme un algorithme de Josephy-Newton sur le système d’optimalité, lequel peut en effet s’écrire comme un problème d’inclusion, et même de complémentarité non linéaire (section 15.1.1). Sa convergence locale peut alors se déduire de celle de l’algorithme de Josephy-Newton (théorème ??), pourvu que le point stationnaire considéré soit semi-stable et hémi-stable. On montre que c’est effectivement le cas lorsque celui-ci correspond à un minimum local de (PEI ) vérifiant les conditions d’optimalité du second ordre semi-fortes (section 15.1.2).

L’algorithme OQS

Par définition, un couple stationnaire de (PEI ) est un couple (x, λ) qui vérifie le système d’optimalité (4.33), c’est-à-dire    ∇f(x) + c ′ (x) ∗λ = 0 cE(x) = 0 0 6 λ ⊥ cI (x) 6 0. (15.1) On peut récrire ce système comme l’inclusion ou le problème de complémentarité en z := (x, λ) ci-dessous F(z) + NK(z) ∋ 0 ou K ∋ z ⊥ F(z) ∈ K+, (15.2a) avec F(z) =  ∇f(x) + c ′ (x) ∗λ −c(x)  et K = E × (R mE × R mI + ). (15.2b) En effet, alors K+ = {0E} × ({0RmE } × R mI + ) et (x, λ) ∈ K s’écrit λI > 0, F(x, λ) ∈ K+ s’écrit ∇xℓ(x, λ) = 0, cE(x) = 0 et cI (x) 6 0, (x, λ) ⊥ F(x, λ) se ramène alors à la relation de complémentarité λI ⊥ cI (x). On retrouve donc bien (15.1). L’algorithme de Josephy-Newton (??) appliqué à l’inclusion ou au problème de complémentarité (15.2) consiste à déterminer l’itéré suivant zk+1 := (xk+1, λk+1) à partir de l’itéré courant zk := (xk, λk) en résolvant l’inclusion linéarisée en z := (x, λ) ci-dessous F(zk) + F ′ (zk)(z − zk) + NK(z) ∋ 0 (15.3a) ou son problème de complémentarité équivalent K ∋ z ⊥ 

Algorithme 15.1 (OQS local)

Une itération passe de l’itéré courant (xk, λk) ∈ E× R m à l’itéré suivant (xk+1, λk+1) par les étapes suivantes : 1. Test d’arrêt : si le couple (xk, λk) est satisfaisant, on s’arrête. 2. Nouvel itéré : On prend comme nouvel itéré (xk+1, λk+1) une solution primale duale du problème quadratique osculateur (15.7).

L’algorithme local 15.2.1

 Un algorithme non convergent Considérons d’abord le problème avec contraintes d’égalité seulement (PE)  min f(x) c(x) = 0, où f : E → R et c : E → R m. 566 15. Optimisation quadratique successive On a vu au chapitre 10 comment on pouvait introduire la méthode de Newton pour résoudre des équations non linéaires (voir (10.3)) et pour minimiser une fonction (voir (10.7)). Pour résoudre le problème (PE ), on pourrait donc être tenté d’obtenir le déplacement dk en xk en prenant une approximation quadratique du critère et en linéarisant les contraintes en xk. Avec cette méthode, on calculerait dk comme solution du problème quadratique  min ∇f(xk) Td + 1 2 d T∇2f(xk)d cE(xk) + c ′ E(xk) · d = 0 (15.16) et on prendrait xk+1 = xk + dk. Attention, cet algorithme n’est pas nécessairement convergent ! On connaît des exemples (voir l’exercice 15.1) dans lesquels la solution est répulsive pour cet algorithme : on peut trouver des itérés aussi proches que l’on veut de la solution (mais différents de la solution), tels que l’itéré suivant est plus éloigné de la solution que l’itéré en question. En fait, si on écrit l’algorithme comme un processus de point fixe, xk+1 = Φ(xk) pour une certaine fonction Φ, l’application Φ n’est pas strictement contractante proche de la solution. Hélas, on voit encore parfois cette approche utilisée de nos jours ! Pourtant il doit bien exister une méthode newtonienne, c’est-à-dire qui procède par linéarisations, pour résoudre les problèmes avec contraintes ! Les chercheurs en optimisation numérique se sont posés la question bien longtemps et ce n’est qu’au milieu des années 1970, soit 30 ans après l’invention de l’algorithme du simplexe, que la situation s’est éclaircie. Ce qui ne fonctionne pas dans l’approche qui a conduit à (15.16), c’est qu’en traitant séparément les problèmes contradictoires « min f(x) » et « c(x) = 0 » (le minimum de f ne vérifie en général pas la contrainte c(x) = 0, sinon pourquoi la spécifier), on a mis en place deux algorithmes qui ne se concertent pas et tirent à hue et à dia. Cela paraît à présent évident, la bonne démarche est de résoudre un seul système qui détermine les solutions de (PE ) et cela par un unique algorithme. Ce système est celui formé par les conditions d’optimalité de (PE ) et l’algorithme est celui de Newton. Ce système comporte en effet n+m équations et n+m inconnues (x∗, λ∗), ce qui en fait un candidat convenable pour être résolu par des itérations de Newton. Nous n’allons pas écrire cet algorithme, qui est en fait un cas particulier de celui que nous introduisons à la section suivante. 

L’algorithme OQS La discussion de la section

 15.2.1 nous a montré qu’il était judicieux de faire des itérations de Newton sur le système d’optimalité de (PEI ). Rappelons (théorème 4.32) que celui-ci détermine les points stationnaires (x∗, λ∗) du problème comme solution du système de Karush, Kuhn et Tucker : (KKT)    (a) ∇f(x∗) + A(x∗) Tλ∗ = 0 (b) cE(x∗) = 0, cI (x∗) 6 0 (c) (λ∗)I > 0 (d) (λ∗) T I cI (x∗) = 0. (15.17) Travailler sur ce système d’optimalité n’allait pas de soi et l’on peut dire qu’il a fallu franchir un saut conceptuel pour y arriver.D’abord, ces relations forment un système en (x∗, λ∗), pas seulement en x∗. Il faut donc les linéariser par rapport à (x, λ), pas seulement par rapport à x comme dans l’algorithme qui a conduit à (15.16). L’algorithme de Newton qui en résultera sera donc une méthode primale-duale, générant à la fois des itérés primaux xk et duaux λk. Une autre difficulté provient de la présence d’inégalités dans (15.17). La linéarisation de l’inégalité F(x) 6 0 en x, pour un accroissement d, se fera par F(x) + F ′ (x) · d 6 0. On verra par les résultats de convergence locale obtenus qu’il s’agit d’un bon choix. Soit (x, λ) ∈ E×R m le point courant auquel on linéarise (15.17) et (d, µ) ∈ E×R m l’accroissement, la correction, que l’on désire apporter au point courant. L’itéré suivant (x+, λ+) s’obtiendra donc par x+ := x + d et λ+ := λ + µ. On obtient le système suivant :    L(x, λ)d + A(x) Tµ = −∇xℓ(x, λ) (c(x) + A(x)d) # = 0 (λ + µ)I > 0 (λ + µ) T I cI (x) + λ T I (A(x)d)I = 0. (15.18) On a noté A(x) := c ′ (x) la jacobienne des contraintes et L(x, λ) := ∇ 2 xxℓ(x, λ) la hessienne du lagrangien. Bien que linéaire, le système (15.18) a l’inconvénient d’être très difficile à résoudre. On y trouve en effet des égalités et des inégalités. De plus, on ne voit plus le problème d’optimisation dont il est issu. On se rappelle, en effet, que dans le cas de l’optimisation sans contrainte, le pas de Newton pouvait se voir comme un point stationnaire d’un problème d’optimisation quadratique sans contrainte. On aimerait pouvoir faire de même ici. Dans ce but, on modifie le système (15.18), de manière à ce qu’il soit le système d’optimalité d’un problème quadratique avec contraintes linéaires. Si on ajoute le terme µ TA(x)d à la dernière équation, celle-ci ressemble davantage à des conditions de complémentarité (c’est alors un produit de deux facteurs). On observera par ailleurs, que dans le voisinage d’une solution primale-duale, le terme µ TA(x)d est formé d’un produit de deux grandeurs très petites, les accroissements µ et d. L’ajout du terme µ TA(x)d apporte donc une perturbation insignifiante au système (15.18), qui ne devrait pas modifier les propriétés de convergence rapide de l’algorithme (cette intuition s’avérera correcte). Le système devient alors    L(x, λ)d + A(x) Tµ = −∇xℓ(x, λ) (c(x) + A(x)d) # = 0 (λ + µ)I > 0 (λ + µ) T I (c(x) + A(x)d)I = 0. (15.19) On vérifie aisément le fait remarquable suivant : (15.19) est formé des conditions de KKT du problème d’optimisation quadratique