Konvexe Optimierung in der Geodäsie

Die Arbeit behandelt konvexe Optimierung für Ausgleichungsaufgaben unter Ungleichungsrestriktionen. Der Fokus liegt auf der Anwendung in der Geodäsie, wo solche Methoden trotz ihrer Verbreitung in anderen Disziplinen (Ökonomie, Ingenieurwissenschaften) bisher kaum Einzug gehalten haben. Die Minimierung der Verbesserungsquadratsumme oder die Maximierung von Likelihood-Funktionen sind zentrale Beispiele in der Geodäsie. Oft existieren zusätzliche Informationen über die unbekannten Parameter, die sich als Ungleichungen ausdrücken lassen (z.B. Nicht-Negativität von Dichten oder obere Schranken für Steigungen). Herkömmliche Ansätze, die den Einfluss inaktiver Restriktionen vernachlässigen oder die Wahrscheinlichkeitsmasse im unzulässigen Bereich ignorieren, sind unvollständig. Daher wird eine neue Methode (MC-QP) vorgeschlagen, um diese Nachteile zu überwinden. Die Arbeit erwähnt wichtige Beiträge von Werner (1990), Werner und Yapar (1996) sowie Wong (2011) zur Lösung von Problemen mit rangdefizienten Systemen und Ungleichungsrestriktionen, wobei letztere Active-Set-Methoden für die quadratische Programmierung erweitern. Die Arbeit betont den Unterschied zwischen Ungleichungen als Restriktionen für zu schätzende Größen und dem Konzept des „Censoring“ bei unvollständigen Daten.

Es existiert umfangreiche Literatur zur konvexen Optimierung (Gill et al., 1981; Fletcher, 1987; Boyd und Vandenberghe, 2004). Ein Spezialfall ist die quadratische Programmierung (QP), bei der eine quadratische Zielfunktion unter linearen Restriktionen minimiert wird (Simon und Simon, 2003; Wong, 2011). Wong (2011) untersuchte Active-Set-Methoden für positiv (semi-)definite und indefinite Systeme. Weitere Ansätze zur Behandlung von Ungleichungsrestriktionen werden diskutiert, z.B. die Methode von Peng et al. (2006), die mehrere einfache Ungleichungen zu einer komplexen Gleichung zusammenfasst. Koch (2006) formulierte Restriktionen für die semantische Integration von 2D-Objekten und digitalen Geländemodellen, während Kaschenz (2006) Ungleichungsrestriktionen als Alternative zur Tikhonov-Regularisierung einsetzte (Nicht-negative Least-Squares). Tang et al. (2012) verwendeten Ungleichungen als Glättungsrestriktionen bei der GRACE-Datenanalyse. Die Literatur zur Qualitätsbeschreibung von Schätzungen unter Ungleichungsrestriktionen ist spärlicher; Liew (1976) schlug einen frequentistischen Ansatz vor, während Geweke (1986) einen Bayes'schen Ansatz vorschlug (weiterentwickelt von Zhu et al., 2005 in der Geodäsie). Die Arbeit entschied sich, die allgemeinste Version des Gauss-Helmert-Modells zu behandeln.

