Gauß-Newton-Verfahren

Das Gauß-Newton-Verfahren (nach Carl Friedrich Gauß und Isaac Newton) ist ein numerisches Verfahren zur Lösung nichtlinearer Minimierungsprobleme nach der Methode der kleinsten Quadrate. Das Verfahren ist verwandt mit dem Newton-Verfahren zur Lösung nichtlinearer Optimierungsprobleme, hat jedoch den Vorteil, dass die für das Newton-Verfahren notwendige Berechnung der 2. Ableitung entfällt. Speziell für große Probleme mit mehreren zehntausend Parametern ist die Berechnung der 2. Ableitung oft ein limitierender Faktor.

Das Optimierungsproblem

Das Gauß-Newton-Verfahren löst Probleme, bei denen das Minimum einer Summe von Quadraten stetig differenzierbarer Funktionen gesucht ist, also

mit . Mit der euklidischen Norm lässt sich das auch schreiben als

mit . Probleme dieser Form kommen in der Praxis häufig vor, insbesondere ist das nichtlineare Problem äquivalent zur Minimierung von unter der Voraussetzung, dass eine Nullstelle besitzt.

Das Gauß-Newton-Verfahren wird sehr häufig verwendet, um nichtlineare Ausgleichsprobleme zu lösen. In diesem Fall ergeben sich die Komponentenfunktionen als Abweichung einer Modellfunktion von bekannten Beobachtungen bzw. Messwerten , also . Ist die Modellfunktion eine lineare Abbildung, ergibt sich der Standardfall der Methode der kleinsten Quadrate mit linearer Modellfunktion.

Die Methode

Die Grundidee des Gauß-Newton-Verfahrens besteht darin, die Zielfunktion zu linearisieren und die Linearisierung im Sinne der kleinsten Quadrate zu optimieren. Die Linearisierung, also die Taylorentwicklung 1. Ordnung, von im Punkt lautet

.

Die Matrix ist die Jacobi-Matrix und wird oft mit bezeichnet. Man erhält das lineare kleinste-Quadrate Problem

,

mit Gradient .

Nullsetzen des Gradienten liefert die sogenannten Normalgleichungen

mit der expliziten Lösung

.

Daraus ergibt sich direkt der Gauß-Newton-Iterationsschritt

wobei deutlich macht, dass die Jacobi-Matrix an der Stelle ausgewertet wird und eine Schrittweite ist.

Ein weiterer Vorteil ist, dass die Suchrichtung immer eine Abstiegsrichtung ist, solange den vollen Rang hat. Dies liegt daran, dass positiv semidefinit ist, was bedeutet, dass auch positiv semidefinit ist, was bedeutet, dass

Wenn den vollen Rang hat, ist die linke Seite dieser Ungleichung kleiner als die rechte Seite. Dies deutet darauf hin, dass das Gauß-Newton-Verfahren typischerweise robuster ist als das Newtonverfahren. Es gibt jedoch immer noch keine Garantie dafür, dass das Gauß-Newton-Verfahren im Allgemeinen konvergiert.[1]

Um das lineare Gleichungssystem im Gauß-Newton-Iterationsschritt zu lösen, gibt es verschiedene Möglichkeiten abhängig von der Problemgröße und der Struktur:[2]

  • Kleine Probleme () werden am besten mit der QR-Zerlegung gelöst
  • Für große Probleme bietet sich die Cholesky-Zerlegung an, da die Matrix per Konstruktion symmetrisch ist. Für dünnbesetzte gibt es speziell angepasste Cholesky-Varianten
  • Als allgemeine Möglichkeit kann das CG-Verfahren verwendet werden, wobei hier üblicherweise eine Vorkonditionierung notwendig ist

Konvergenz

Der Update-Vektor im Gauß-Newton-Iterationsschritt hat die Form , wobei . Wenn vollen Rang hat, so ist und damit auch positiv definit. Andererseits ist der Gradient des quadratischen Problems , somit ist eine Abstiegsrichtung, d. h., es gilt . Daraus folgt (bei geeigneter Wahl der Schrittweite ) die Konvergenz der Gauß-Newton-Methode zu einem stationären Punkt. Aus dieser Darstellung lässt sich auch erkennen, dass die Gauß-Newton Methode im Wesentlichen ein skaliertes Gradientenverfahren mit der positiv definiten Skalierungsmatrix ist.

Über die Konvergenzgeschwindigkeit kann im Allgemeinen keine Aussage getroffen werden. Falls der Startpunkt sehr weit vom Optimum entfernt ist oder die Matrix schlecht konditioniert ist, so konvergiert die Gauß-Newton-Methode u. U. nur sublinear. In vielen praktischen Anwendungsfällen konvergiert die Gauß-Newton-Methode jedoch wesentlich schneller und kann in manchen Fällen sogar dieselbe quadratische Konvergenz wie die Newton-Methode erreichen. Dies ist aus der Verwandtschaft zur Newton-Methode ersichtlich: Die Taylorentwicklung 2. Ordnung der Zielfunktion lautet

