„WORHP“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[ungesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
K Bot: Kategorien in BNR-Unterseite ausgeblendet)
Dwassel (Diskussion | Beiträge)
5 Bearbeitungen
Kleine Umformulierungen, 1 Link eingefügt + 1 überarbeitet
Zeile 17: Zeile 17:
}}
}}


„WORHP“, ausgesprochen wie das englische Wort „warp“, bei der [[ESA|ESA]] auch bekannt als „eNLP“ ([[Nonlinear programming|NLP]] solver), ist ein mathematisches Programm bzw. eine [[Programmbibliothek|Bibliothek]] zur numerischen Lösung stetiger hochdimensionaler [[Optimierung_(Mathematik)#Nichtlineare_Optimierung|nichtlinearer Optimierungsprobleme]]. Die Abkürzung WORHP bedeutet ausgeschrieben "'''W'''e '''O'''ptimize '''R'''eally '''H'''uge '''P'''roblems", dies stellt das primäre Anwendungsgebiet der Software dar. WORHP ist hybrid in den Sprachen [[Fortran]] und [[C_(Programmiersprache)‎|C]] implementiert und bietet zusätzlich die Möglichkeit über verschiedene Schnittstellen in C/[[C++]]- und Fortran-Programmen integriert zu werden. Zusätzlich existieren Schnittstellen zur Einbindung in die Modellierungsumgebungen [[MATLAB]], CasADi und [[AMPL]]. <ref name="Interfaces">
„WORHP“, ausgesprochen wie das englische Wort „warp“, bei der [[ESA|ESA]] auch bekannt als „eNLP“ ([[Nonlinear programming|NLP]] solver), ist ein mathematisches Programm bzw. eine [[Programmbibliothek|Bibliothek]] zur numerischen Lösung stetiger hochdimensionaler [[Optimierung_(Mathematik)#Nichtlineare_Optimierung|nichtlinearer Optimierungsprobleme]]. Die Abkürzung WORHP bedeutet ausgeschrieben "'''W'''e '''O'''ptimize '''R'''eally '''H'''uge '''P'''roblems", dies stellt das primäre Anwendungsgebiet der Software dar. WORHP ist hybrid in den Sprachen [[Fortran]] und [[C_(Programmiersprache)‎|C]] implementiert und bietet zusätzlich die Möglichkeit über verschiedene Schnittstellen in C/[[C++]]- und Fortran-Programmen integriert zu werden. Zusätzlich existieren Schnittstellen zur Einbindung in die Modellierungsumgebungen [[MATLAB]], CasADi und [[AMPL]].<ref name="Interfaces">
{{cite web |url=http://worhp.de/content/interfaces |title=WORHP interfaces |accessdate=2013-05-27}}
{{cite web |url=http://worhp.de/content/interfaces |title=WORHP interfaces |accessdate=2013-05-27}}
</ref>
</ref>


== Formulerung des Problems ==
== Formulierung des Problems ==
WORHP wurde entwickelt um Probleme der Form
WORHP wurde entwickelt um Probleme der Form
::: <math>\min_{x \in \R^n} f(x)</math>
::: <math>\min_{x \in \R^n} f(x)</math>
:unter
:unter
::: <math>L \leq \begin{pmatrix} x \\ g(x) \end{pmatrix} \leq U </math>
::: <math>L \leq \begin{pmatrix} x \\ g(x) \end{pmatrix} \leq U </math>
mit hinreichend glatten Funktionen <math>f:\R^n \to \R</math> (Zielfunktion) und <math>g:\R^n \to \R^m</math> (Nebenbedingungen) welche nichtlinear sein dürfen, und nicht notwendig konvex sein müssen, zu lösen. Sogar Probleme mit sehr großen Dimensionen <math>n</math> und <math>m</math> können effizient gelöst werden, wenn das Problem hinreichend dünnbesetzt ist.
mit hinreichend glatten Funktionen <math>f:\R^n \to \R</math> (Zielfunktion) und <math>g:\R^n \to \R^m</math> (Nebenbedingungen) zu lösen, welche nichtlinear sein dürfen, und nicht notwendig konvex sein müssen. Sogar Probleme mit sehr großen Dimensionen <math>n</math> und <math>m</math> können effizient gelöst werden, wenn das Problem hinreichend dünnbesetzt ist; die höchsten bisher erreichten Dimensionen liegen in der Größenordnung <math>10^9</math>.
Problemstellungen in denen es nicht möglich ist Zielfunktion und Nebenbedingungen separat oder in denen es möglich ist die Nebenbedingungen elementweise auszuwerten, können von WORHP ausgenutzt werden um die Berechnung effizient zu gestalten.
Problemstellungen in denen es nicht möglich ist, Zielfunktion und Nebenbedingungen separat auszuwerten, oder in denen es möglich ist, die Nebenbedingungen elementweise auszuwerten, können von WORHP ausgenutzt werden um die Berechnung effizient zu gestalten.


=== Ableitungen ===
=== Ableitungen ===
WORHP benötigt die erste Ableitung ([[Gradient]]) von <math>f</math> und von <math>g</math> ([[Jacobi-Matrix]]) und die zweite Ableitung ([[Hesse-Matrix]]) der [[Lagrange-Multiplikator|Lagrange-Funktion]]; in einer Modellierungsumgebung wie AMPL können diese durch [[Automatisches_Differenzieren|automatische Differentiation]] zur Verfügung gestellt werden, aber in anderen Anwendungen müssen diese durch den Benutzer übergeben werden. Erste und zweite Ableitungen können durch WORHP mit Hilfe von finiten Differenzen ermittelt werden. Um die typischerweise dadurch enstehende sehr hohe Anzahl an Funkionsauswertungen in hochdimensionalen dünnbesetzten Anwendungen zu vermeiden, wird die [[Färbung_(Graphentheorie)|Graphenfärbungstheorie]] ausgenutzt um erste und zweite Ableitungen zu gruppieren. Zweite Ableitungen können außerdem durch Variationen der klassischen [[Quasi-Newton-Verfahren|BFGS]] Verfahren, inklusive block-diagonaler und dünnbesetzter Variante, approximiert werden.
WORHP benötigt die erste Ableitung ([[Gradient]]) von <math>f</math> und von <math>g</math> ([[Jacobi-Matrix]]) und die zweite Ableitung ([[Hesse-Matrix]]) der [[Lagrange-Multiplikator|Lagrange-Funktion]]; in einer Modellierungsumgebung wie AMPL können diese durch [[Automatisches_Differenzieren|automatische Differentiation]] zur Verfügung gestellt werden, aber in anderen Anwendungen müssen diese durch den Benutzer übergeben werden. Erste und zweite Ableitungen können durch WORHP mit Hilfe von finiten Differenzen ermittelt werden. Um die typischerweise dadurch enstehende sehr hohe Anzahl an Funkionsauswertungen in hochdimensionalen dünnbesetzten Anwendungen zu vermeiden, wird die [[Färbung_(Graphentheorie)|Graphenfärbungstheorie]] ausgenutzt um erste und zweite Ableitungen zu gruppieren. Zweite Ableitungen können außerdem durch Variationen der klassischen [[Quasi-Newton-Verfahren|BFGS]] Verfahren, inklusive block-diagonaler und dünnbesetzter Variante, approximiert werden. WORHP implementiert als erstes NLP Verfahren ein strukturerhaltendes (ggf. also dünnbesetztes) '''S'''BFGS-Verfahren, für das ein Konvergenzbeweis existiert.<ref name="SBFGS">{{Literatur | Autor=Patrik Kalmbach | Verlag=Universität Bremen | Titel=Effiziente Ableitungsbestimmung bei hochdimensionaler nichtlinearer Optimierung | Ort=Bremen | Jahr=2011 | Monat=Juni | Tag=23 |Online=[http://nbn-resolving.de/urn:nbn:de:gbv:46-00102087-10 Online bei der Staats- und Unversitätsbibliothek Bremen; PDF-Datei; 2,2 MB] |Zugriff=2013-06-07 | Typ=Dissertation}}</ref>


== Struktur ==
== Struktur ==
Zeile 41: Zeile 41:
{{cite web |url=http://uma.ensta.fr/itn-sadco/?module=conf_aero&action=programme |title=eNLP: application-centric NLP-based optimization in the aerospace market |location=ITN Sadco First Industrial Workshop |author=Sven Erb |date=2011-03-02}}
{{cite web |url=http://uma.ensta.fr/itn-sadco/?module=conf_aero&action=programme |title=eNLP: application-centric NLP-based optimization in the aerospace market |location=ITN Sadco First Industrial Workshop |author=Sven Erb |date=2011-03-02}}
</ref> (Die Benutzung von Ipfilter in WORHP wurde nach 2010 nicht weiter verfolgt.)
</ref> (Die Benutzung von Ipfilter in WORHP wurde nach 2010 nicht weiter verfolgt.)
Das [http://www.stw.de/su/1118 Steinbeis-Forschungszentrum Optimierung, Steuerung und Regelung] und Wissenschaftler der Arbeitsgruppe [http://www.math.uni-bremen.de/zetem/o2c/de Optimierung und Optimale Steuerung] an der [[Universität_Bremen|Universität Bremen]] und der [[Universität_der_Bundeswehr_München|Universtität der Bundeswehr München]] arbeiten an der weiteren Entwicklung von WORHP.<ref name="Entwicklerteam">
Das [http://www.stw.de/su/1118 Steinbeis-Forschungszentrum Optimierung, Steuerung und Regelung] und Wissenschaftler der Arbeitsgruppe [http://www.math.uni-bremen.de/zetem/o2c/de Optimierung und Optimale Steuerung] an der [[Universität_Bremen|Universität Bremen]] und der [[Universität_der_Bundeswehr_München|Universtität der Bundeswehr München]] arbeiten an der weiteren Entwicklung von WORHP.<ref name="Entwicklerteam">{{cite web |url=http://worhp.de/content/team-worhp |title=Entwicklerteam |accessdate=2013-05-27}}</ref>
Die Entwickler von WORHP betonen, dass es trotz seines akademischen Ursprungs von Beginn an als industriell nutzbares Werkzeug entwickelt wurde, statt als reine Forschungsplattform.<ref name="The ESA NLP Solver WORHP">
{{cite web |url=http://worhp.de/content/team-worhp |title=Entwicklerteam |accessdate=2013-05-27}}
{{Literatur | Autor=Christof Büskens, Dennis Wassel |Verlag=Springer |Titel=The ESA NLP Solver WORHP |ISBN=978-1-4614-4469-5 |Herausgeber=Giorgio Fasano, János D. Pintér |Sammelwerk=Modeling and Optimization in Space Engineering |Reihe = Springer Optimization and Its Applications | Band = 73 | Jahr = 2013 | DOI = 10.1007/978-1-4614-4469-5_4 | Online = [http://link.springer.com/chapter/10.1007%2F978-1-4614-4469-5_4 Seite bei Springer online] | Zugriff = 2013-06-07}}</ref>
</ref> Die Entwickler verbessern WORHP zur Zeit verstärkt, so dass es im Gegensatz zu seinen akademischen Ursprüngen, als Werkzeug zur Anwendung in der Industrie dienen kann. <ref name="The ESA NLP Solver WORHP">
{{cite web |url=http://link.springer.com/chapter/10.1007%2F978-1-4614-4469-5_4 |author=Christof Büskens, Dennis Wassel |title=The ESA NLP Solver WORHP |accessdate=2013-05-27}}
</ref>


== Anwendungen ==
== Anwendungen ==

Version vom 7. Juni 2013, 11:23 Uhr


WORHP

Konsolenansicht von WORHP bei Lösung eines kleinen Beispielproblems
Identifikationsproblem Ausgangssituation
Identifikationsproblem optimale Lösung mit WORHP ermittelt
Basisdaten

Entwickler Christof Büskens, Matthias Gerdts et al.
Erscheinungsjahr 2010
Aktuelle Version 1.1
(07. Mai 2013)
Betriebssystem Unix, Windows XP (oder neuer)
Programmier­sprache ANSI C, FORTRAN 77, Fortran 95 and Fortran 2003
Kategorie Mathematik, Optimierung_(Mathematik)
Lizenz Proprietär, Kostenfrei für akademische Zwecke
deutschsprachig nein
worhp.de

„WORHP“, ausgesprochen wie das englische Wort „warp“, bei der ESA auch bekannt als „eNLP“ (NLP solver), ist ein mathematisches Programm bzw. eine Bibliothek zur numerischen Lösung stetiger hochdimensionaler nichtlinearer Optimierungsprobleme. Die Abkürzung WORHP bedeutet ausgeschrieben "We Optimize Really Huge Problems", dies stellt das primäre Anwendungsgebiet der Software dar. WORHP ist hybrid in den Sprachen Fortran und C implementiert und bietet zusätzlich die Möglichkeit über verschiedene Schnittstellen in C/C++- und Fortran-Programmen integriert zu werden. Zusätzlich existieren Schnittstellen zur Einbindung in die Modellierungsumgebungen MATLAB, CasADi und AMPL.[1]

Formulierung des Problems

WORHP wurde entwickelt um Probleme der Form

unter

mit hinreichend glatten Funktionen (Zielfunktion) und (Nebenbedingungen) zu lösen, welche nichtlinear sein dürfen, und nicht notwendig konvex sein müssen. Sogar Probleme mit sehr großen Dimensionen und können effizient gelöst werden, wenn das Problem hinreichend dünnbesetzt ist; die höchsten bisher erreichten Dimensionen liegen in der Größenordnung . Problemstellungen in denen es nicht möglich ist, Zielfunktion und Nebenbedingungen separat auszuwerten, oder in denen es möglich ist, die Nebenbedingungen elementweise auszuwerten, können von WORHP ausgenutzt werden um die Berechnung effizient zu gestalten.

Ableitungen

WORHP benötigt die erste Ableitung (Gradient) von und von (Jacobi-Matrix) und die zweite Ableitung (Hesse-Matrix) der Lagrange-Funktion; in einer Modellierungsumgebung wie AMPL können diese durch automatische Differentiation zur Verfügung gestellt werden, aber in anderen Anwendungen müssen diese durch den Benutzer übergeben werden. Erste und zweite Ableitungen können durch WORHP mit Hilfe von finiten Differenzen ermittelt werden. Um die typischerweise dadurch enstehende sehr hohe Anzahl an Funkionsauswertungen in hochdimensionalen dünnbesetzten Anwendungen zu vermeiden, wird die Graphenfärbungstheorie ausgenutzt um erste und zweite Ableitungen zu gruppieren. Zweite Ableitungen können außerdem durch Variationen der klassischen BFGS Verfahren, inklusive block-diagonaler und dünnbesetzter Variante, approximiert werden. WORHP implementiert als erstes NLP Verfahren ein strukturerhaltendes (ggf. also dünnbesetztes) SBFGS-Verfahren, für das ein Konvergenzbeweis existiert.[2]

Struktur

Auf NLP-Ebene basiert WORHP auf einem klassischen SQP-Algorithmus, wohingegen die quadratischen Teilprobleme mit Hilfe von Innere-Punkte-Verfahren gelöst werden. Dieser Aufbau wurde gewählt um von der Robustheit von SQP-Verfahren und dem zuverlässigen numerischen Aufwand von IP-Verfahren zu profitieren, da klassische Aktive-Mengen-Strategien bei hochdimensionalen Problemen ungeeignet sind.

Entwicklung

Die Entwicklung von WORHP startete in 2006 mit einer Finanzierung des deutschen Zentrums für Luft- und Raumfahrt und wurde unter dem Namen „eNLP“ nach 2008 mit Unterstützung der ESA / ESTEC zusammen mit dem Innere-Punkte-Löser ipfilter [3] fortgesetzt. Ziel war die Implementierung eines NLP-Lösers zur Bestimmung optimaler Trajektorien, zur Missionsanalyse und für Raumfahrtanwendungen im Allgemeinen.[4] (Die Benutzung von Ipfilter in WORHP wurde nach 2010 nicht weiter verfolgt.) Das Steinbeis-Forschungszentrum Optimierung, Steuerung und Regelung und Wissenschaftler der Arbeitsgruppe Optimierung und Optimale Steuerung an der Universität Bremen und der Universtität der Bundeswehr München arbeiten an der weiteren Entwicklung von WORHP.[5] Die Entwickler von WORHP betonen, dass es trotz seines akademischen Ursprungs von Beginn an als industriell nutzbares Werkzeug entwickelt wurde, statt als reine Forschungsplattform.[6]

Anwendungen

WORHP wurde in Programmen zur Analyse von Trajektorien wie LOTNAV [7] und ASTOS integriert, und wird am ESOC und am ESTEC genutzt. Es ist auch möglich WORHP als Optimierer in CasADi (seit Version 1.5.0 beta) [8] einzubinden und es wird als lokaler Optimierer im SVAGO MDO [9] Programm, entwickelt an der Universität Bremen und am Politecnico di Milano, zur multidisziplinären Optimierung im ESA PRESTIGE Programm genutzt. [10]

Einzelnachweise

  1. ↑ WORHP interfaces. Abgerufen am 27. Mai 2013.
  2. ↑ Patrik Kalmbach: Effiziente Ableitungsbestimmung bei hochdimensionaler nichtlinearer Optimierung. Universität Bremen, Bremen 23. Juni 2011 (Online bei der Staats- und Unversitätsbibliothek Bremen; PDF-Datei; 2,2 MB [abgerufen am 7. Juni 2013]).
  3. ↑ Luis Vicente, Renata Silva, Michael Ulbrich, Stefan Ulbrich: ipfilter — An NLP Solver based on a primal-dual interior-point filter algorithm. Abgerufen am 27. Mai 2013.
  4. ↑ Sven Erb: eNLP: application-centric NLP-based optimization in the aerospace market. 2. März 2011;.
  5. ↑ Entwicklerteam. Abgerufen am 27. Mai 2013.
  6. ↑ Christof Büskens, Dennis Wassel: The ESA NLP Solver WORHP. In: Giorgio Fasano, János D. Pintér (Hrsg.): Modeling and Optimization in Space Engineering (= Springer Optimization and Its Applications). Band 73. Springer, 2013, ISBN 978-1-4614-4469-5, doi:10.1007/978-1-4614-4469-5_4 (Seite bei Springer online [abgerufen am 7. Juni 2013]).
  7. ↑ J. L. Cano, M. Bello, J. Rodriguez-Canabal: Navigation and Guidance for Low-Thrust Trajectories, LOTNAV. 2004, abgerufen am 27. Mai 2013.
  8. ↑ CasADi wiki. Abgerufen am 27. Mai 2013.
  9. ↑ Francesco Castellini: PRESTIGE MDO research, Research Achievements. 2009, abgerufen am 23. März 2011.
  10. ↑ ESA education: Universities selected for PRESTIGE programme. 2009, abgerufen am 23. März 2011.

Externe Links


[[Kategorie:Numerische Software]] [[Kategorie:Linux-Software]] [[Kategorie:Windows-Software]]

Abgerufen von „https://de.wikipedia.org/w/index.php?title=WORHP&oldid=119297244“