Die Arbeit konzentriert sich auf Active-Set-Methoden zur Lösung von Optimierungsproblemen mit Ungleichungsrestriktionen. Im Gegensatz zu Problemen ohne oder mit Gleichheitsrestriktionen ist bei Ungleichungsrestriktionen im Voraus nicht bekannt, welche Restriktionen aktiv sein werden, was iterative Algorithmen notwendig macht. Active-Set-Methoden verfolgen iterativ den Rand des zulässigen Bereichs im Parameterraum, bis die optimale Lösung gefunden ist. Dabei wird die Menge der als Gleichungen geltenden Restriktionen (aktive Menge) extrahiert und eine Folge von Problemen mit Gleichheitsrestriktionen gelöst (Wong, 2011). Das Vorzeichen der Lagrange-Multiplikatoren ist entscheidend, um inaktive Restriktionen zu identifizieren. Negative Lagrange-Multiplikatoren zeigen an, welche Ungleichungsrestriktionen deaktiviert werden sollten, um die Zielfunktion weiter zu minimieren. Gleichheitsrestriktionen bleiben immer aktiv. Alternativen zu den beschriebenen Active-Set-Methoden sind Standard-Löser für LP, QP oder LCP-Probleme, die jedoch meist langsamer konvergieren. Die Qualitätsbeschreibung stellt eine besondere Herausforderung dar, da die Fehlerfortpflanzung nicht mehr analytisch angewendet werden kann; stattdessen werden iterative Löser und Monte-Carlo-Methoden eingesetzt. Konfidenzregionen können jedoch auch in beschnittenen Parameterräumen angegeben werden.

Ein weiterer Schwerpunkt liegt auf der Behandlung rangdefizierter Systeme mit Ungleichungsrestriktionen. Im Gegensatz zum unbeschränkten Fall, wo die allgemeine Lösung mit Hilfe verallgemeinerter Inverser berechnet werden kann (Koch, 1999), ist dies bei Ungleichungsrestriktionen nicht möglich. Die meisten gängigen Optimierungsalgorithmen (Active-Set-Methoden, Interior-Point-Methoden) können mit rangdefizienten Zielfunktionen nicht umgehen oder liefern nur eine partikuläre Lösung. Die Arbeit schlägt einen zweistufigen Ansatz vor: Zuerst wird die allgemeine Lösung des unbeschränkten Problems berechnet. Anschließend werden die Ungleichungsrestriktionen berücksichtigt, wobei ein zweites Optimierungsproblem gelöst wird, abhängig davon, ob sich die Lösungsmannigfaltigkeit und der zulässige Bereich schneiden. Der vorgeschlagene Ansatz bietet Vorteile: Beschreibung der Mannigfaltigkeit unter Berücksichtigung der Restriktionen, zusätzliche Nullraumoptimierung für eine partikuläre Lösung mit bestimmten Eigenschaften (z.B. Sparsität), Skalierbarkeit und Erkennung von Dimensionsreduktionen der Mannigfaltigkeit durch die Ungleichungsrestriktionen. Die Arbeit verweist auf Arbeiten von Werner und Yapar (1996) und diskutiert die Unterschiede zu anderen Ansätzen wie denen von Best (1984) und O’Leary und Rust (1986).

Die Arbeit demonstriert die Anwendbarkeit der entwickelten Methoden anhand verschiedener Beispiele. Der Huber-Schätzer, reformuliert als quadratisches Programm, dient als Beispiel für robuste Schätzung unter Ungleichungsrestriktionen. Weitere Anwendungen umfassen die Schätzung positiver definiter Kovarianzfunktionen und die VLBI-Ausgleichung mit Restriktionen für troposphärische Verzögerungen (Halsig et al., 2015). Auch die Optimierung geodätischer Netze und ein Ingenieurbeispiel mit Schweißtoleranzen werden behandelt, die zu rangdefizienten Systemen führen. Das Gauss-Helmert-Modell mit Ungleichungsrestriktionen (ICGHM) wird detailliert behandelt, wobei eine effiziente Reformulierung als quadratisches Programm vorgeschlagen wird. Die Arbeit zeigt, dass die Einführung von Ungleichungen, kombiniert mit den neuen Methoden, in zahlreichen geodätischen Disziplinen Vorteile bietet (z.B. Photogrammetrie, Navigation, Geoinformationswissenschaften). Im Ausblick werden zukünftige Forschungsfragen angesprochen, wie die umfassendere Beschreibung der stochastischen Informationen von Schätzungen unter Ungleichungsrestriktionen und die analytische Beschreibung der Wahrscheinlichkeitsmasse am Rand des zulässigen Bereichs.