wobei die Hesse-Matrix im Punkt ist. Für den Fall, dass klein ist (z. B. wenn fast linear ist, oder wenn die Komponentenfunktionen in der Nähe des Optimums sehr klein sind), kann der quadratische Term vernachlässigt werden und die Gauß-Newton-Methode konvergiert superlinear. Gilt im optimalen Punkt dass , dann ist der entsprechende Newton-Schritt identisch mit dem Gauss-Newton-Schritt und die Konvergenz der Gauß-Newton-Methode ist quadratisch.

Erweiterung

Um das Verhalten im Fall von schlecht konditionierten bzw. singulären zu verbessern, kann der Gauß-Newton-Iterationsschritt folgendermaßen modifiziert werden

,

wobei die Diagonalmatrix so gewählt wird, dass positiv definit ist. Mit der Wahl , also einem skalaren Vielfachen der Identitätsmatrix, erhält man den Levenberg-Marquardt-Algorithmus.

Beispiel

Die Rosenbrock-Funktion mit .

Die Rosenbrock-Funktion

wird häufig als Test für Optimierungsmethoden verwendet, da sie wegen des schmalen und flachen Tals, in welchem iterative Methoden nur kleine Schritte machen können, eine Herausforderung darstellt. Die Konstanten werden üblicherweise mit gewählt, das globale Optimum liegt in diesem Fall bei mit dem Funktionswert .

Um die Gauß-Newton-Methode anzuwenden, muss die Rosenbrock-Funktion zunächst in die Form "Summe von Quadraten von Funktionen" gebracht werden. Da die Rosenbrock-Funktion bereits aus einer Summe von zwei Termen besteht, wählt man den Ansatz

und

.

Das Gauß-Newton-Problem für die Rosenbrock-Funktion lautet somit

wobei .

Die Jacobi-Matrix ergibt sich als und damit ist . Da vollen Rang hat, ist positiv definit und die Inverse existiert. Zur Bestimmung der Schrittweite kommt folgende einfache Liniensuche zum Einsatz:

  1. Starte mit .
  2. Berechne den neuen Punkt mit .
  3. Wenn setze und gehe zur nächsten Iteration.
  4. Ansonsten halbiere und gehe zu 2.

Die Liniensuche erzwingt, dass der neue Funktionswert kleiner als der vorherige ist; sie terminiert garantiert (mit ev. sehr kleinem ), da eine Abstiegsrichtung ist.

Als Startpunkt wird gewählt. Die Gauß-Newton-Methode konvergiert in wenigen Iterationen zum globalen Optimum:

Optimierung der Rosenbrock-Funktion mit der Gauß-Newton Methode
Optimierung mit Gauß-Newton Methode
0 (0, -0.1) 2
1 (0.1250, -0.0875) 1.8291
2 (0.2344, -0.0473) 1.6306
3 (0.4258, 0.0680) 1.6131
4 (0.5693, 0.2186) 1.3000
5 (0.7847, 0.5166) 1.0300
6 (1.0, 0.9536) 0.2150
7 (1.0, 1.0) 1.1212e-27

Das Gradientenverfahren (mit derselben Liniensuche) liefert im Vergleich dazu folgendes Ergebnis, es findet selbst nach 500 Iterationen nicht zum Optimum:

Optimierung der Rosenbrock-Funktion mit dem Gradientenverfahren
Optimierung mit Gradientenverfahren
0 (0, -0.1) 2
1 (0.0156, 0.0562) 1.2827
2 (0.0337, -0.0313) 1.0386
3 (0.0454, 0.0194) 0.9411
4 (0.0628, -0.0077) 0.8918
5 (0.0875, 0.0286) 0.8765
500 (0.8513, 0.7233) 0.0223

Literatur

  • Dimitri P. Bertsekas: Nonlinear Programming. Second Edition, Athena Scientific, 1995, ISBN 978-1-886529-14-4.
  • Yurii Nesterov: Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, 2003, ISBN 978-1-4419-8853-9.
  • Jorge Nocedal, Stephen Wright: Numerical Optimization. Springer Science & Business Media, 2000, ISBN 978-0-387-98793-4.
  • Amir Beck: Introduction to Nonlinear Optimization. SIAM, 2014, ISBN 978-1-61197-364-8.

Einzelnachweise

  1. Michael S. Floater, Universität Oslo: Non-linear least squares and the Gauss-Newton method
  2. Ceres Solver Dokumentation. Abgerufen am 10. Mai 2019.

Read other articles:

