Rosenbrock function

Last updated December 30, 2023

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.

Multidimensional generalizations

Two variants are commonly encountered.

Animation of Rosenbrock's function of three variables. Rosenbrock3.gif — Animation of Rosenbrock's function of three variables.

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

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

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 $N=3$ (at $(1,1,1)$ ) and exactly two minima for $4\leq N\leq 7$ —the global minimum at $(1,1,...,1)$ and a local minimum near ${\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 $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$ .^[5] 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.^[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 $x_{0}=(-3,-4)$ . The solution with the function value $10^{-10}$ can be found after 325 function evaluations.

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

Related Research Articles

In machine learning, support vector machines are supervised max-margin models with associated learning algorithms that analyze data for classification and regression analysis. Developed at AT&T Bell Laboratories by Vladimir Vapnik with colleagues SVMs are one of the most studied models, being based on statistical learning frameworks or VC theory proposed by Vapnik and Chervonenkis (1974).

In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equation constraints. It is named after the mathematician Joseph-Louis Lagrange.

<span class="mw-page-title-main">Convex function</span> Real function with secant line between points above the graph itself

In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph is a convex set. In simple terms, a convex function graph is shaped like a cup $, while a concave function's graph is shaped like a cap .$

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

In mathematics and computing, the Levenberg–Marquardt algorithm, also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least squares curve fitting. The LMA interpolates between the Gauss–Newton algorithm (GNA) and the method of gradient descent. The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well-behaved functions and reasonable starting parameters, the LMA tends to be slower than the GNA. LMA can also be viewed as Gauss–Newton using a trust region approach.

In statistics, nonlinear regression is a form of regression analysis in which observational data are modeled by a function which is a nonlinear combination of the model parameters and depends on one or more independent variables. The data are fitted by a method of successive approximations.

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

Random forests or random decision forests is an ensemble learning method for classification, regression and other tasks that operates by constructing a multitude of decision trees at training time. For classification tasks, the output of the random forest is the class selected by most trees. For regression tasks, the mean or average prediction of the individual trees is returned. Random decision forests correct for decision trees' habit of overfitting to their training set.

In mathematics, the real coordinate space or real coordinate n-space, of dimension $n$ , denoted $R n$ or , is the set of the $n$ -tuples of real numbers, that is the set of all sequences of $n$ real numbers. Special cases are called the real line $R 1$ , the real coordinate plane $R 2$ , and the real coordinate three-dimensional space $R 3$ . With component-wise addition and scalar multiplication, it is a real vector space, and its elements are called coordinate vectors.

In (unconstrained) mathematical optimization, a backtracking line search is a line search method to determine the amount to move along a given search direction. Its use requires that the objective function is differentiable and that its gradient is known.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard. With recent advancements in computing and optimization algorithms, convex programming is nearly as straightforward as linear programming.

Interval arithmetic is a mathematical technique used to mitigate rounding and measurement errors in mathematical computation by computing function bounds. Numerical methods involving interval arithmetic can guarantee relatively reliable and mathematically correct results. Instead of representing a value as a single number, interval arithmetic or interval mathematics represents each value as a range of possibilities.

<span class="mw-page-title-main">Differential evolution</span> Method of mathematical optimization

In evolutionary computation, differential evolution (DE) is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as they make few or no assumptions about the optimized problem and can search very large spaces of candidate solutions. However, metaheuristics such as DE do not guarantee an optimal solution is ever found.

In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the inverse image of any set of the form $is a convex set. For a function of a single variable, along any stretch of the curve the highest point is one of the endpoints. The negative of a quasiconvex function is said to be quasiconcave .$

Penalty methods are a certain class of algorithms for solving constrained optimization problems.

In polynomial interpolation of two variables, the Padua points are the first known example of a unisolvent point set with minimal growth of their Lebesgue constant, proven to be $. Their name is due to the University of Padua, where they were originally discovered.$

Non-linear least squares is the form of least squares analysis used to fit a set of m observations with a model that is non-linear in n unknown parameters (m ≥ n). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box–Cox transformed regressors ( $).$

In mathematics and optimization, a pseudo-Boolean function is a function of the form

Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function $, if it is possible to construct a flow network with positive weights such that$

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for quadratic pseudo-Boolean functions in the form

References

↑ 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.
↑ 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.
↑ 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.
↑ "Generalized Rosenbrock's function" . Retrieved 2008-09-16.
1 2 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.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[kok2009-5] 1 2 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.

[1]

[3]

[4]

[5]