Der Abschnitt beginnt mit einer Übersicht über die umfangreiche Literatur zur konvexen Optimierung, mit Nennung von Standardwerken wie Gill et al. (1981), Fletcher (1987) und Boyd & Vandenberghe (2004). Ein wichtiger Spezialfall der konvexen Optimierung ist die quadratische Programmierung (QP), bei der eine quadratische Zielfunktion unter linearen Restriktionen minimiert wird. Die Arbeit erwähnt Simon & Simon (2003), die einen QP-Ansatz für einen ungleichheitsbeschränkten Kalman-Filter zur Triebwerkszustandsüberwachung entwickelten, und Wong (2011), der Active-Set-Methoden für QP in positiv (semi-)definiten und indefiniten Systemen untersuchte. Auch Ansätze zur Stabilisierung schlecht konditionierter LCP-Probleme (Koch, 1999) und die Umformulierung vieler einfacher Ungleichungsrestriktionen zu einer komplexen Gleichungsrestriktion im Kleinste-Quadrate-Kontext (Peng et al., 2006) werden kurz erwähnt. Die Anwendung von Ungleichungsrestriktionen in verschiedenen Kontexten wird beleuchtet: Koch (2006) zur semantischen Integration von 2D-Objekten und Geländemodellen, Kaschenz (2006) zur Analyse von Radio-Okkultationsdaten von GRACE (Gravity Recovery and Climate Experiment) mittels nicht-negativer Kleinste-Quadrate, und Tang et al. (2012) zur Verbesserung der GRACE-basierten Massenschätzungen in der Antarktis.

Ein zentraler Punkt ist die Qualitätsbeschreibung ungleichheitsbeschränkter Schätzungen, für die es vergleichsweise wenig Literatur gibt. Der am häufigsten zitierte Ansatz ist der frequentistische Ansatz von Liew (1976), der zuerst die aktiven Restriktionen identifiziert und das Problem dann durch ein Problem mit Gleichheitsrestriktionen approximiert. Geweke (1986) hingegen schlug einen Bayes'schen Ansatz vor, der von Zhu et al. (2005) in die Geodäsie eingeführt wurde. Die Arbeit hebt die Schwierigkeit hervor, die Genauigkeit von Schätzungen unter Ungleichungsrestriktionen zu quantifizieren, da die Parameter nicht mehr analytisch mit den Beobachtungen verknüpft sind und iterative Löser (Active-Set oder Interior-Point-Methoden) verwendet werden müssen. Die klassische Fehlerfortpflanzung ist nicht mehr anwendbar, und die Vorstellung einer symmetrischen Standardabweichung ist unzureichend, da die Ungleichungsrestriktionen die Symmetrie zerstören können. Konfidenzregionen bieten eine geeignetere Möglichkeit, die Genauigkeit in beschnittenen Parameterräumen zu beschreiben, wobei die Wahrscheinlichkeitsdichtefunktion (PDF) der Schätzungen benötigt wird. Die Arbeit wählt aufgrund der Schwierigkeiten bei der analytischen Bestimmung der PDF einen Monte-Carlo-Ansatz.

Der Abschnitt beschreibt verschiedene existierende Methoden zur Lösung von Optimierungsproblemen mit Ungleichungsrestriktionen. Es wird erwähnt, dass im Gegensatz zu Problemen ohne oder mit Gleichheitsrestriktionen bei Ungleichungsrestriktionen nicht im Voraus feststeht, welche Restriktionen aktiv sein werden. Dies führt zur Notwendigkeit iterativer Lösungsverfahren. Die Arbeit fokussiert sich auf Active-Set-Methoden, deren grundlegende Idee darin besteht, iterativ den Rand des zulässigen Bereichs im Parameterraum zu verfolgen, bis die optimale Lösung erreicht ist. Dies geschieht durch die Identifizierung der aktiven Restriktionen, die im aktuellen Iterationsschritt als Gleichheitsrestriktionen behandelt werden, und die Lösung einer Folge von Problemen mit Gleichheitsrestriktionen (Wong, 2011). Es wird darauf hingewiesen, dass das Vorzeichen der Lagrange-Multiplikatoren eine wichtige Rolle bei der Bestimmung der zu deaktivierenden Restriktionen spielt. Negative Lagrange-Multiplikatoren korrespondieren mit Ungleichungsrestriktionen, die deaktiviert werden können, um die Zielfunktion weiter zu minimieren. Gleichheitsrestriktionen bleiben stets aktiv. Alternativ zu den Active-Set-Methoden können auch Standardlöser für lineare Programme (LP), quadratische Programme (QP) oder lineare Komplementaritätsprobleme (LCP) verwendet werden, die allerdings in der Regel langsamer konvergieren.

