Rosenbrock function

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. 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.

It is defined by

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

It has a global minimum at (x,y) = (1,1) where f(x,y) = 0. A different coefficient of the second term is sometimes given, but this does not affect the position of the global minimum.

Multidimensional generalisations

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].$

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.$

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 . For larger N this method breaks down due to the size of the coefficients involved.

Stationary points

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

Stochastic version

There are many ways to extend this function stochastically. In Xin-She Yang's functions, a generic or heuristic extension of Rosenbrock's function is given to extend this function into a stochastic function

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

where the random variables $\epsilon_i (i=1,2,...,n-1)$ obey a uniform distribution Unif(0,1). In principle, this stochastic function has the same global optimimum at (1,1,...,1), however, the stochastic nature of this function makes it impossible to use any gradient-based optimization algorithms.

See also

• Himmelblau's function

References

• 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, MR0136042 

External links

• Rosenbrock function plot in 3D
• Minimizing the Rosenbrock Function by Michael Croucher, The Wolfram Demonstrations Project.
• Weisstein, Eric W., "Rosenbrock Function" from MathWorld.