アルファロメオ・アルファスッド アルファスッド・ベルリーナ前期型 アルファスッド・ベルリーナ後期型 アルファスッド・スプリント後期型概要販売期間 1971年 - 1989年デザイン イタルデザイン・ジウジアーロボディ乗車定員 5人ボディタイプ 2/4ドアファストバックセダン3/5ドアハッチバック3ドアファストバッククーペ駆動方式 FFパワートレインエンジン 水平対向4気...

 

Cet article est une ébauche concernant les réserves naturelles et autres zones protégées, la liste du patrimoine mondial et le Honduras. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Réserve de la biosphère Río PlátanoGéographiePays HondurasDépartements Colón,Gracias a DiosCoordonnées 15° 44′ 40″ N, 84° 40′ 30″ OSuperficie 8 000 km2Partie de Corridor...

 

France Info Eslogan Et tout est plus clair. (Todo es más claro)[1]​Programación NoticiasPropietario Gobierno francésOperado por France TélévisionsPaís  FranciaIdioma FrancésFundación 1 de septiembre de 2016Inicio de transmisiones 1 de septiembre de 2016 (7 años)Formato de imagen 1080i HDTV(reescalado a 16:9 576i para la señal en resolución estándar)Área de transmisión Francia metropolitanaUbicación ParísSitio web francetvinfo.fr[editar datos en Wikidata&#x...

Vorlage:Infobox hochrangige Straße/Wartung/AT-B Landesstraße B131 in Österreich Basisdaten Gesamtlänge: 14,5 km Bundesland: Oberösterreich Straßenverlauf Bezirk Urfahr-Umgebung Ottensheim Rodl Mühllackener Straße Feldkirchen an der Donau Donau Bezirk Eferding Aschach an der Donau Hartkirchen Die Aschacher Straße (B 131) ist eine Landesstraße in Österreich. Sie führt auf einer Länge von 14,5 km durch das Mühlviertel in Oberösterreich. Die Aschacher Straße beginnt in O...

 

Jürgen Becker 2019 Jürgen Becker (2009) Jürgen Becker (2007) Am 9. Juli 2011 in Wolfenbüttel Am 9. Juli 2011 in Wolfenbüttel Jürgen Becker (* 27. August 1959 in Köln) ist ein deutscher Kabarettist, Autor und Fernsehmoderator. Inhaltsverzeichnis 1 Leben 1.1 Karneval und Kabarett 2 Engagement 3 Ehrungen 4 Bühnenprogramme (Auswahl) 5 Veröffentlichte Werke 5.1 Diskografie 5.2 Bibliographie 5.3 Filme 5.4 Biographie 6 Weblinks 7 Einzelnachweise Leben Becker blieb als Schüler zweimal sitze...

 

This article uses bare URLs, which are uninformative and vulnerable to link rot. Please consider converting them to full citations to ensure the article remains verifiable and maintains a consistent citation style. Several templates and tools are available to assist in formatting, such as reFill (documentation) and Citation bot (documentation). (August 2022) (Learn how and when to remove this template message) Emblem of Volkssport, inspired by German Sturmabteilung The Volkssport (German Verb...

العلاقات الليختنشتانية المالاوية ليختنشتاين مالاوي   ليختنشتاين   مالاوي تعديل مصدري - تعديل   العلاقات الليختنشتانية المالاوية هي العلاقات الثنائية التي تجمع بين ليختنشتاين ومالاوي.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية ل...

 

2018 film by M. A. Nishad Kinar / KeniDirected byM. A. NishadScreenplay byAnwar AbdullaAju K. NarayananProduced bySajeev P. K.Anne SajeevStarringJaya PradaRevathiCinematographyNoushad SherifEdited bySreekumar NairMusic byBijibalProductioncompanyFragrant Nature Film CreationsRelease date 23 February 2018 (2018-02-23) CountryIndiaLanguagesMalayalamTamil Kinar (Well in Malayalam), titled Keni (transl. Well in Tamil) in, is a 2018 Indian drama film co-written and directed by ...

 

Mexican-American accordionist and pioneer of conjunto music Narciso MartínezNarciso MartínezBackground informationBorn(1911-10-29)October 29, 1911[1]Reynosa, Mexico[1]DiedJune 5, 1992(1992-06-05) (aged 80) [2]San Benito, Texas[2]Genresconjunto musicOccupationsaccordionistInstrumentsaccordionLabelsBluebirdMusical artist Narciso Martínez (October 29, 1911 in Reynosa, Mexico[1] – June 5, 1992 in San Benito, Texas[2]), whose nickname was E...

LivignoKomuneComune di LivignoNegara ItaliaWilayahLombardyProvinsiSondrio (SO)FrazioniTrepallePemerintahan • Wali kotaDamiano BormoliniLuas • Total211 km2 (81 sq mi)Ketinggian1.816 m (5,958 ft)Populasi (31 December 2004) • Total5.326 • Kepadatan25/km2 (65/sq mi)DemonimLivignaschiZona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST)Kode pos23030Kode area telepon0342Santo/a PelindungSanta Maria /...

 

Luo Nilotic ethnic group in the East AfricaThis article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Anuak people – news · newspapers · books · scholar · JSTOR (June 2020) (Learn how and when to remove this template message) AnyuakAnywaak children in Dimma, EthiopiaTotal population250,000-300,000[1]Regions wit...

 

For other uses, see Crime Wave. 1996 video gameCrimeWaveDeveloper(s)Eidos InteractivePublisher(s)Eidos InteractiveDesigner(s)Jim BlacklerArtist(s)Joe GroombridgeDavid BannerComposer(s)Joe MyersMike AshPlatform(s)Sega SaturnReleaseEU: November 8, 1996NA: March 10, 1997[1]Genre(s)Vehicular combatMode(s)Single-player CrimeWave is a vehicular combat video game, developed and published by Eidos Interactive, released as a Sega Saturn exclusive in 1996-1997. Gameplay Gameplay screenshot. The...

Deadly suspension bridge collapse due to human error. Kutai Kartanegara BridgeThe bridge as of 2016Coordinates0°26′40″S 117°00′10″E / 0.444433°S 117.00288°E / -0.444433; 117.00288CrossesMahakam RiverLocaleKutai Kartanegara Regency, East Kalimantan, IndonesiaOfficial nameKutai Kartanegara ing Martadipura BridgeCharacteristicsDesignSuspension bridge[1] (original) Arch bridge[1] (new)MaterialSteel[1]Total length710 m (2,329 ft...

 

American college football season 2016 Cornell Big Red footballConferenceIvy LeagueRecord4–6 (2–5 Ivy)Head coachDavid Archer (4th season)Offensive coordinatorRoy Istvan (3rd season)Defensive coordinatorJared Backus (4th season)CaptainMiles Norris, Ben Rogers, Matt Sullivan, Jackson WeberHome stadiumSchoellkopf Field(Capacity: 25,597)Seasons← 20152017 → 2016 Ivy League football standings vte Conf Overall Team   W   L     W  ...

 

This article is about the book by Donald Wandrei. For concept in Japanese Buddhism, see Trikaya. Three Mysteries First editionAuthorDonald WandreiCountryUnited StatesLanguageEnglishGenreDetective fictionPublisherF & B MysteryPublication date2000Media typePrint (paperback)Pages38 ppOCLC51309341 Three Mysteries is a collection of mystery stories by author Donald Wandrei. It was released in 2000 by F & B Mystery in an edition of 125 copies of which 100 were released in a slipcase wi...

Leah DanielsBackground informationBorn (1987-12-25) December 25, 1987 (age 35)OriginUxbridge, Ontario, CanadaGenres Pop country Occupation(s)Singer-songwriter, musicianInstrument(s) Vocals piano guitar Years active1996–presentLabelsIndependentMusical artist Leah Daniels (born December 25, 1987)[1] is a Canadian country music singer and songwriter. She is an independent recording artist. Her self-titled debut was released in November 2011 and her debut single was released in Feb...

 

Pin badge to encourage communication in the Irish language This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Fáinne – news · newspapers · books · scholar · JSTOR (January 2016) (Learn how and when to remove this template message) Piaras Béaslaí wearing An Fáinne. Fáinne (Irish: [ˈfˠaːn̠ʲə]; ...

 

Handheld video game console for children This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: LeapFrog Didj – news · newspapers · books · scholar · JSTOR (May 2014) (Learn how and when to remove this template message) LeapFrog DidjManufacturerLeapFrog EnterprisesTypeHandheld game consoleRelease dateAugust 22...

2023 Nepalese film directed by Nischal Basnet Dimag KharabTheatrical release posterNepaliदिमाग खराब Directed byNischal BasnetScreenplay byAakash BaralProduced byRaunak Bikram KandelStarringDayahang RaiKhagendra LamichhaneSwastima KhadkaArpan ThapaBijay BaralCinematographySusan PrajapatiEdited byNimesh ShresthaProductioncompaniesBlack Horse Pictures Pvt.Ltd.Cinema art Pvt.Ltd.Release date November 10, 2023 (2023-11-10) (Nepal) CountryNepalLanguageNepali Dim...

 

Erzsébetliget TheatreAddressErzsébetligetLocationBudapest, Pest county, HungaryCoordinates47°30′36″N 19°12′15″E / 47.50998°N 19.20422°E / 47.50998; 19.20422TypeTheatreConstructionBuilt1956Opened1956WebsiteErzsébetliget Theatre The Erzsébetliget Theatre (Hungarian: Erzsébetligeti Színház) is a theatre in Mátyásföld, Budapest. History The English-Hungarian indie rock band, Dawnstar, played three shows at the theatre in 2006. The third concert was pa...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!