Ein Kernproblem der Arbeit ist die Qualitätsbeschreibung von Schätzungen im Kontext der ungleichheitsbeschränkten Kleinste-Quadrate-Methode (ICLS). Im Gegensatz zu gewöhnlichen (OLS) oder gleichheitsbeschränkten (ECLS) Kleinste-Quadrate-Anpassungen, wo die Genauigkeit der Schätzung analytisch über die Kovarianzmatrix der Beobachtungen auf die Parameter fortgepflanzt werden kann, ist dies bei ICLS nicht möglich. Die Parameter sind nicht mehr analytisch mit den Beobachtungen verknüpft, und iterative Lösungsverfahren wie Active-Set-Methoden oder Interior-Point-Methoden werden eingesetzt. Die übliche Fehlerfortpflanzung (Koch, 1999) ist nicht mehr anwendbar. Die einfache Vorstellung einer symmetrischen Standardabweichung als Maß der Genauigkeit ist unzureichend, da der durch die Ungleichungsrestriktionen beschnittene Parameterraum die Symmetrie zerstört. Trotzdem ist ein Maß für die Genauigkeit unerlässlich. Die Arbeit argumentiert, dass Konfidenzregionen besser geeignet sind als Standardabweichungen, da sie an die beschnittenen Parameterräume angepasst werden können. Die Konstruktion von Konfidenzregionen erfordert die Kenntnis der Wahrscheinlichkeitsdichtefunktion (PDF) der Schätzungen. Die analytische Bestimmung der PDF ist jedoch komplex und rechenintensiv, besonders im multivariaten Fall. Daher wird ein Monte-Carlo-Ansatz vorgeschlagen.

Die Arbeit schlägt einen frequentistischen Monte-Carlo-Ansatz zur Qualitätsbeschreibung von ICLS-Schätzungen vor. Dieser Ansatz umgeht die komplexen analytischen Berechnungen und eignet sich gut für Parallelisierung. Die Methode basiert darauf, die angepassten Beobachtungen als Realisierung eines Zufallsvektors zu interpretieren und mittels Monte-Carlo-Simulationen die Wahrscheinlichkeitsdichtefunktion (PDF) der Schätzungen zu approximieren. Für korrelierte Daten wird die Cholesky-Zerlegung der Kovarianzmatrix der Beobachtungen verwendet (Alkhatib & Schuh, 2007). Die Arbeit diskutiert die Herausforderungen bei der numerischen Auswertung der PDF im multivariaten Fall und kritisiert das einfache Skalieren der Wahrscheinlichkeitsmasse außerhalb des zulässigen Bereichs. Als Alternative wird vorgeschlagen, die Wahrscheinlichkeitsmasse nur so weit zu verschieben, wie nötig, um die Restriktionen zu erfüllen. Die Arbeit beschreibt, wie Konfidenzregionen aus der approximierten PDF bestimmt werden können, indem die Histogrammbins nach Wert sortiert und die kumulative Summe bis zu einem bestimmten Perzentil berechnet wird. Die Methode wird für eindimensionale und höherdimensionale Probleme erläutert und auf die Asymmetrie der Konfidenzregionen im Vergleich zu OLS-Schätzungen hingewiesen (Roese-Koerner et al., 2015).

