Méthode prédicteur de prédicteur-correcteur – Wikipedia wiki

Méthode prédictrice-correct de Mehrotra dans l’optimisation est une méthode de point intérieur spécifique pour la programmation linéaire. Il a été proposé en 1989 par Sanjay Mehrotra. ^[d’abord]

La méthode est basée sur le fait qu’à chaque itération d’un algorithme de point intérieur, il est nécessaire de calculer la décomposition (factorisation) de Cholesky d’une grande matrice pour trouver la direction de recherche. L’étape de factorisation est l’étape la plus coûteuse dans l’algorithme. Par conséquent, il est logique d’utiliser la même décomposition plus d’une fois avant de le recomposer.

À chaque itération de l’algorithme, la méthode prédicte-correct de Mehrotra utilise la même décomposition de Cholesky pour trouver deux directions différentes: un prédicteur et un correcteur.

L’idée est de calculer d’abord une direction de recherche d’optimisation basée sur un terme de premier ordre (prédicteur). La taille des pas qui peut être prise dans ce sens est utilisée pour évaluer la quantité de correction de centralité nécessaire. Ensuite, un terme correcteur est calculé: il contient à la fois un terme de centralité et un terme de deuxième ordre.

La direction de recherche complète est la somme de la direction prédictive et de la direction du correcteur.

Bien qu’il n’y ait pas encore de complexité théorique liée, la méthode prédicte-correct de Mehrotra est largement utilisée dans la pratique. ^[2] Son étape correctrice utilise la même décomposition de Cholesky trouvée au cours de l’étape prédictive de manière efficace, et donc elle n’est que légèrement plus chère qu’un algorithme de point intérieur standard. Cependant, les frais généraux supplémentaires par itération sont généralement remboursés par une réduction du nombre d’itérations nécessaires pour atteindre une solution optimale. Il semble également converger très rapidement lorsqu’il est proche de l’optimum.

Dérivation [ modifier ]]

La dérivation de cette section suit le contour de Nocedal et Wright. ^[3]

Étape du prédicteur – direction de l’échelle affine [ modifier ]]

Un programme linéaire peut toujours être formulé sous la forme standard

${displayStyle {begin {aligned} & {Undernset {x} {min}} & q (x) & = c ^ {t} x, \ & {text {s.t.}} & ax & = b, \ &; & x & geq 0, end { aligné}}}$

où

${displayStyle cin Mathbb {r} ^ {ntimes 1},; ain mathbb {r} ^ {mtimes n}}$

et

${displaystyle bin mathbb {r} ^ {mTimes 1}}$

définir le problème avec

${displaystyle m}$

contraintes et

${displaystyle n}$

équations pendant que

${displaystyle xin mathbb {r} ^ {ntimes 1}}$

est un vecteur de variables.

Les conditions de Karush-Kuhn-Tucker (KKT) pour le problème sont

${displayStyle {begin {aligned} a ^ {t} lambda + s & = c, ;;; {text {(Lagrange Gradient Condition)}} \ ax & = b, ;;; {Text {(condition de faisabilité)}} \ xse & = 0, ;;; {Texte {(condition de complémentarité)}} \ (x, s) & geq 0, end {aligné}}}$

où

${DisplayStyle x = {texte {diag}} (x)}$

et

${displayStyle s = {text {diag}} (s)}$

d’où

${displayStyle e = (1,1, points, 1) ^ {t} dans mathbb {r} ^ {ntimes 1}}$

.

Ces conditions peuvent être reformulées comme une cartographie

${Displaystyle f: mathbb {r} ^ {2n + m} rightarrow Mathbb {r} ^ {2n + m}}$

comme suit

${displayStyle {begin {aligned} f (x, lambda, s) = {begin {bmatrix} a ^ {t} lambda + s-c \ ax-b \ xseend {bMatrix}} & = 0 \ (x, s) & geq 0end {aligné}}}$

La méthode prédictive-correct fonctionne ensuite en utilisant la méthode de Newton pour obtenir la direction de mise à l’échelle affine. Ceci est réalisé en résolvant le système suivant d’équations linéaires

${displayStyle j (x, lambda, s) {begin {bmatrix} delta x ^ {text {aff}} \ delta lambda ^ {text {aff}} \ delta s ^ {text {aff}} end {bmatrix}} = -F (x, lambda, s)}$

où

${displaystyle J}$

, défini comme

${displayStyle j (x, lambda, s) = {begin {bmatrix} nabla _ {x} f & nabla _ {lambda} f & nabla _ {s} fend {bmatrix}},}$

est le jacobien de F.

Ainsi, le système devient

${displayStyle {begin {bmatrix} 0 & a ^ {t} & i \ a & 0 & 0 \ s & 0 & xend {bmatrix}} {begin {bmatrix} delta x ^ {text {aff}} \ delta lambda ^ {text {aff}} \ delta S ^ { Texte {AFF}} end {bMatrix}} = {begin {bmatrix} -r_ {c} \ – r_ {b} \ – xseend {bmatrix}}, ;;; r_ {c} = a ^ {t} lambda + s-c, ;;; r_ {b} = ax-b}$

Pas de centrage [ modifier ]]

La valeur moyenne des produits

${displayStyle x_ {i} s_ {i},; i = 1,2, points, n}$

constituent une mesure importante de l’opportunité d’un certain ensemble

${displayStyle (x ^ {k}, s ^ ​​{k})}$

(Les exposés indiquent la valeur du numéro d’itération,

${displaystyle k}$

, de la méthode). C’est ce qu’on appelle la mesure de la dualité et est défini par

${displayStyle mu = {frac {1} {n}} sum _ {i = 1} ^ {n} x_ {i} s_ {i} = {frac {x ^ {t} s} {n}}.}$

Pour une valeur du paramètre de centrage,

${DisplayStyle Sigma dans [0,1],}$

L’étape de centrage peut être calculée comme la solution pour

${displayStyle {begin {bmatrix} 0 & a ^ {t} & i \ a & 0 & 0 \ s & 0 & xend {bmatrix}} {begin {bmatrix} delta x ^ {text {cen}} \ delta lambda ^ {text {cen}} \ delta s ^ {Lambda ^ {Text {cen}} \ delta S ^ { Texte {Cen}} end {bMatrix}} = {begin {bmatrix} -r_ {c} \ – r_ {b} \ – xse + sigma mu eend {bMatrix}}}$

Étape du correcteur [ modifier ]]

Compte tenu du système utilisé pour calculer la direction de mise à l’échelle affine définie dans ce qui précède, on peut noter que faire un pas complet dans la direction de mise à l’échelle affine, la condition de complémentarité n’est pas satisfaite:

${displayStyle Left (x_ {i} + delta x_ {i} ^ {text {aff}} droite) Left (s_ {i} + delta s_ {i} ^ {text {aff}} droit) = x_ {i} s_ {i} + x_ {i} delta s_ {i} ^ {text {aff}} + s_ {i} delta x_ {i} ^ {text {aff}} + delta x_ {i} ^ {text {aff}} Delta s_ {i} ^ {texte {aff}} = delta x_ {i} ^ {texte {aff}} delta s_ {i} ^ {texte {aff}} neq 0.}$

En tant que tel, un système peut être défini pour calculer une étape qui tente de corriger cette erreur. Ce système repose sur le calcul précédent de la direction de mise à l’échelle affine.

${displayStyle {begin {bmatrix} 0 & a ^ {t} & i \ a & 0 & 0 \ s & 0 & xend {bmatrix}} {begin {bmatrix} delta x ^ {text {cor}} \ delta lambda ^ {text {cor}} \ delta s ^ {Lambda ^ {Text {cor}} \ delta s ^ { Texte {Cor}} end {bMatrix}} = {begin {bmatrix} 0 \ 0 \ -delta x ^ {text {aff}} delta s ^ {text {aff}} eend {bmatrix}}}$

Système agrégé – Direction centrale-correct [ modifier ]]

Le prédicteur, le correcteur et les contributions de centrage au système à droite du système peuvent être agrégés en un seul système. Ce système dépendra du calcul précédent de la direction de mise à l’échelle affine, cependant, la matrice du système sera identique à celle de l’étape de prédicteur de telle sorte que sa factorisation puisse être réutilisée.

Le système agrégé est

${displayStyle {begin {bmatrix} 0 & a ^ {t} & i \ a & 0 & 0 \ s & 0 & xend {bmatrix}} {begin {bmatrix} delta x \ delta lambda \ delta envoy -r_ {b} \ – xse-delta x ^ {text {aff}} delta s ^ {text {aff}} e + sigma mu eend {bMatrix}}}$

L’algorithme prédicteur-corrécteur calcule ensuite d’abord la direction de l’échelle affine. Deuxièmement, il résout le système agrégé pour obtenir la direction de recherche de l’itération actuelle.

Sélection adaptative du paramètre de centrage [ modifier ]]

La direction de l’échelle affine peut être utilisée pour définir une heuristique pour choisir de manière adaptative le paramètre de centrage comme

${displayStyle Sigma = Left ({frac {mu _ {text {aff}}} {mu}} droit) ^ {3},}$

où

${displayStyle {begin {aligned} mu _ {text {aff}} & = (x + alpha _ {text {aff}} ^ {text {pri}} delta x ^ {text {aff}}) ^ {t} (( S + alpha _ {texte {aff}} ^ {texte {dual}} delta s ^ {text {aff}}) / n, \ alpha _ {texte {aff}} ^ {texte {pri}} & = min Left (1. } droit), \ alpha _ {texte {aff}} ^ {texte {dual}} & = min Left (1, {Underfet {i: delta s_ {i} ^ {text {aff}} <0} {min} } - {frac {s_ {i}} {delta s_ {i} ^ {text {aff}}}} droit), end {aligné}}}$

Ici,

${displayStyle mu _ {text {aff}}}$

est la mesure de dualité de l’étape affine et

${displaystyle mu}$

est la mesure de dualité de l’itération précédente. ^[3]

Longueurs de pas [ modifier ]]

Dans les implémentations pratiques, une version de la recherche en ligne est effectuée pour obtenir la longueur maximale de pas qui peut être prise dans la direction de la recherche sans violer la non-négativité,

${displayStyle (x, s) geq 0}$

. ^[3]

Adaptation à la programmation quadratique [ modifier ]]

Bien que les modifications présentées par Mehrotra aient été destinées aux algorithmes de points intérieurs pour la programmation linéaire, les idées ont également été étendues et appliquées avec succès à la programmation quadratique. ^[3]

Les références [ modifier ]]