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} \left[  (1-x_i)^2+ 100 (x_{i+1} - x_i^2 )^2 \right] \quad \forall  x\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.

Rosenbrock.png

See also[edit]

Notes[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. ^ 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". Retrieved 2008-09-16. 
  4. ^ a b Schalk Kok, Carl Sandrock. Locating and Characterizing the Stationary Points of the Extended Rosenbrock Function. Evolutionary Computation 17, 2009. [2]

References[edit]

External links[edit]