Функция Розенброка

График функции Розенброка двух переменных. Здесь $a=1,b=100$ , а минимальное нулевое значение находится при $(1,1)$ .

В математической оптимизации функция Розенброка — это невыпуклая функция , введенная Говардом Х. Розенброком в 1960 году и используемая в качестве задачи проверки производительности оптимизации алгоритмов . ^[1] Она также известна как долина Розенброка или банановая функция Розенброка .

Глобальный минимум находится внутри длинной, узкой, плоской долины параболической формы. Найти долину тривиально. Однако достичь глобального минимума сложно.

Функция определяется

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

Он имеет глобальный минимум в $(x,y)=(a,a^{2})$ , где $f(x,y)=0$ . Обычно эти параметры задаются так, что $a=1$ и $b=100$ . Только в тривиальном случае, когда $a=0$ функция симметрична и минимум находится в начале координат.

Многомерные обобщения

Обычно встречаются два варианта.

Анимация функции трех переменных Розенброка. ^[2]

Один представляет собой сумму $N/2$ несвязанные двумерные задачи Розенброка и определены только для четных $N$ с:

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]

Этот вариант имеет предсказуемо простые решения.

Второй, более сложный вариант:

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]

имеет ровно один минимум для $N=3$ (в $(1,1,1)$ ) и ровно два минимума для $4\leq N\leq 7$ — глобальный минимум в $(1,1,...,1)$ и локальный минимум вблизи ${\hat {\mathbf {x} }}=(-1,1,\dots ,1)$ . Этот результат получается, если установить градиент функции равным нулю, заметив, что полученное уравнение является рациональной функцией $x$ . Для маленьких $N$ полиномы могут быть определены точно, и теорема Штурма может использоваться для определения количества действительных корней, в то время как корни могут быть ограничены в области $|x_{i}|<2.4$ . ^[5] Для большего $N$ этот метод не работает из-за размера используемых коэффициентов.

Стационарные точки

Многие из стационарных точек функции при построении графика имеют регулярный характер. ^[5] Эту структуру можно использовать для их обнаружения.

Примеры оптимизации

Функцию Розенброка можно эффективно оптимизировать путем адаптации соответствующей системы координат без использования какой-либо информации о градиенте и без построения моделей локальной аппроксимации (в отличие от многих оптимизаторов без производных). На следующем рисунке показан пример двумерной оптимизации функции Розенброка с помощью адаптивный спуск по координатам от начальной точки $x_{0}=(-3,-4)$ . Решение со значением функции $10^{-10}$ можно найти после 325 вычислений функции.

Использование метода Нелдера-Мида с начальной точки $x_{0}=(-1,1)$ при правильном начальном симплексе минимум находится по значению функции $1.36\cdot 10^{-10}$ после 185 оценок функций. На рисунке ниже показана эволюция алгоритма.

См. также

Тестовые функции для оптимизации

Ссылки

^ Розенброк, HH (1960). «Автоматический метод нахождения наибольшего или наименьшего значения функции» . Компьютерный журнал . 3 (3): 175–184. дои : 10.1093/comjnl/3.3.175 . ISSN 0010-4620 .
^ Симионеску, Пенсильвания (2014). Инструменты компьютерного построения графиков и моделирования для пользователей AutoCAD (1-е изд.). Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-5290-3 .
^ Диксон, LCW; Миллс, диджей (1994). «Влияние ошибок округления на метод переменной метрики» . Журнал теории оптимизации и приложений . 80 : 175–179. дои : 10.1007/BF02196600 .
^ «Обобщенная функция Розенброка» . Проверено 16 сентября 2008 г.
^ Перейти обратно: ^а ^б Кок, Шалк; Сандрок, Карл (2009). «Нахождение и характеристика стационарных точек расширенной функции Розенброка». Эволюционные вычисления . 17 (3): 437–53. дои : 10.1162/evco.2009.17.3.437 . hdl : 2263/13845 . ПМИД 19708775 .

Внешние ссылки

[1] Розенброк, HH (1960). «Автоматический метод нахождения наибольшего или наименьшего значения функции» . Компьютерный журнал . 3 (3): 175–184. дои : 10.1093/comjnl/3.3.175 . ISSN 0010-4620 .

[2] Симионеску, Пенсильвания (2014). Инструменты компьютерного построения графиков и моделирования для пользователей AutoCAD (1-е изд.). Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-5290-3 .

[3] Диксон, LCW; Миллс, диджей (1994). «Влияние ошибок округления на метод переменной метрики» . Журнал теории оптимизации и приложений . 80 : 175–179. дои : 10.1007/BF02196600 .

[4] «Обобщенная функция Розенброка» . Проверено 16 сентября 2008 г.

[kok2009-5] Перейти обратно: ^а ^б Кок, Шалк; Сандрок, Карл (2009). «Нахождение и характеристика стационарных точек расширенной функции Розенброка». Эволюционные вычисления . 17 (3): 437–53. дои : 10.1162/evco.2009.17.3.437 . hdl : 2263/13845 . ПМИД 19708775 .

[1]

[2]

[3]

[4]

[5]