Rosenbrock函數

维基百科,自由的百科全书
跳转至: 导航搜索
雙變數的Rosenbrock函數

在數學最佳化中,Rosenbrock函數是一個用來測試最佳化演算法性能的非凸函数,由Howard Harry Rosenbrock在1960年提出[1]。也稱為Rosenbrock山谷Rosenbrock香蕉函數,也簡稱為香蕉函數

Rosenbrock函數的定義如下:

f(x, y) = (1-x)^2 + 100(y-x^2)^2 .\quad

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

其全域最小值位於(x, y)=(1, 1)點,數值為f(x, y)=0。有時第二項的係數不同,但不會影響全域最小值的位置。

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

多變數下的擴展[编辑]

多變數的Rosenbrock函數有以下二種形式。一種是N/2個獨立二維Rosenbrock函數的和:

f(\mathbf{x}) = f(x_1, x_2, \dots, x_N) = \sum_{i=1}^{N/2} \left[100(x_{2i-1}^2 - x_{2i})^2
+ (x_{2i-1} - 1)^2 \right].[2]

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

另一個較複雜的形式為:

f(\mathbf{x}) = \sum_{i=1}^{N-1} \left[  (1-x_i)^2+ 100 (x_{i+1} - x_i^2 )^2 \right] \quad \forall  x\in\mathbb{R}^N.[3]

可證明當N=3時,此形式的Rosenbrock函數只有一個最小值(位置在(1, 1, 1)),在 4 \le N \le 7時只有二個最小值,所有變數均為1時有全域最小值,而在(x_1, x_2, \dots, x_N) = (-1, 1, \dots, 1)附近有局部最小值。此結果是將令函數的梯度為0後求得,Rosenbrock函數的梯度仍為一個x的多項式,在N較小時,可以精確的列出多項式,再求出實根的個數,而其根限制在|x_i| < 2.4的範圍內[4]。若N較大時因為相關的係數太多,無法用以上方式進行。

随机函数[编辑]

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

 f(\mathbf{x}) =\sum_{i=1}^{n-1} \Big[(1-x_i)^2+100 \epsilon_i (x_{i+1}-x_i^2)^2 \Big],

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

可適用的最佳化演算法[编辑]

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

Rosenbrock.png

相關條目[编辑]

參考資料[编辑]

  1. ^ Rosenbrock, H.H. An automatic method for finding the greatest or least value of a function. The Computer Journal. 1960, 3: 175–184. doi:10.1093/comjnl/3.3.175. ISSN 0010-4620. 
  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]. 
  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)

外部連結[编辑]