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

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

Графік функції Розенброка для двох змінних. В даному прикладіі ${\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}$, функція симетрична, а мінімум знаходиться в початку координат.

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

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

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

Ця багатовимірна функція є сумою ${\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].}$^[3]

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

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

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

має рівно один мінімум для ${\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}$.^[5] Для більшого ${\displaystyle N}$ цей метод не працює через велике значення задіяних коефіцієнтів.

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

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

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

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

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

Функцію Розенброка можна ефективно оптимізувати шляхом адаптації відповідної системи координат без використання будь-якої інформації про градієнт і без побудови локальних апроксимаційних моделей (на відміну від багатьох оптимізаторів без похідних). Наступний малюнок ілюструє приклад двовимірної оптимізації функції Розенброка за допомогою адаптивного спуску координат від початкової точки ${\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 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. Процитовано 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. {{cite journal}}: |hdl-access= вимагає |hdl= (довідка)

Посилання

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