Nichtlineare kleinste Quadrate mit Box-Einschränkungen

10

Was sind empfohlene Methoden, um nichtlineare kleinste Quadrate, min , mit Box-Einschränkungen ? Es scheint mir (Dummköpfe eilen ), dass man die Box-Einschränkungen quadratisch machen und wobei ist die "Wannenfunktion" in Form von \ _ _ _ /, . Funktioniert das theoretisch, in der Praxis? (Es scheint viele theoretische Arbeiten zu NLS + zu geben, aber mein Interesse ist praktisch - echte oder realistische Testfälle würden mir helfen, zwischen Methoden zu wählen.) $\sum err_i(p)^2$ $lo_j <= p_j <= hi_j$

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$

t u b (x, l o, h i)

$tub( x, lo, hi )$

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$

(Experten, bitte Tags hinzufügen: "kleinste Quadrate"?)

optimization constraints denis
quelle

5

Das Ersetzen strenger Einschränkungen durch Straffunktionen ist eine übliche Technik bei der numerischen Optimierung. Es scheint, dass das, was Sie vorschlagen, eine bestimmte Form dieses Ersatzes ist. Sie können alles über ähnliche Techniken lesen, z. B. hier: stanford.edu/~boyd/cvxbook

David Ketcheson

Sie können eine geeignete Parametrisierung von , um die Box-Einschränkungen zu erfüllen (z. B. . In Bezug auf NLS-Löser ist Levenberg-Marquardt die meiste Zeit gut genug Einige kommerzielle Toolboxen scheinen auch Vertrauensbereichsmethoden anzubieten, die auf adaptiven Antwortoberflächenmodellen basieren, was für mich nach einer vernünftigen Verallgemeinerung von Levenberg-Marquardt aussieht.

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

Thomas Klimpel

11

Das Hinzufügen von quadratischen Strafbegriffen, um Einschränkungen zu beseitigen, ist ein einfacher Ansatz, der nur eine Genauigkeit von Ordnung 1 / Straffaktor ergibt. Daher wird es für eine hohe Genauigkeit nicht empfohlen, es sei denn, Sie lassen die Strafe während der Berechnung auf unendlich gehen. Ein hoher Straffaktor macht den Hessischen jedoch sehr schlecht konditioniert, was die erreichbare Gesamtgenauigkeit einschränkt, ohne die Einschränkungen explizit zu berücksichtigen.

Beachten Sie, dass gebundene Einschränkungen viel einfacher zu handhaben sind als allgemeine Einschränkungen, weshalb sie praktisch nie in Strafen umgewandelt werden.

Der Löser L-BFGS-B (verwendet mit einer ungefähr 5-dimensionalen Historie) löst gebundene eingeschränkte Probleme normalerweise sehr zuverlässig und schnell in beiden niedrigen hohen Dimensionen. Ausnahmen sind Missverständnisse bei Problemen, die weit entfernt von den Lösungen sehr flach werden können, wo es leicht ist, bei einer Abstiegsmethode hängen zu bleiben.

Wir haben viele Experimente mit sehr unterschiedlichen Funktionen in vielen verschiedenen Dimensionen durchgeführt, wobei viele verschiedene Löser zur Verfügung standen, da wir als Teil unserer globalen Optimierungssoftware einen sehr robusten Löser mit gebundenen Einschränkungen benötigten. L-BFGS-B ist eindeutig eine Allzweckmethode, obwohl andere Löser bei einigen Problemen natürlich eine deutlich bessere Leistung erbringen. Daher würde ich L-BFGS-B als erste Wahl empfehlen und alternative Techniken ausprobieren, nur für den Fall, dass L-BFGS-B Ihre spezielle Klasse von Problemen schlecht behandelt.

Arnold Neumaier
quelle

L-BFGS ist in IPOPT verfügbar, ich habe meine Antwort überarbeitet.

Ali

5

Ich würde einfach den universellen NLP-Löser IPOPT verwenden . Es ist der robusteste Löser unter denen, die ich versucht habe.

Sofern Sie keine besonderen Anforderungen haben, gibt es keinen Grund, warum Sie auf einem problemspezifischen Löser bestehen sollten, der nur für NLS mit Box-Einschränkungen funktioniert.

Eine Änderung der Anforderungen (z. B. das Hinzufügen nichtlinearer Einschränkungen) würde bei einem problemspezifischen Löser zu starken Kopfschmerzen führen. Sie werden keine derartigen Probleme haben, wenn Sie das Allzweck-IPOPT verwenden.

UPDATE: Sie können L-BFGS mit IPOPT ausprobieren , siehe unter Quasi-Newton in der Dokumentation.

Das Lösungsverfahren kann schneller werden, wenn die bemerkenswerte Robustheit von IPOPT beeinträchtigt wird. Verwenden Sie meiner Meinung nach die genauen Derivate, wenn sie verfügbar sind. Ich würde nur dann mit Annäherungen (wie L-BFGS) herumspielen, wenn ich nachgewiesene Leistungsprobleme hätte.

Ali
quelle

Ich weiß nicht, wie gut IPOPT funktioniert, aber Ihr Vorschlag erinnert mich an ähnliche Aussagen von Befürwortern der Downhill-Simplex-Methode. Da nichtlineare kleinste Quadrate eine häufige Problemklasse sind, erscheint mir die völlige Ablehnung mit einem der vorhandenen NLS-Löser etwas verdächtig.

Thomas Klimpel

@ThomasKlimpel Nun, Denis sollte uns mehr Details geben, dann könnten wir ihm bei der Auswahl des richtigen Lösers helfen. :) Oder er kann es selbst überprüfen und herausfinden, welches seinen Bedürfnissen am besten entspricht. IPOPT scheint zunächst ein guter Löser zu sein.

