2022, випуск 4, c. 45-55
Одержано 17.12.2022; Виправлено 19.12.2022; Прийнято 20.12.2022
Надруковано 29.12.2022; Вперше Online 28.02.2023
https://doi.org/10.34229/2707-451X.22.4.4
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про субградієнтні методи з кроком Поляка та перетворенням простору
В.О. Стовба * 
, О.О. Жмуд
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Мінімізація яружних опуклих функцій, як гладких, так і негладких, виникає в багатьох задачах планування, керування, аналізу стійкості динамічних систем, штучному інтелекті та машинному навчанні. Тому розвиток нових та покращення наявних методів є важливою задачею, зважаючи на те, що дедалі частіше функції, що мінімізуються, залежать від великої кількості змінних.
Особливої уваги заслуговують методи, що використовують операцію лінійного перетворення простору, які дозволяють покращити властивості цільової функції і значно прискорити її мінімізацію. Відомі методи такого типу, зокрема методи еліпсоїдів та r-алгоритми, потребують перерахунку матриці перетворення на кожній ітерації. Тому розвиток методів з разовим перетворенням простору, що мають меншу ціну ітерації, є безумовно актуальною задачею.
Мета роботи. Огляд модифікацій субградієнтного методу з кроком Поляка, що використовують скалярний параметр m³1 та операцію разового перетворення простору. Доповнити обґрунтування збіжності та швидкості збіжності описаних модифікацій. Навести рекомендації стосовно підбору параметру m та матриці перетворення простору B.
Результати. Субградієнтний метод з кроком Поляка у перетвореному просторі та параметром m>1 є ефективним методом мінімізації гладких та негладких опуклих функцій, які мають яружну структуру. Підбір доцільного значення параметра m³1 та матриці перетворення простору B дозволяє суттєво прискорити цей метод і використовувати його для мінімізації функцій, що залежать від великої кількості змінних.
Висновки. Розвиток швидких методів мінімізації негладких опуклих функцій багатьох змінних з яружною структурою дозволяє ефективно розв’язувати сучасні задачі штучного інтелекту, зокрема задачі машинного навчання, розпізнавання образів, аналізу даних великих об’ємів тощо.
Ключові слова: субградієнтний метод, перетворення простору, яружні функції.
Цитувати так: Стовба В.О., Жмуд О.О. Про субградієнтні методи з кроком Поляка та перетворенням простору. Cybernetics and Computer Technologies. 2022. 4. С. 45–55. https://doi.org/10.34229/2707-451X.22.4.4
Список літератури
1. Agmon S. The relaxation method for linear inequalities. Canad. J. Math. 1954. No. 6. P. 382−392. https://doi.org/10.4153/CJM-1954-037-2
2. Motzkin T., Schoenberg I. The relaxation method for linear inequalities. Canad. J. Math. 1954. No. 6. P. 393−404. https://doi.org/10.4153/CJM-1954-038-x
3. Поляк Б.Т. Введение в оптимизацию. М.: Наука. 1983.384 с.
4. Polyak B.T. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics. 1969. 9 (3). P. 14–29. https://doi.org/10.1016/0041-5553(69)90061-5
5. Еремин И.И. Обобщение релаксационного метода Агмона-Моцкина. УМН. 1965. 20 (122). С. 183–187.
6. Брэгман Л.М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования. ЖВМ и МФ. 1967. 7 (3). С. 200–217. https://doi.org/10.1016/0041-5553(67)90040-7
7. Стецюк П.И. r-алгоритмы и эллипсоиды. Кибернетика и системный анализ. 1996. № 1. С. 113–134. https://doi.org/10.1007/BF02366587
8. Стецюк П.И. Ортогонализующие линейные операторы в выпуклом программировании. І. Кибернетика и системный анализ. 1997. № 3. С. 97–119. https://doi.org/10.1007/BF02733072
9. Стецюк П.И. Ортогонализующие линейные операторы в выпуклом программировании. ІІ. Кибернетика и системный анализ. 1997. № 5. С. 111–124. https://doi.org/10.1007/BF02667194
10. Гершович В.И., Шор Н.З. Метод эллипсоидов, его обобщения и приложения. Кибернетика. 1982. № 5. С. 61–69. https://doi.org/10.1007/BF01068741
11. Стецюк П.И. Метод amsg2p для овражных выпуклых функций. Информационный бюллетень Ассоциации математического программирования. 2011. № 12. С. 57–58.
12. Стовба В.О. Субградієнтний метод з кроком Поляка у перетвореному просторі : дис. на здобуття наук. ступеня д-ра філософії : 113 Прикладна математика / Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2021. 184 с.
13. Стецюк П.І. Ускорение субградиентного метода Поляка. Теорія оптимальних рішень. 2012. № 11. С. 151–60. http://dspace.nbuv.gov.ua/handle/123456789/85030
14. Стецюк П.І., Стовба В.О., Жмуд О.О. Про швидкість збіжності субградієнтних методів з кроком Поляка. Наук. вісник Ужгород. ун-ту. Сер. матем. і інформ. 2019. 1 (34). С. 94–101. https://doi.org/10.24144/2616-7700.2019.1(34).94-101
15. Сергиенко И.В., Стецюк П.И. О трех научных идеях Н.З. Шора. Кибернетика и системный анализ. 2012. № 1. С. 4–22. https://doi.org/10.1007/s10559-012-9387-x
16. Stetsyuk P., Stovba V., Chernousova Z. Subgradient method with Polyak’s step in transformed space. Optimization and Applications (OPTIMA 2018). 2018. Vol. 974. P. 49–63. https://doi.org/10.1007/978-3-030-10934-9_4
17. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика. 1977. № 1. С. 94–95. https://doi.org/10.1007/BF01071394
18. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов. Кибернетика. 1971. № 3. С. 51–59. https://doi.org/10.1007/BF01070454
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна