2020, випуск 1, c. 5-14
Одержано 07.02.2020; Виправлено 15.02.2020; Прийнято 10.03.2020
Надруковано 31.03.2020; Вперше Online 26.04.2020
https://doi.org/10.34229/2707-451X.20.1.1
Попередня | Повний текст | Наступна
СТОХАСТИЧНИЙ МЕТОД зГЛАДЖУВАННЯ ДЛЯ НЕГЛАДКОЇ ГЛОБАЛЬНОЇ ОПТИМІЗАЦІЇ
В.І.
Норкін 1, 2 * 
1 Інститут кібернетики імені В.М. Глушкова НАН України, Київ, Україна
2 Національний технічний університет України «Київський політехнічний інститут ім. Ігоря Сікорського»
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Реферат. Проблема глобальної оптимізації неопуклих негладких функцій з обмеженнями є актуальною для багатьох інженерних застосувань, зокрема, для навчання неопуклих негладких нейронних мереж. У роботі представлені результати тестування методу згладжування багатоекстремальної цільової функції для знаходження її глобального мінімуму в деякій опуклій допустимій області евклідового простору. Попередньо цільова функція довизначається поза опуклої допустимої області так, щоб не змінити її глобального мінімуму, та зробити її коерцитивною.
Згладжування функції в будь-якій точці здійснюється шляхом усереднення значень функції по деякому околу цієї точки. Розмір околу є параметром згладжування. Традиційно локальне згладжування використовувалось для гладкої апроксимації недиференційованих або розривних функцій. Більш широке згладжування ліквідує мілкі локальні екстремуми вихідної функції. При великому параметрі згладжування усереднена коерцитивна функція може мати лише один мінімум.
Метод згладжування для глобальної оптимізації функцій полягає у заміні вихідної функцій послідовністю згладжених апроксимацій зі зменшенням до нуля параметра згладжування та оптимізації останніх сучасними методами стохастичної оптимізації (метод усереднення траєкторії, важкої кульки, яружного кроку). При цьому градієнти згладжених функцій представляються у вигляді багатовимірних інтегралів та оцінюються методом Монте-Карло. Пересуваючись від мінімуму однієї згладженої функції до близького мінімуму другої згладженої функції з меншим параметром згладжування, можна потрапити в область глобального мінімуму вихідної функції. Остаточну дооптимізацію функції можна зробити будь-яким підходящим методом нелінійного програмування.
Метод згладжування без будь-яких змін може бути застосований для оптимізації негладких яружних функцій за опуклих обмежень, а також у комбінації з методом точних негладких штрафів.
Показано, що метод згладжування впевнено розв’язує тестові задачі глобальної оптимізації невеликої розмірності з літератури. При збільшенні розмірності задачі час розв’язання значно зростає у зв'язку з необхідністю багатократної оцінки багатовимірних інтегралів методом Монте-Карло.
Ключові слова: глобальна оптимізація; згладжування за Стекловим; усереднені функції; стохастична оптимізація; негладка неопукла оптимізація.
Цитувати так: Норкін В.І. Стохастичний метод згладжування для негладкої глобальної оптимізації. Cybernetics and Computer Technologies. 2020. 1. С. 5–14. https://doi.org/10.34229/2707-451X.20.1.1
Список літератури
1. Steklov V.A. Sur les expressions asymptotiques de certaines fonctions d´efinies par les equations differentielles du second ordre et leurs applications au probleme du developement dune fonction arbitraire en series procedant suivant les diverses fonctions. Communications de la Société mathématique de Kharkow, Série 2. 1907. 10. P. 97–199.
2. Gupal A.M. A method for the minimization of almost-differentiable functions. Cybernetics. 1977. 13 (1). P. 115–117. https://doi.org/10.1007/BF01071397
3. Gupal A.M., Norkin V.I. Algorithm for the minimization of discontinuous functions. Cybernetics. 1977. 13 (2). P. 220–223. https://doi.org/10.1007/BF01073313
4. Норкин В.И. Два алгоритма случайного поиска для минимизации недифференцируемых функций. Математические методы исследования операций и теории надежности. Ред. Ермольев Ю.М., Коваленко И.Н. Институт кибернетики Академии наук Украинской ССР: Киев, 1978. С. 36–40.
5. Гупал А.М. Стохастические методы решения негладких экстремальных задач. Наукова думка: Киев, 1979.
6. Михалевич В.С., Гупал А.М., Норкин В.И. Методы невыпуклой оптимизации. Наука: Москва, 1987.
7. Ermoliev Y.M., Norkin V.I., Wets R.J.-B. The minimization of semicontinuous functions: mollifier subgradients. SIAM J. Control Optim. 1995. 33 (1). C. 149–167. https://doi.org/10.1137/S0363012992238369
8. Юдин Д. Б. Методы количественного анализа сложных систем. Изв. АН СССР. Техн. кибернетика. 1965. 1. С. 3–13.
9. Норкин В.И. Два замечания: о методе сглаживания в многоэкстремальной оптимизации и о конечно-разностном методе в недифференцируемой оптимизации. Тезисы III Всесоюзного семинара «Численные методы нелинейного программирования». ХГУ: Харьков, 1979.
10. Arıkan O., Burachik R.S., Kaya C.Y. Steklov Regularization and Trajectory Methods for Univariate Global Optimization. J. Glob. Optim. 2020. 76 (1). P. 91–120. https://doi.org/10.1007/s10898-019-00837-3
11. Burachik R.S., Kaya C.Y. Steklov Convexification and a Trajectory Method for Global Optimization of Multivariate Quartic Polynomials. 2019. https://arxiv.org/abs/1912.00332v1
12. Clarke F.H. Optimization and Nonsmooth Analysis, 2nd ed.; Volume 5 of Classics in Applied Mathematics. SIAM: Philadelphia, PA. 1990. https://doi.org/10.1137/1.9781611971309
13. Ермольев Ю. М. Методы стохастического программирования. М.: Наука, 1976.
14. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
15. Ermoliev Y.M., Norkin V.I. Solution of nonconvex nonsmooth stochastic optimization problems. Cybern. Syst. Anal. 2003. 39 (5). P. 701-715. https://doi.org/10.1023/B:CASA.0000012091.84864.65
16. Bottou L., Curtis F.E., Nocedal J. Optimization Methods for Large-Scale Machine Learning. SIAM Review. 2018. 60 (2). P. 223–311. https://doi.org/10.1137/16m1080173
17. Törn A., Zilinskas A. Global Optimization. Springer: Berlin. 1989. https://doi.org/10.1007/3-540-50871-6
18. Qi L., Wan Z., Yang Y.-F. Global Minimization of Normal Quartic Polynomials Based on Global Descent Directions. SIAM J. Optim. 2004. 15 (1). P. 275–302. https://doi.org/10.1137/s1052623403420857
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна