Mehrotra-Prädiktor-Korrektor-Methode – Wikipedia

Posted on by
before-content-x4

Mehrotra-Prädiktor-Korrektor-Methode Bei der Optimierung handelt es sich um eine spezielle Innenpunktmethode für die lineare Programmierung. Es wurde 1989 von Sanjay Mehrotra vorgeschlagen.[1]

 after-content-x4

Das Verfahren basiert auf der Tatsache, dass bei jeder Iteration eines inneren Punktalgorithmus die Cholesky-Zerlegung (Faktorisierung) einer großen Matrix berechnet werden muss, um die Suchrichtung zu finden. Der Faktorisierungsschritt ist der rechenintensivste Schritt im Algorithmus. Daher ist es sinnvoll, dieselbe Zerlegung mehrmals zu verwenden, bevor Sie sie neu berechnen.

Bei jeder Iteration des Algorithmus verwendet die Prädiktor-Korrektor-Methode von Mehrotra dieselbe Cholesky-Zerlegung, um zwei verschiedene Richtungen zu finden: einen Prädiktor und einen Korrektor.

Die Idee ist, zuerst eine optimierende Suchrichtung basierend auf einem Term erster Ordnung (Prädiktor) zu berechnen. Die Schrittgröße, die in diese Richtung genommen werden kann, wird verwendet, um zu bewerten, wie viel Zentralitätskorrektur erforderlich ist. Dann wird ein Korrektorterm berechnet: Dieser enthält sowohl einen Zentralitätsterm als auch einen Term zweiter Ordnung.

Die vollständige Suchrichtung ist die Summe aus Prädiktorrichtung und Korrektorrichtung.

Obwohl noch keine theoretische Komplexität daran gebunden ist, ist die Prädiktor-Korrektor-Methode von Mehrotra in der Praxis weit verbreitet.[2] Sein Korrektorschritt verwendet auf effektive Weise dieselbe Cholesky-Zerlegung, die während des Prädiktorschritts gefunden wurde, und ist daher nur unwesentlich teurer als ein Standard-Innenpunktalgorithmus. Der zusätzliche Aufwand pro Iteration zahlt sich jedoch normalerweise durch eine Verringerung der Anzahl der Iterationen aus, die zum Erreichen einer optimalen Lösung erforderlich sind. Es scheint auch sehr schnell zu konvergieren, wenn es nahe am Optimum liegt.

Ableitung[edit]

Die Ableitung dieses Abschnitts folgt dem Entwurf von Nocedal und Wright.[3]

 after-content-x4

Prädiktorschritt – Affine Skalierungsrichtung[edit]

Ein lineares Programm kann immer in der Standardform formuliert werden