Die Arbeit thematisiert die Herausforderungen bei der Lösung von Optimierungsproblemen mit Ungleichungsrestriktionen im Kontext rangdefizierter Systeme. Im unbeschränkten Fall kann die allgemeine Lösung eines rangdefizienten Normalgleichungssystems mithilfe der Theorie verallgemeinerter Inverser effizient berechnet werden (Koch, 1999), inklusive der Berechnung einer eindeutigen Lösung über die Moore-Penrose-Inverse. Die Anwesenheit von Ungleichungsrestriktionen verändert dies grundlegend. Moderne Optimierungsalgorithmen wie Active-Set-Methoden (Gill et al., 1981; Wong, 2011) oder Interior-Point-Methoden (Boyd & Vandenberghe, 2004) sind oft nicht für rangdefiziente Zielfunktionen geeignet oder liefern lediglich eine von unendlich vielen möglichen partikulären Lösungen. Die existierende Literatur zu singulären Optimierungsproblemen mit Ungleichungsrestriktionen ist begrenzt (wenige Publikationen, siehe Abschnitt 5.1). In der Geodäsie treten solche Probleme jedoch häufig auf, beispielsweise beim Entwurf geodätischer Netze zweiter Ordnung, bei datumfreien Netzen oder bei Spline-Approximationen mit Datenlücken und zusätzlichen Informationen zum Funktionsverhalten. Die Arbeit fokussiert sich deshalb auf die Entwicklung von Methoden, um auch in diesen Fällen eine robuste und sinnvolle Lösung zu finden.

Um die Herausforderungen bei rangdefizienten Systemen mit Ungleichungsrestriktionen zu bewältigen, schlägt die Arbeit einen zweistufigen Ansatz vor. Dieser Ansatz orientiert sich an der Vorgehensweise von Werner und Yapar (1996). Im ersten Schritt werden die Restriktionen vernachlässigt und eine allgemeine Lösung des unbeschränkten Problems berechnet. Im zweiten Schritt werden die Ungleichungsrestriktionen berücksichtigt, und ein weiteres Optimierungsproblem wird gelöst, abhängig davon, ob ein Schnittpunkt zwischen der Lösungsmannigfaltigkeit und dem zulässigen Bereich existiert. Um die Gleichungen übersichtlich zu halten, konzentriert sich die Arbeit zunächst auf Probleme mit ausschließlich Ungleichungsrestriktionen. Mögliche Gleichheitsrestriktionen müssen vorher entfernt werden (Boyd & Vandenberghe, 2004). Der vorgeschlagene Ansatz hat vier Hauptvorteile: Beschreibung der Mannigfaltigkeit inklusive der Restriktionen, zusätzliche Nullraumoptimierung für eine partikuläre Lösung mit gewünschten Eigenschaften (z.B. Sparsität), Skalierbarkeit für größere Probleme und Erkennung von Dimensionsreduktionen der Lösungsmannigfaltigkeit durch die Ungleichungsrestriktionen.

Die Arbeit befasst sich mit der Erweiterung des Gauss-Helmert-Modells (GHM) auf den Fall von Ungleichungsrestriktionen, dem Inequality Constrained Gauss-Helmert Model (ICGHM). Es wird eine direkte Umformulierung des ICGHM als quadratisches Programm in Standardform gezeigt. Allerdings wird festgestellt, dass dies einen hohen Rechenaufwand verursacht. Daher wird eine maßgeschneiderte Umformulierung vorgeschlagen, die die spezielle Struktur des GHM ausnutzt. Diese Umformulierung macht die Verwendung von Standard-QP-Lösern unmöglich. Deshalb werden die KKT-Optimalitätsbedingungen für das modifizierte Problem hergeleitet und die Binding-Direction Primal Active-Set-Methode an diese Struktur angepasst. Die Arbeit betont, dass die Berücksichtigung von Rangdefiziten und Ungleichungsrestriktionen im GHM die Formulierung deutlich komplexerer, aber auch realitätsnäherer Modelle erlaubt, als dies bisher der Fall war. Es werden verschiedene Anwendungsszenarien in der Geodäsie und verwandten Gebieten erwähnt, wo solche Modelle von Vorteil sind (z.B. Design geodätischer Netze, datumfreie Netze, Spline-Approximation).

