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

Функція Розенброка у математичній оптимізації — неопукла функція, яка використовується для тестування продуктивності алгоритмів оптимізації. Була представлена ^[en] у 1960 році.

Графік функції Розенброка для двох змінних. В даному прикладіі ${\displaystyle a=1,b=100}$, а мінімальне значення функції дорівнює нулю і досягається в координатах ${\displaystyle (1,1)}$.

Глобальний мінімум функції знаходиться всередині довгої вузької плоскої фігури параболічної форми. Що робить складним пошук шлях до глобального мінімуму для алгоритмів оптимізації.

Функція визначається як:

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

Функція має глобальний мінімум при ${\displaystyle (x,y)=(a,a^{2})}$, де ${\displaystyle f(x,y)=0}$. Зазвичай ці параметри встановлюються так, що ${\displaystyle a=1}$ і ${\displaystyle b=100}$. Але тільки в тривіальному випадку, де ${\displaystyle a=0}$, функція симетрична, а мінімум знаходиться в початку координат.

Багатовимірні узагальнення

Зазвичай зустрічаються два варіанти.

Анімація функції Розенброка трьох змінних

Ця багатовимірна функція є сумою ${\displaystyle N/2}$ незв'язаних 2D функцій Розенброка, і визначається лише для парних ${\displaystyle N}$:

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

Цей варіант має передбачувано прості рішення.

Другий, більш складний варіант:

${\displaystyle f(\mathbf {x} )=\sum _{i=1}^{N-1}[100(x_{i+1}-x_{i}^{2})^{2}+(1-x_{i})^{2}],\quad {\text{де}}\quad \mathbf {x} =(x_{1},\ldots ,x_{N})\in \mathbb {R} ^{N}.}$

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

Стаціонарні точки

Багато стаціонарних точок функції демонструють правильну закономірність під час побудови. Цю структуру можна використати, щоб знайти їх.

Графіки розв'язання цієї функції мають горбисті структури

Приклади оптимізації

Метод Нелдера-Міда, застосований до функції Розенброка

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

Використання методу Нелдера–Міда з початкової точки ${\displaystyle x_{0}=(-1,1)}$ з регулярним початковим симплексом. Мінімум знайдено зі значенням функції ${\displaystyle 1.36\cdot 10^{-10}}$ після 185 оцінок функцій.

Див. також

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

Список літератури

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). Boca Raton, FL: CRC Press. ISBN .
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. Процитовано 16 вересня 2008.
5. 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. PMID 19708775. {{}}: |hdl-access= вимагає |hdl= ()

Посилання

• Тривимірний графік функції Розенброка
• Weisstein, Eric W. Функція Розенброка(англ.) на сайті Wolfram MathWorld.