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

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

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

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

• Test functions for optimization

Notes

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

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, MR 0136042

External links

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