在解最小二乘問題上，ceres還有哪些改進點（lm為例），或者說如何寫出超越ceres的優化器？

1樓：範帝楷

沒想到還有人關注這個問題。

本質上最小二乘法的求解公式是比較簡單的：

這個公式是有解析解的（normal equation）：

這其實沒啥好說的，多數時候直接LLT就求解了，但是求解這個方程實際上是有兩個問題的：

當的維度足夠大時，求解速度很慢

當的條件數很大時，的條件數將會更大(後者條件數是前者平方)，本身求解不穩定的問題會更不穩定

因此實際上在遇到這兩個問題時，才有是否有改進優化器一說(正常市面上的優化器都是使用normal equation的。

對於第二個問題，實際上對矩陣A進行QR分解，然後求解線性方程組，不會是的矩陣條件數變大。

但是對於第乙個問題，類似於ceres或者g2o這樣的求解器，其實是並未做太多設計的(雖然可以設定稀疏求解器，甚至可以設定pcg，但是總歸並未對這種情況進行設計)。

實際上求解大型稀疏線性方程組是乙個很複雜的問題，現在大多都使用平行計算的。這句話說起來簡單，但實際上不是那麼容易的，考慮線性方程組：

這個方程雖然很簡單，但實際上直接求解的時候是需要先算出乙個未知數，然後回代才能算出另乙個未知數的，這是乙個序列演算法，是無法直接使用顯示卡並行的。

並行演算法大多數都是迭代演算法，例如共軛梯度下降。但是，對於迭代演算法如果條件數很大，迭代收斂其實是很不容易的，你需要設計乙個收斂的很快的迭代演算法，通常可能就是找到乙個預處理器，去求解新的方程組極端情況就是預處理器就是你的線性方程組的係數矩陣，這樣你的矩陣條件數就變成1了。

但使用預處理器，你又無法避免求解預處理器的逆，矩陣求逆本質上也是乙個序列演算法，所以你需要設定乙個容易求逆的預處理器，最好能夠並行，而且還能大幅度降低矩陣條件數。

設計乙個並行度較高的結構是極為困難的，線性方程組的係數矩陣其實是可以對映成乙個圖的，對於對稱情況就是乙個無向圖。

當乙個圖可以分成相互不連通的子圖時，子圖和子圖之間是可以並行的，因此，你設計乙個並行結構的本質是設法將原來的圖打斷一些連線，從而得到一些相互不連通的子圖，從而得到乙個並行的結構。這是乙個可以考慮的點。

有乙個針對稀疏線性方程組的求解演算法叫做代數多重網格

範帝楷：大規模對稱正定稀疏線性方程組的求解與代數多重網格

這個方法實際上是考慮在不同的「解析度」下求解方程組，在迭代過程中，你會發現高頻誤差收斂往往很快，低頻往往很慢，因此把「解析度「降低，從而把「原解析度」上的低頻變為現在「低解析度」上的高頻，從而讓難以收斂的部分收斂。

但是這實際上會有另乙個問題，就是如何選擇粗網格(低解析度)上的節點，事實上也有不少演算法，但是選擇了這些節點後，你會做乙個把原來的線性方程組放到粗網格上的過程，這個過程很可能會引入fill in(即導致原來稀疏的問題變稠密)，最終導致粗網格上的計算無法進行。

因此，實際上你是需要設法在粗網格上將線性方程組稀疏化的，但為了盡量不影響原來求解的性質，這又是乙個極為複雜的問題。題主也可以對它進行研究。

如果做出來求解器，期待開源。