Rosenbrock function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Plot of the Rosenbrock function of two variables.

In mathematical optimization, the Rosenbrock function is a non-convex function used as a performance test problem for optimization algorithms introduced by Howard H. Rosenbrock in 1960.[1] It is also known as Rosenbrock's valley or Rosenbrock's banana function.

The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial. To converge to the global minimum, however, is difficult.

The function is defined by

f(x, y) = (a-x)^2 + b(y-x^2)^2

It has a global minimum at (x, y)=(a, a^2), where f(x, y)=0. Usually a = 1 and b = 100.

Multidimensional generalisations[edit]

Two variants are commonly encountered. One is the sum of N/2 uncoupled 2D Rosenbrock problems,

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]

This variant is only defined for even N and has predictably simple solutions.

A more involved variant is

f(\mathbf{x}) = \sum_{i=1}^{N-1} 100 (x_{i+1} - x_i^2 )^2 + (1-x_i)^2 \quad \mbox{where} \quad \mathbf{x} = [x_1, \ldots, x_N] \in \mathbb{R}^N.[3]

This variant has been shown to have exactly one minimum for N=3 (at (1, 1, 1)) and exactly two minima for 4 \le N \le 7—the global minimum of all ones and a local minimum near (x_1, x_2, \dots, x_N) = (-1, 1, \dots, 1). This result is obtained by setting the gradient of the function equal to zero, noticing that the resulting equation is a rational function of x. For small N the polynomials can be determined exactly and Sturm's theorem can be used to determine the number of real roots, while the roots can be bounded in the region of |x_i| < 2.4.[4] For larger N this method breaks down due to the size of the coefficients involved.

Stationary points[edit]

Many of the stationary points of the function exhibit a regular pattern when plotted.[4] This structure can be exploited to locate them.

Rosenbrock roots exhibiting hump structures

An example of optimization[edit]

The Rosenbrock function can be efficiently optimized by adapting appropriate coordinate system without using any gradient information and without building local approximation models (in contrast to many derivate-free optimizers). The following figure illustrates an example of 2-dimensional Rosenbrock function optimization by adaptive coordinate descent from starting point x_0=(-3,-4). The solution with the function value 10^{-10} can be found after 325 function evaluations.


See also[edit]


  1. ^ Rosenbrock, H.H. (1960). "An automatic method for finding the greatest or least value of a function". The Computer Journal 3: 175–184. doi:10.1093/comjnl/3.3.175. ISSN 0010-4620. 
  2. ^ Dixon, L. C. W.; Mills, D. J. (1994). "Effect of Rounding Errors on the Variable Metric Method". Journal of Optimization Theory and Applications 80. 
  3. ^ "Generalized Rosenbrock's function". Retrieved 2008-09-16. 
  4. ^ a b Kok, Schalk; Sandrock, Carl (2009). "Locating and Characterizing the Stationary Points of the Extended Rosenbrock Function". Evolutionary Computation 17. doi:10.1162/evco.2009.17.3.437. 


External links[edit]