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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Графік функції Розенброка для двох змінних. В даному прикладіі , а мінімальне значення функції дорівнює нулю і досягається в координатах .

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

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

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

Функція має глобальний мінімум при , де . Зазвичай ці параметри встановлюються так, що і . Але тільки в тривіальному випадку, де , функція симетрична, а мінімум знаходиться в початку координат.

Багатовимірні узагальнення[ред. | ред. код]

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

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

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

[3]

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

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

[4]

має рівно один мінімум для (при ) і рівно два мінімуми для  — глобальний мінімум при і локальний мінімум поблизу . Цей результат отримано шляхом встановлення градієнта функції рівним нулю, зауваживши, що отримане рівняння є раціональною функцією . Для маленьких поліноми можна визначити точно, а теорему Штурма можна використати для визначення кількості справжніх коренів, тоді як корені можуть бути обмежені в області .[5] Для більшого цей метод не працює через велике значення задіяних коефіцієнтів.

Стаціонарні точки[ред. | ред. код]

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

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

Приклади оптимізації[ред. | ред. код]

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

Функцію Розенброка можна ефективно оптимізувати шляхом адаптації відповідної системи координат без використання будь-якої інформації про градієнт і без побудови локальних апроксимаційних моделей (на відміну від багатьох оптимізаторів без похідних). Наступний малюнок ілюструє приклад двовимірної оптимізації функції Розенброка за допомогою адаптивного спуску координат від початкової точки . Розв'язок зі значенням функції можна знайти після 325 оцінок функцій.

Використання методу Нелдера–Міда з початкової точки з регулярним початковим симплексом. Мінімум знайдено зі значенням функції після 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. ISSN 0010-4620. doi:10.1093/comjnl/3.3.175. 
  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. PMID 19708775. doi:10.1162/evco.2009.17.3.437. 

Посилання[ред. | ред. код]