Mindestxq((x)=cT.x,stEINx=b,x≥0,{ displaystyle { begin {align} & { underset {x} { min}} & q (x) & = c ^ {T} x, \ & { text {st}} & Ax & = b, \ & ; & x & geq 0, end {align}}}

wo

c∈R.n×1,EIN∈R.m×n{ displaystyle c in mathbb {R} ^ {n times 1}, ; A in mathbb {R} ^ {m times n}}

und

b∈R.m×1{ displaystyle b in mathbb {R} ^ {m times 1}}

Definieren Sie das Problem mit

m{ displaystyle m}

Einschränkungen und

n{ displaystyle n}

Gleichungen während

x∈R.n×1{ displaystyle x in mathbb {R} ^ {n times 1}}

ist ein Vektor von Variablen.

Die Karush-Kuhn-Tucker (KKT) Bedingungen für das Problem sind

EINT.λ+s=c,(Lagrange-Gradientenbedingung)EINx=b,(Machbarkeitsbedingung)X.S.e=0,(Komplementaritätsbedingung)((x,s)≥0,{ displaystyle { begin {align} A ^ {T} lambda + s & = c, ; ; ; { text {(Lagrange-Gradientenbedingung)}} \ Ax & = b, ; ; ; { text {(Machbarkeitsbedingung)}} \ XSe & = 0, ; ; ; { text {(Komplementaritätsbedingung)}} \ (x, s) & geq 0, end {align}} }}

wo

X.=diag((x){ displaystyle X = { text {diag}} (x)}

und

S.=diag((s){ displaystyle S = { text {diag}} (s)}

woher

e=((1,1,…,1)T.∈R.n×1{ displaystyle e = (1,1, dots, 1) ^ {T} in mathbb {R} ^ {n times 1}}

.

Diese Bedingungen können als Mapping umformuliert werden

F.::R.2n+m→R.2n+m{ displaystyle F: mathbb {R} ^ {2n + m} rightarrow mathbb {R} ^ {2n + m}}

wie folgt

F.((x,λ,s)=[ATλ+s−cAx−bXSe]=0((x,s)≥0{ displaystyle { begin {align} F (x, lambda, s) = { begin {bmatrix} A ^ {T} lambda + sc \ Ax-b \ XSe end {bmatrix}} & = 0 \ (x, s) & geq 0 end {align}}}

Die Prädiktor-Korrektor-Methode arbeitet dann unter Verwendung der Newton-Methode, um die affine Skalierungsrichtung zu erhalten. Dies wird erreicht, indem das folgende lineare Gleichungssystem gelöst wird

J.((x,λ,s)[ΔxaffΔλaffΔsaff]=– –F.((x,λ,s){ 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)}

wo

J.{ displaystyle J}

, definiert als

J.((x,λ,s)=[∇xF∇λF∇sF],{ displaystyle J (x, lambda, s) = { begin {bmatrix} nabla _ {x} F & nabla _ { lambda} F & nabla _ {s} F end {bmatrix}},}

ist der Jakobianer von F.

Somit wird das System

[0ATIA00S0X][ΔxaffΔλaffΔsaff]=[−rc−rb−XSe],rc=EINT.λ+s– –c,rb=EINx– –b{ displaystyle { begin {bmatrix} 0 & A ^ {T} & I \ A & 0 & 0 \ S & 0 & X end {bmatrix}} { begin {bmatrix} Delta x ^ { text {aff}} \ Delta lambda ^ { text {aff}} \ Delta s ^ { text {aff}} end {bmatrix}} = { begin {bmatrix} -r_ {c} \ – r_ {b} \ – XSe end {bmatrix}}, ; ; ; r_ {c} = A ^ {T} lambda + sc, ; ; ; r_ {b} = Axe-b}

Zentrierschritt[edit]

Der Durchschnittswert der Produkte

xichsich,ich=1,2,…,n{ displaystyle x_ {i} s_ {i}, ; i = 1,2, dots, n}

ein wichtiges Maß für die Wünschbarkeit eines bestimmten Satzes darstellen

((xk,sk){ displaystyle (x ^ {k}, s ^ ​​{k})}

(Die hochgestellten Zeichen bezeichnen den Wert der Iterationsnummer.

k{ displaystyle k}

der Methode). Dies wird als Dualitätsmaß bezeichnet und ist definiert durch

μ=1n∑ich=1nxichsich=xT.sn.{ displaystyle mu = { frac {1} {n}} sum _ {i = 1} ^ {n} x_ {i} s_ {i} = { frac {x ^ {T} s} {n }}.}

Für einen Wert des Zentrierungsparameters gilt

σ∈[0,1],{ displaystyle sigma in [0,1],}

Der Zentrierungsschritt kann als Lösung für berechnet werden

[0ATIA00S0X][ΔxcenΔλcenΔscen]=[−rc−rb−XSe+σμe]{ displaystyle { begin {bmatrix} 0 & A ^ {T} & I \ A & 0 & 0 \ S & 0 & X end {bmatrix}} { begin {bmatrix} Delta x ^ { text {cen}} \ Delta lambda ^ { text {cen}} \ Delta s ^ { text {cen}} end {bmatrix}} = { begin {bmatrix} -r_ {c} \ – r_ {b} \ – XSe + sigma mu e end {bmatrix}}}

Korrekturschritt[edit]

In Anbetracht des Systems, das zur Berechnung der oben definierten affinen Skalierungsrichtung verwendet wird, kann man feststellen, dass ein vollständiger Schritt in der affinen Skalierungsrichtung dazu führt, dass die Komplementaritätsbedingung nicht erfüllt ist:

((xich+Δxichaff)((sich+Δsichaff)=xichsich+xichΔsichaff+sichΔxichaff+ΔxichaffΔsichaff=ΔxichaffΔsichaff≠0.{ displaystyle left (x_ {i} + Delta x_ {i} ^ { text {aff}} right) left (s_ {i} + Delta s_ {i} ^ { text {aff}} right) = 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} ^ { text {aff}} = Delta x_ {i} ^ { text {aff}} Delta s_ {i} ^ { text {aff}} neq 0.}

Als solches kann ein System definiert werden, um einen Schritt zu berechnen, der versucht, diesen Fehler zu korrigieren. Dieses System stützt sich auf die vorherige Berechnung der affinen Skalierungsrichtung.

[0ATIA00S0X][ΔxcorΔλcorΔscor]=[00−ΔXaffΔSaffe]{ displaystyle { begin {bmatrix} 0 & A ^ {T} & I \ A & 0 & 0 \ S & 0 & X end {bmatrix}} { begin {bmatrix} Delta x ^ { text {cor}} \ Delta lambda ^ { text {cor}} \ Delta s ^ { text {cor}} end {bmatrix}} = { begin {bmatrix} 0 \ 0 \ – Delta X ^ { text {aff }} Delta S ^ { text {aff}} e end {bmatrix}}}

Aggregiertes System – Richtung des Mittelkorrektors[edit]

Die Prädiktor-, Korrektor- und Zentrierungsbeiträge zur rechten Seite des Systems können zu einem einzigen System zusammengefasst werden. Dieses System hängt von der vorherigen Berechnung der affinen Skalierungsrichtung ab, jedoch ist die Systemmatrix mit der des Prädiktorschritts identisch, so dass ihre Faktorisierung wiederverwendet werden kann.

Das aggregierte System ist

[0ATIA00S0X][ΔxΔλΔs]=[−rc−rb−XSe−ΔXaffΔSaffe+σμe]{ displaystyle { begin {bmatrix} 0 & A ^ {T} & I \ A & 0 & 0 \ S & 0 & X end {bmatrix}} { begin {bmatrix} Delta x \ Delta lambda \ Delta s end { bmatrix}} = { begin {bmatrix} -r_ {c} \ – r_ {b} \ – XSe- Delta X ^ { text {aff}} Delta S ^ { text {aff}} e + sigma mu e end {bmatrix}}}

Der Prädiktor-Korrektor-Algorithmus berechnet dann zuerst die affine Skalierungsrichtung. Zweitens löst es das aggregierte System, um die Suchrichtung der aktuellen Iteration zu erhalten.

Adaptive Auswahl des Zentrierparameters[edit]

Die affine Skalierungsrichtung kann verwendet werden, um eine Heuristik zu definieren, mit der der Zentrierungsparameter adaptiv als ausgewählt werden kann

σ=((μaffμ)3,{ displaystyle sigma = left ({ frac { mu _ { text {aff}}} { mu}} right) ^ {3},}

wo

μaff=((x+αaffpriΔxaff)T.((s+αaffDualΔsaff)T./.n,αaffpri=Mindest((1,Mindestich::Δxichaff<0– –xichΔxichaff),αaffDual=Mindest((1,Mindestich::Δsichaff<0– –sichΔsichaff),{ displaystyle { begin {align} mu _ { text {aff}} & = (x + alpha _ { text {aff}} ^ { text {pri}} Delta x ^ { text {aff }}) ^ {T} (s + alpha _ { text {aff}} ^ { text {dual}} Delta s ^ { text {aff}}) ^ {T} / n, \ alpha _ { text {aff}} ^ { text {pri}} & = min left (1, { underset {i: Delta x_ {i} ^ { text {aff}} <0} { min}} - { frac {x_ {i}} { Delta x_ {i} ^ { text {aff}}} right), \ alpha _ { text {aff}} ^ { text {dual}} & = min left (1, { underset {i: Delta s_ {i} ^ { text {aff}} <0} { min}} - { frac {s_ {i} } { Delta s_ {i} ^ { text {aff}}}} right), end {align}}}

Hier,

μaff{ displaystyle mu _ { text {aff}}}

ist das Dualitätsmaß des affinen Schrittes und

μ{ displaystyle mu}

ist das Dualitätsmaß der vorherigen Iteration.[3]

Schrittlängen[edit]

In praktischen Implementierungen wird eine Version der Zeilensuche durchgeführt, um die maximale Schrittlänge zu erhalten, die in Suchrichtung ausgeführt werden kann, ohne die Nicht-Negativität zu verletzen.

((x,s)≥0{ displaystyle (x, s) geq 0}

.[3]

Anpassung an die quadratische Programmierung[edit]

Obwohl die von Mehrotra vorgestellten Modifikationen für innere Punktalgorithmen für die lineare Programmierung gedacht waren, wurden die Ideen erweitert und auch erfolgreich auf die quadratische Programmierung angewendet.[3]

Verweise[edit]

  1. ^ Mehrotra, S. (1992). “Zur Implementierung einer Primal-Dual-Interior-Point-Methode”. SIAM Journal zur Optimierung. 2 (4): 575–601. doi:10.1137 / 0802028.
  2. ^ “1989 beschrieb Mehrotra einen praktischen Algorithmus für die lineare Programmierung, der die Grundlage der meisten aktuellen Software bleibt. Seine Arbeit erschien 1992.”

    Potra, Florian A.; Stephen J. Wright (2000). “Innenpunktmethoden”. Zeitschrift für Computergestützte und Angewandte Mathematik. 124 (1–2): 281–302. doi:10.1016 / S0377-0427 (00) 00433-7.

  3. ^ ein b c d Nocedal, Jorge; Wright, Stephen J. (2006). Numerische Optimierung. Vereinigte Staaten von Amerika: Springer. S. 392–417, 448–496. ISBN 978-0387-30303-1.


after-content-x4