Jump to content

# Rosenbrock function

In mathematical optimization, the Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is used as a performance test problem for optimization algorithms.[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

${\displaystyle f(x,y)=(a-x)^{2}+b(y-x^{2})^{2}}$

It has a global minimum at ${\displaystyle (x,y)=(a,a^{2})}$, where ${\displaystyle f(x,y)=0}$. Usually, these parameters are set such that ${\displaystyle a=1}$ and ${\displaystyle b=100}$. Only in the trivial case where ${\displaystyle a=0}$ the function is symmetric and the minimum is at the origin.

## Multidimensional generalizations

Two variants are commonly encountered.

One is the sum of ${\displaystyle N/2}$ uncoupled 2D Rosenbrock problems, and is defined only for even ${\displaystyle N}$s:

${\displaystyle 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].}$[3]

This variant has predictably simple solutions.

A second, more involved variant is

${\displaystyle 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}.}$[4]

has exactly one minimum for ${\displaystyle N=3}$ (at ${\displaystyle (1,1,1)}$) and exactly two minima for ${\displaystyle 4\leq N\leq 7}$—the global minimum at ${\displaystyle (1,1,...,1)}$ and a local minimum near ${\displaystyle {\hat {\mathbf {x} }}=(-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 ${\displaystyle x}$. For small ${\displaystyle 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 ${\displaystyle |x_{i}|<2.4}$.[5] For larger ${\displaystyle 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.[5] This structure can be exploited to locate them.

## Optimization examples

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 ${\displaystyle x_{0}=(-3,-4)}$. The solution with the function value ${\displaystyle 10^{-10}}$ can be found after 325 function evaluations.

Using the Nelder–Mead method from starting point ${\displaystyle x_{0}=(-1,1)}$ with a regular initial simplex a minimum is found with function value ${\displaystyle 1.36\cdot 10^{-10}}$ after 185 function evaluations. The figure below visualizes the evolution of the algorithm.

## References

1. ^ Rosenbrock, H.H. (1960). "An automatic method for finding the greatest or least value of a function". The Computer Journal. 3 (3): 175–184. doi:10.1093/comjnl/3.3.175. ISSN 0010-4620.
2. ^ Simionescu, P.A. (2014). Computer Aided Graphing and Simulation Tools for AutoCAD users (1st ed.). Boca Raton, FL: CRC Press. ISBN 978-1-4822-5290-3.
3. ^ Dixon, L. C. W.; Mills, D. J. (1994). "Effect of Rounding Errors on the Variable Metric Method". Journal of Optimization Theory and Applications. 80: 175–179. doi:10.1007/BF02196600.
4. ^ "Generalized Rosenbrock's function". Retrieved 2008-09-16.
5. ^ a b Kok, Schalk; Sandrock, Carl (2009). "Locating and Characterizing the Stationary Points of the Extended Rosenbrock Function". Evolutionary Computation. 17 (3): 437–53. doi:10.1162/evco.2009.17.3.437. hdl:2263/13845. PMID 19708775.