Der Abschnitt präsentiert den Huber-Schätzer als Beispiel für robuste Schätzung unter Ungleichungsrestriktionen. Der Huber-Schätzer wird als quadratisches Programm in Standardform reformuliert. Ein reales Datenbeispiel aus der robusten Statistik (Rousseeuw & Leroy, 2003) wird verwendet: die Anzahl internationaler Telefonate aus Belgien über die Jahre. Die Daten zeigen Ausreißer, die mit dem Huber-Schätzer unter Berücksichtigung von Ungleichungsrestriktionen behandelt werden. Die Analyse beinhaltet die Betrachtung der Lagrange-Multiplikatoren, um den Einfluss der Restriktionen auf die Schätzung zu untersuchen. Die größten Lagrange-Multiplikatoren korrespondieren mit den größten Änderungen der geschätzten Parameter. Es wird gezeigt, dass trotz einer 100%igen Wahrscheinlichkeitsmasse im unzulässigen Bereich der Wald-Test die Gültigkeit der Restriktionen unterstützt.

Ein weiteres Anwendungsbeispiel ist die Very Long Baseline Interferometry (VLBI)-Ausgleichung mit Restriktionen für die troposphärische Verzögerung. Dieses Beispiel wurde bereits in einer Publikation (Halsig et al., 2015) vorgestellt. Die genaue Modellierung des Signalwegs durch die Atmosphäre ist für Raumgeodätische Techniken wie VLBI und GNSS entscheidend. Die troposphärische Verzögerung, insbesondere die feuchte Komponente (Zenith Wet Delay, ZWD), stellt eine wichtige Fehlerquelle dar. Die Arbeit zeigt, wie Ungleichungsrestriktionen verwendet werden können, um die Schätzung des ZWD zu verbessern. Die Arbeit verweist auf die Publikation von Halsig et al. (2015), „Improved Parameter Estimation of Zenith Wet Delay Using an Inequality Constrained Least Squares Method“, und bietet lediglich eine kurze Zusammenfassung des Beispiels.

Die Arbeit präsentiert weitere Anwendungsbeispiele, um die Vielseitigkeit der entwickelten Methodik zu demonstrieren. Dies umfasst das Design geodätischer Netze zweiter Ordnung (führend zu rangdefizienten Systemen), wobei die Schätzung individueller Gewichte als erster Schritt eines dreistufigen Prozesses beschrieben wird (Müller, 1985). Ein weiteres Beispiel aus dem Engineering befasst sich mit strengen Schweißtoleranzen bei der Konstruktion eines Bauteils. Hier werden Ungleichungsrestriktionen verwendet, um die zulässigen Abmessungen des Bauteils zu modellieren. Die Analyse der Lagrange-Multiplikatoren ermöglicht die Erkennung inkompatibler Elemente. Auch das Design von Straßen wird als Anwendung des Gauss-Helmert-Modells mit Ungleichungsrestriktionen (ICGHM) vorgestellt. Dabei werden Ungleichungsrestriktionen verwendet, um zulässige Steigungen und Radien von Kurven zu definieren (RAL, 2012). Die Arbeit verweist auf Koch (1976) für das horizontale und auf RAL (2012) für das vertikale Straßendesign und berücksichtigt auch die Arbeit von Vitkiene und Puodziukas (2014) zum Einfluss von Umweltfaktoren auf das Straßendesign. Diese Beispiele unterstreichen die breite Anwendbarkeit der entwickelten Methoden in verschiedenen geodätischen Disziplinen und verwandten Bereichen.