數值求解非線性方程

Question

我需要解決Java程序中的非線性最小化（N個未知數的最小殘差平方）問題。解決這些問題的常用方法是Levenberg-Marquardt算法。我有幾個問題

• 有沒有人有不同的LM實現可用的經驗？ LM存在稍微不同的風味，我聽說算法的確切實現對其數值穩定性有重大影響。我的功能非常好，所以這可能不會成爲問題，但我當然想選擇一個更好的替代方案。以下是我找到的一些替代方案：

  • FPL Statistics Group's Nonlinear Optimization Java Package。這包括經典Fortran MINPACK例程的Java翻譯。

  • JLAPACK，另一個Fortran翻譯。

  • Optimization Algorithm Toolkit。

  • Javanumerics。

  • 一些Python實現。純Python會很好，因爲它可以通過jythonc編譯爲Java。

• 是否有任何常用啓發式方法來做LM需要的初始猜測？

• 在我的應用程序中，我需要對解決方案設置一些限制，但幸運的是它們很簡單：我只是要求解決方案（爲了成爲物理解決方案）是非負的。稍微負面的解決方案是數據測量不準確的結果，顯然應該爲零。我正在考慮使用「常規」LM，但是迭代，以便如果某些未知變成負數，我將它設置爲零，並從中解決其餘部分。真正的數學家可能會嘲笑我，但你認爲這可能有用嗎？

感謝您的意見！這不是火箭科學，需要解決的參數數（N）最多爲5，而且數據集勉強夠大以至於不能解決問題，所以我相信Java非常高效，足以解決這個問題。這個。我相信這個問題已經被聰明的應用數學家解決了很多次，所以我只是尋找一些現成的解決方案，而不是自己做。例如。 Scipy.optimize.minpack.leastsq可能會很好，如果它是純Python的話。

Answer 1

我實際上沒有使用過任何這些Java庫，所以請帶上一點鹽：基於後端，我可能會看首先在JLAPACK。我相信LAPACK是Numpy的後端，它本質上是在Python中進行線性代數/數學操作的標準。至少，您絕對應該使用經過良好優化的C或Fortran庫而不是純Java，因爲對於大型數據集，這些類型的任務可能會非常耗時。

對於創建初始猜測，它實際上取決於您嘗試適合什麼樣的函數（以及您擁有哪種類型的數據）。基本上，只要尋找一些相對較快（可能是O（N）或更好）的計算，就可以給出所需參數的近似值。（我最近在Numpy中做了一個高斯分佈，我估計的平均值只是average(values, weights = counts) - 也就是直方圖中的計數的加權平均值，這是數據集的真實平均值，它不是確切的中心我期待的峯值，但它已經足夠接近了，算法就走了。）

至於保持約束正面，你的方法似乎是合理的。既然你正在編寫一個程序來完成這項工作，也許只需要製作一個布爾標誌，讓你輕鬆地啓用或禁用「強制非負面」行爲，並通過兩種方式進行比較。只有當你得到很大的差異（或者如果算法的一個版本需要不合理的長時間），它可能是值得擔心的。 （REAL數學家會從頭開始分析最小二乘法的最小化; -P所以我認爲你是那個可以嘲笑他們的人....也許吧）

Answer 2

你最初的猜測越接近解決方案，你會收斂得越快。

你說這是一個非線性問題。你可以做一個線性化的最小二乘解。也許你可以使用該解決方案作爲第一個猜測。一些非線性迭代會告訴你一些假設的好壞。

另一個想法是嘗試另一種優化算法。如果可以在許多CPU上運行它們，遺傳和蟻羣算法可能是一個不錯的選擇。他們也不需要連續的衍生工具，所以如果你有不連續的，不連續的數據，他們會很好。

Answer 3

如果問題有限制，則不應使用無約束求解器。對於 實例，如果知道您的某些變量必須是非負的，則應該將 告知解算器。

如果您樂於使用Scipy，我會推薦scipy.optimize.fmin_l_bfgs_b 您可以使用L-BFGS-B在變量上放置簡單的界限。請注意，L-BFGS-B採用一般的非線性目標函數，而不僅僅是一個非線性最小二乘問題。

Answer 4

FPL軟件包相當可靠，但由於其對Fortran代碼的字面解釋，有一些怪癖（數組訪問從1開始）。如果你的功能表現良好，LM方法本身就相當可靠。強制非負約束的一個簡單方法是直接使用參數的平方而不是參數。這可能會引入虛假解決方案，但對於簡單的型號，這些解決方案很容易篩選出來。

有一種可用於「約束」LM方法的代碼。在這裏看看http://www.physics.wisc.edu/~craigm/idl/fitting.html爲mpfit。有一個python（不幸的是依賴於Numeric）和一個C版本。 LM方法大約有1500行代碼，因此您可能傾向於將C移植到Java。事實上，「約束」LM方法與您所設想的方法沒有多大區別。在mpfit中，代碼調整相對於變量邊界的步長。我用mpfit也有很好的效果。

我對BFGS沒有太多的經驗，但代碼更加複雜，我從來沒有清楚過授權代碼。

祝你好運。

Answer 5

我同意codehippo;我認爲解決約束問題的最好方法是使用專門設計來處理它們的算法。在這種情況下，L-BFGS-B算法應該是一個很好的解決方案。

但是，如果使用python的scipy.optimize。在你的情況下fmin_l_bfgs_b模塊不是一個可行的選擇（因爲你使用的是Java），你可以嘗試使用我編寫的庫：用於L-BFGS-B算法原始Fortran代碼的Java包裝器。您可以從http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper下載並查看它是否符合您的需求。