Функция Розенброка: тест для алгоритмов оптимизации
Rosenbrock function
Функция Розенброка: тест для алгоритмов оптимизации. Невыпуклая функция, сложная для поиска глобального минимума из-за узкой долины. Оптимизация, математика.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Функция, используемая в качестве тестовой задачи для оценки производительности алгоритмов оптимизации.
Function used as a performance test problem for optimization algorithms
В математической оптимизации функция Розенброка — это невыпуклая функция, представленная Говардом Розенброком в 1960 году и используемая в качестве тестовой задачи для оценки производительности алгоритмов оптимизации. Она также известна как «долина Розенброка» или «банановая функция Розенброка». Глобальный минимум находится внутри длинной, узкой, параболической плоской долины. Найти эту долину — тривиальная задача. Однако сходимость к глобальному минимуму представляет собой значительную трудность. Функция определяется как
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. 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
Она имеет глобальный минимум в точке , где Обычно эти параметры устанавливаются так, что и Только в тривиальном случае, когда , функция симметрична, и минимум находится в начале координат.
It has a global minimum at , where Usually, these parameters are set such that and Only in the trivial case where the function is symmetric and the minimum is at the origin.
Стационарные точки
Многие стационарные точки функции демонстрируют закономерный рисунок при построении графика. Эту закономерность можно использовать для их нахождения.
Many of the stationary points of the function exhibit a regular pattern when plotted. This structure can be exploited to locate them.
Примеры оптимизации
Функция Розенброка может быть эффективно оптимизирована путем адаптации подходящей системы координат без использования информации о градиенте и без построения локальных аппроксимационных моделей (в отличие от многих оптимизаторов, не использующих производные). На следующем рисунке показан пример оптимизации двумерной функции Розенброка с помощью адаптивного спуска по координатам, начиная с точки. Решение со значением функции может быть найдено после 325 вычислений функции. Используя метод Нельдера-Мида, начиная с точки, с регулярным начальным симплексом, минимум находится со значением функции после 185 вычислений функции. Ниже на рисунке визуализирована эволюция алгоритма.
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 The solution with the function value can be found after 325 function evaluations. Using the Nelder–Mead method from starting point with a regular initial simplex a minimum is found with function value after 185 function evaluations. The figure below visualizes the evolution of the algorithm.