羅森布羅克函數

在數學最佳化中,羅森布羅克函數是一個用來測試最佳化演算法效能的非凸函數,由霍華德·哈里·羅森布羅克】在1960年提出[1]。也稱為羅森布羅克山谷羅森布羅克香蕉函數,也簡稱為香蕉函數

雙變數的羅森布羅克函數

羅森布羅克函數的定義如下:

羅森布羅克函數的每個等高線大致呈拋物線形,其全域最小值也位在拋物線形的山谷中(香蕉型山谷)。很容易找到這個山谷,但由於山谷內的值變化不大,要找到全域的最小值相當困難。

其全域最小值位於點,數值為。有時第二項的系數不同,但不會影響全域最小值的位置。

用羅森布羅克函數測試梯度下降法的結果,約1000次才到達全域最小值

多變數下的擴展

多變數的羅森布羅克k函數有以下二種形式。一種是 個獨立二維羅森布羅克函數的和:

 [2]

此形式只在 為偶數時有定義,而且其解較簡單。

另一個較複雜的形式為:

 [3]

可證明當 時,此形式的羅森布羅克函數只有一個最小值(位置在 ),在  時只有二個最小值,所有變數均為1時有全域最小值,而在 附近有局部最小值。此結果是將令函數的梯度為0後求得,羅森布羅克函數的梯度仍為一個 的多項式,在 較小時,可以精確的列出多項式,再求出實根的個數,而其根限制在 的範圍內[4]。若 較大時因為相關的系數太多,無法用以上方式進行。

隨機函數

有許多方式可以將羅森布羅克函數延伸到隨機(stochastic)函數,以下是一種例子:[5]

 

其中隨機變量 服從均勻分佈 Unif(0,1)。原則上,此隨機函數的全域最小值仍在(1,1,...,1),不過因為其隨機的特性,任何以梯度下降法為基礎的最佳化演算法均無法用來求得此隨機函數的最小值。

可適用的最佳化演算法

經若經過適當的坐標系調整,可以在沒有梯度資訊及不建立局部近似模型的情形下(和其他不使用梯度資訊的最佳化演算法相反),用最佳化演算法求得羅森布羅克函數的最小值。以下的例子說明如何用適應坐標下降法英語Adaptive coordinate descent對二維的羅森布羅克函數進行最佳化,啟始點 。在325次函數的運算後可找到最小值的位置,函數的數值為 

 

相關條目

參考資料

  1. ^ Rosenbrock, H.H. An automatic method for finding the greatest or least value of a function. The Computer Journal. 1960, 3: 175–184. ISSN 0010-4620. doi:10.1093/comjnl/3.3.175. 
  2. ^ L C W Dixon, D J Mills. Effect of Rounding errors on the Variable Metric Method. Journal of Optimization Theory and Applications 80, 1994. [1]頁面存檔備份,存於互聯網檔案館
  3. ^ Generalized Rosenbrock's function. [2008-09-16]. (原始內容存檔於2008-09-26). 
  4. ^ Schalk Kok, Carl Sandrock. Locating and Characterizing the Stationary Points of the Extended Rosenbrock Function. Evolutionary Computation 17, 2009. [2]頁面存檔備份,存於互聯網檔案館
  5. ^ Yang X.-S. and Deb S., Engineering optimization by cuckoo searc1h, Int. J. Math. Modelling Num. Optimisation, Vol. 1, No. 4, 330-343 (2010)

外部連結