梯度（最速）下降的實現

我正在尋找一些關於如何在C中實現Gradient (steepest) Descent的建議。我找到了f（x）= || Ax-y ||^2的最小值，其中A （n，n）和y（n）。由於計算梯度Δf（x）= [df/dx（1），...，df/dx（n）]需要計算導數，所以這在C中是困難的（我認爲）。梯度（最速）下降的實現

我只是想在SO拋出此得到一些方向去編程該，如：

1）什麼維度將是最好的開始（1,2，...）

2）如何去這樣做的偏導數

3）是否我應該在一個更簡單的語言實現，如Python，第一個忠告 - 然後在轉換到C

4）等等

讓我知道你的想法！在此先感謝

來源

2010-10-16 dougvk

對於一個想法，你可以看看C中的數值食譜，雖然我不喜歡他們的許可證條款：http://www.fizyka.umk.pl/nrbook/bookcpdf.html – 2010-10-16 19:50:35

1）從2D開始，這樣你可以繪製下降的路徑，並實際看到你的算法工作。（f（x + h）-f（x））/ h時，df/dx =（f（x + h）-f（xh））/（2 * h）如果它很貴。 h的選擇應該平衡截斷誤差（主要是大h）和舍入誤差（小h）。典型的h值是〜pow（DBL_EPSILON，1./3），但實際指數取決於導數公式，理想情況下應該有一個依賴於f的前因子。對於參數空間中的某些給定採樣點，您可以將數值導數繪製爲對數的對數h的函數。然後，您將清楚地看到您正在採樣的點的最佳h範圍。

3）是的，無論你覺得更容易。

4）難點在於找到最佳步長。您可能希望在此使用內部循環來搜索最佳步驟。

來源

2010-10-16 19:38:58

1）我會從一個簡單的一維例子開始，然後一旦我確定這個例子有用，就去2D。 2）如你所知目標函數在前，也許你也可以提供一個分析梯度。如果可能的話，那就是（幾乎）總是比採用數值導數更好。

3）通過一切手段。 4）大概最陡峭的下降只是第一步，接下來可能會查看像CG或BFGS的東西。

來源

2010-10-16 20:05:54 janneb

我找到了給定的A（n，n）和y（n）的最小值f（x）= || Ax-y ||^2。

此問題被稱爲最小二乘法，並且您正在進行無約束優化。用C寫一個有限差分梯度下降求解器根本不是正確的方法。首先，你可以很容易地計算導數分析，所以沒有理由做有限差分。此外，問題是凸的，所以它變得更容易。

（設A」表示A的轉置）

d/dx ||Ax - y||^2 = 2*A'*(Ax - y)

，因爲這是我們知道，當衍生物爲0

0 = 2*A'(Ax - y) 
A'y = A'Ax 
inverse(A'A)*A'y = x

A'A是將發生全球min的covex問題由於它是正定的，所以保證可逆，所以問題簡化爲計算這個反函數，即O（N^3）。也就是說，在C和Python中都有最小二乘的庫，所以你應該使用它們來代替編寫你自己的代碼。

來源

2010-10-16 20:27:39 fairidox

哦，是的，我認爲我的問題很清楚，這是一項重要任務。要在C中完成我自己的任務，並且每次迭代必須根據梯度最小化下降。不過謝謝！ – dougvk 2010-10-17 00:18:39

好的，我看到，在這種情況下，使用我顯示的分析梯度而不是有限差分估計。 – fairidox 2010-10-17 00:19:47

梯度（最速）下降的實現

回答

相關問題