[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki12\/2020\/12\/27\/mehrotra-pradiktor-korrektor-methode-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki12\/2020\/12\/27\/mehrotra-pradiktor-korrektor-methode-wikipedia\/","headline":"Mehrotra-Pr\u00e4diktor-Korrektor-Methode – Wikipedia","name":"Mehrotra-Pr\u00e4diktor-Korrektor-Methode – Wikipedia","description":"before-content-x4 Mehrotra-Pr\u00e4diktor-Korrektor-Methode Bei der Optimierung handelt es sich um eine spezielle Innenpunktmethode f\u00fcr die lineare Programmierung. Es wurde 1989 von","datePublished":"2020-12-27","dateModified":"2020-12-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki12\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki12\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c4df87d9031bd91758a2a576ecc6ede098d36270","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c4df87d9031bd91758a2a576ecc6ede098d36270","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki12\/2020\/12\/27\/mehrotra-pradiktor-korrektor-methode-wikipedia\/","wordCount":8621,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Mehrotra-Pr\u00e4diktor-Korrektor-Methode Bei der Optimierung handelt es sich um eine spezielle Innenpunktmethode f\u00fcr die lineare Programmierung.  Es wurde 1989 von Sanjay Mehrotra vorgeschlagen.[1]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Das Verfahren basiert auf der Tatsache, dass bei jeder Iteration eines inneren Punktalgorithmus die Cholesky-Zerlegung (Faktorisierung) einer gro\u00dfen 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\u00e4diktor-Korrektor-Methode von Mehrotra dieselbe Cholesky-Zerlegung, um zwei verschiedene Richtungen zu finden: einen Pr\u00e4diktor und einen Korrektor.Die Idee ist, zuerst eine optimierende Suchrichtung basierend auf einem Term erster Ordnung (Pr\u00e4diktor) zu berechnen.  Die Schrittgr\u00f6\u00dfe, die in diese Richtung genommen werden kann, wird verwendet, um zu bewerten, wie viel Zentralit\u00e4tskorrektur erforderlich ist.  Dann wird ein Korrektorterm berechnet: Dieser enth\u00e4lt sowohl einen Zentralit\u00e4tsterm als auch einen Term zweiter Ordnung.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Die vollst\u00e4ndige Suchrichtung ist die Summe aus Pr\u00e4diktorrichtung und Korrektorrichtung.Obwohl noch keine theoretische Komplexit\u00e4t daran gebunden ist, ist die Pr\u00e4diktor-Korrektor-Methode von Mehrotra in der Praxis weit verbreitet.[2]  Sein Korrektorschritt verwendet auf effektive Weise dieselbe Cholesky-Zerlegung, die w\u00e4hrend des Pr\u00e4diktorschritts gefunden wurde, und ist daher nur unwesentlich teurer als ein Standard-Innenpunktalgorithmus.  Der zus\u00e4tzliche Aufwand pro Iteration zahlt sich jedoch normalerweise durch eine Verringerung der Anzahl der Iterationen aus, die zum Erreichen einer optimalen L\u00f6sung erforderlich sind.  Es scheint auch sehr schnell zu konvergieren, wenn es nahe am Optimum liegt.Table of ContentsAbleitung[edit]Pr\u00e4diktorschritt – Affine Skalierungsrichtung[edit]Zentrierschritt[edit]Korrekturschritt[edit]Aggregiertes System – Richtung des Mittelkorrektors[edit]Adaptive Auswahl des Zentrierparameters[edit]Schrittl\u00e4ngen[edit]Anpassung an die quadratische Programmierung[edit]Verweise[edit]Ableitung[edit]Die Ableitung dieses Abschnitts folgt dem Entwurf von Nocedal und Wright.[3]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Pr\u00e4diktorschritt – Affine Skalierungsrichtung[edit]Ein lineares Programm kann immer in der Standardform formuliert werdenMindestxq((x)=cT.x,stEINx=b,x\u22650,{ displaystyle { begin {align} & { underset {x} { min}} & q (x) & = c ^ {T} x, \\ & { text {st}} & Ax & = b, \\ & ; & x &  geq 0,  end {align}}}wo c\u2208R.n\u00d71,EIN\u2208R.m\u00d7n{ displaystyle c  in  mathbb {R} ^ {n  times 1}, ; A  in  mathbb {R} ^ {m  times n}}  und b\u2208R.m\u00d71{ displaystyle b  in  mathbb {R} ^ {m  times 1}}  Definieren Sie das Problem mit m{ displaystyle m}  Einschr\u00e4nkungen und n{ displaystyle n}  Gleichungen w\u00e4hrend x\u2208R.n\u00d71{ displaystyle x  in  mathbb {R} ^ {n  times 1}}  ist ein Vektor von Variablen.Die Karush-Kuhn-Tucker (KKT) Bedingungen f\u00fcr das Problem sindEINT.\u03bb+s=c,(Lagrange-Gradientenbedingung)EINx=b,(Machbarkeitsbedingung)X.S.e=0,(Komplementarit\u00e4tsbedingung)((x,s)\u22650,{ displaystyle { begin {align} A ^ {T}  lambda + s & = c, ; ; ; { text {(Lagrange-Gradientenbedingung)}} \\ Ax & = b, ; ; ; { text {(Machbarkeitsbedingung)}} \\ XSe & = 0, ; ; ; { text {(Komplementarit\u00e4tsbedingung)}} \\ (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,\u2026,1)T.\u2208R.n\u00d71{ displaystyle e = (1,1,  dots, 1) ^ {T}  in  mathbb {R} ^ {n  times 1}}.Diese Bedingungen k\u00f6nnen als Mapping umformuliert werden F.::R.2n+m\u2192R.2n+m{ displaystyle F:  mathbb {R} ^ {2n + m}  rightarrow  mathbb {R} ^ {2n + m}}  wie folgtF.((x,\u03bb,s)=[AT\u03bb+s\u2212cAx\u2212bXSe]=0((x,s)\u22650{ 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\u00e4diktor-Korrektor-Methode arbeitet dann unter Verwendung der Newton-Methode, um die affine Skalierungsrichtung zu erhalten.  Dies wird erreicht, indem das folgende lineare Gleichungssystem gel\u00f6st wirdJ.((x,\u03bb,s)[\u0394xaff\u0394\u03bbaff\u0394saff]=– –F.((x,\u03bb,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 alsJ.((x,\u03bb,s)=[\u2207xF\u2207\u03bbF\u2207sF],{ 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][\u0394xaff\u0394\u03bbaff\u0394saff]=[\u2212rc\u2212rb\u2212XSe],rc=EINT.\u03bb+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,\u2026,n{ displaystyle x_ {i} s_ {i}, ; i = 1,2,  dots, n}  ein wichtiges Ma\u00df f\u00fcr die W\u00fcnschbarkeit eines bestimmten Satzes darstellen ((xk,sk){ displaystyle (x ^ {k}, s ^ \u200b\u200b{k})}  (Die hochgestellten Zeichen bezeichnen den Wert der Iterationsnummer. k{ displaystyle k}der Methode).  Dies wird als Dualit\u00e4tsma\u00df bezeichnet und ist definiert durch\u03bc=1n\u2211ich=1nxichsich=xT.sn.{ displaystyle  mu = { frac {1} {n}}  sum _ {i = 1} ^ {n} x_ {i} s_ {i} = { frac {x ^ {T} s} {n }}.}F\u00fcr einen Wert des Zentrierungsparameters gilt \u03c3\u2208[0,1],{ displaystyle  sigma  in [0,1],}  Der Zentrierungsschritt kann als L\u00f6sung f\u00fcr berechnet werden[0ATIA00S0X][\u0394xcen\u0394\u03bbcen\u0394scen]=[\u2212rc\u2212rb\u2212XSe+\u03c3\u03bce]{ 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\u00e4ndiger Schritt in der affinen Skalierungsrichtung dazu f\u00fchrt, dass die Komplementarit\u00e4tsbedingung nicht erf\u00fcllt ist:((xich+\u0394xichaff)((sich+\u0394sichaff)=xichsich+xich\u0394sichaff+sich\u0394xichaff+\u0394xichaff\u0394sichaff=\u0394xichaff\u0394sichaff\u22600.{ 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\u00fctzt sich auf die vorherige Berechnung der affinen Skalierungsrichtung.[0ATIA00S0X][\u0394xcor\u0394\u03bbcor\u0394scor]=[00\u2212\u0394Xaff\u0394Saffe]{ 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\u00e4diktor-, Korrektor- und Zentrierungsbeitr\u00e4ge zur rechten Seite des Systems k\u00f6nnen zu einem einzigen System zusammengefasst werden.  Dieses System h\u00e4ngt von der vorherigen Berechnung der affinen Skalierungsrichtung ab, jedoch ist die Systemmatrix mit der des Pr\u00e4diktorschritts identisch, so dass ihre Faktorisierung wiederverwendet werden kann.Das aggregierte System ist[0ATIA00S0X][\u0394x\u0394\u03bb\u0394s]=[\u2212rc\u2212rb\u2212XSe\u2212\u0394Xaff\u0394Saffe+\u03c3\u03bce]{ 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\u00e4diktor-Korrektor-Algorithmus berechnet dann zuerst die affine Skalierungsrichtung.  Zweitens l\u00f6st 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\u00e4hlt werden kann\u03c3=((\u03bcaff\u03bc)3,{ displaystyle  sigma =  left ({ frac { mu _ { text {aff}}} { mu}}  right) ^ {3},}wo\u03bcaff=((x+\u03b1affpri\u0394xaff)T.((s+\u03b1affDual\u0394saff)T.\/.n,\u03b1affpri=Mindest((1,Mindestich::\u0394xichaffxichaff),\u03b1affDual=Mindest((1,Mindestich::\u0394sichaffsichaff),{ 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}} { displaystyle  mu}  ist das Dualit\u00e4tsma\u00df der vorherigen Iteration.[3]Schrittl\u00e4ngen[edit]In praktischen Implementierungen wird eine Version der Zeilensuche durchgef\u00fchrt, um die maximale Schrittl\u00e4nge zu erhalten, die in Suchrichtung ausgef\u00fchrt werden kann, ohne die Nicht-Negativit\u00e4t zu verletzen. ((x,s)\u22650{ displaystyle (x, s)  geq 0}.[3]Anpassung an die quadratische Programmierung[edit]Obwohl die von Mehrotra vorgestellten Modifikationen f\u00fcr innere Punktalgorithmen f\u00fcr die lineare Programmierung gedacht waren, wurden die Ideen erweitert und auch erfolgreich auf die quadratische Programmierung angewendet.[3]Verweise[edit]^ Mehrotra, S. (1992).  “Zur Implementierung einer Primal-Dual-Interior-Point-Methode”. SIAM Journal zur Optimierung. 2 (4): 575\u2013601.  doi:10.1137 \/ 0802028.^ “1989 beschrieb Mehrotra einen praktischen Algorithmus f\u00fcr 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\u00fcr Computergest\u00fctzte und Angewandte Mathematik. 124 (1\u20132): 281\u2013302.  doi:10.1016 \/ S0377-0427 (00) 00433-7.^ ein b c d Nocedal, Jorge;  Wright, Stephen J. (2006). Numerische Optimierung.  Vereinigte Staaten von Amerika: Springer.  S. 392\u2013417, 448\u2013496.  ISBN 978-0387-30303-1.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki12\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki12\/2020\/12\/27\/mehrotra-pradiktor-korrektor-methode-wikipedia\/#breadcrumbitem","name":"Mehrotra-Pr\u00e4diktor-Korrektor-Methode – Wikipedia"}}]}]