Ali

@Ali, kannst du bitte auf einige "echte oder realistische Testfälle" verweisen?

Denis

@denis Ich könnte, aber ich habe nicht die Absicht, es würde dich von der Strecke werfen. Das einzige, was zählt, ist, wie IPOPT Ihr Problem behandelt . Sofern Sie keine besonderen Anforderungen haben, sollte es diese gut lösen. IPOPT verfügt über Schnittstellen zu MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Wählen Sie eine Schnittstelle und testen Sie, was mit Ihrem Problem passiert :) Das Testen eines problemspezifischen Lösers wäre ebenfalls nicht einfacher.

Ali

@ Thomas Klimpel, ich glaube, ich war nicht klar: Ich lehne nicht ab, frage nicht nach Paketen, sondern frage nach Einsichten oder Testfällen: Warum könnte diese triviale Methode nicht gut funktionieren?

Denis

1

Das CRAN-Paket R minpack.lm bietet eine Levenberg-Marquardt-Implementierung mit Box-Einschränkungen.

Im Allgemeinen ist Levenberg-Marquardt für Probleme mit kleinsten Quadraten viel besser geeignet als L-BFGS-B. Es wird (viel) besser bei herausfordernden Problemen konvergieren. Es wird auch viel schneller sein als das Allzweck-IPOPT, da es auf nichtlineare Probleme der kleinsten Quadrate zugeschnitten ist.

Das R-Paket wählt einen sehr einfachen Projektionsansatz, um die Einschränkungen durchzusetzen (siehe Quellcode ). Abhängig von der von Ihnen verwendeten LM-Implementierung kann die Einbindung einfach sein.

Der Vorschlag in den Kommentaren zur Verwendung einer Transformation (z. B. eine Sinustransformation wie in scipy) ist nun auch eine gute, einfache Alternative, um Ihren nicht eingeschränkten LM-Algorithmus in einen eingeschränkten zu transformieren. Sie müssen die Transformation auch in den Jacobian aufnehmen, wenn der Jacobian analytisch ist.

Jherek
quelle

0

(Jahre später) zwei Löser, die Box-Einschränkungen behandeln:

Scipy least_squares verfügt über 3 Methoden mit umfangreichem Dokument:
1. 'trf': Trust Region Reflective
2. "Hundebox"
3. 'lm': ein Legacy-Wrapper für MINPACK ohne Box-Einschränkungen.
ceres

denis
quelle

1

Der Scipy sagt ausdrücklich, dass der Levenberg-Marquardt-Algorithmus keine Box-Einschränkungen verarbeiten kann.

Tholy

Nichtlineare kleinste Quadrate mit Box-Einschränkungen

Antworten: