2023, випуск 2, c. 46-54
Одержано 18.07.2023; Виправлено 24.07.2023; Прийнято 25.07.2023
Надруковано 28.07.2023; Вперше Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.5
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Обчислювальні експерименти для r(𝛂)-алгоритму з прискореною реалізацією розтягу простору
А.А. Супрун
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
В статті розглянуто модифікацію r(α)-алгоритму з адаптивним регулюванням кроку за напрямком спуску, яка використовує прискорену реалізацію розтягу простору. В класичних варіантах r(α)-алгоритмів розтяг простору здійснюється у напрямку нормованого вектора різниці двох послідовних субградієнтів. У модифікованому r(α)-алгоритмі розтяг простору здійснюється у напрямку, який визначається найбільшими за модулем компонентами вектора різниці двох послідовних субградієнтів. Кількість таких компонент на кожній ітерації модифікованого r(α)-алгоритму змінюється і контролюється за рахунок спеціального параметра. Таким чином, розтяг простору на кожній ітерації відбувається у відповідному підпросторі змінних меншої розмірності, а кількість операцій множення для процедури розтягу простору на кожній ітерації зменшується з 2n2 + 3n до 2nm + 2m + n, де n – розмірність простору, m – кількість ненульових компонент вектора розтягу простору.
Наведено схему модифікованого r(α)-алгоритму та результати обчислювальних експериментів для задач мінімізації опуклих кусково-лінійних та квадратичних яружних функцій. Для розв’язку задач використовувались С++ реалізації класичного r(α)-алгоритму з адаптивним регулюванням кроку за напрямком спуску ralgb5a та його модифікація з прискореною реалізацію розтягу простору ralgb5at. На основі отриманих результатів зазначено, що у порівнянні зі звичайним r(α)-алгоритмом, його модифікований варіант для мінімізації кусково-лінійної функції загалом потребує приблизно таку ж саму кількість ітерацій, але, при цьому, виконує значно меншу кількість операцій множення. Для мінімізації квадратичної строго опуклої функції кількість ітерацій і, як наслідок, час виконання програми, зменшуються. Тому варіанти r-алгоритмів на основі прискореного розтягу простору в напрямках, наближених до напрямку нормованої різниці двох послідовних субградієнтів, можна вважати доволі перспективними, оскільки для деяких класів функцій вони можуть краще враховувати характер яружності функції та, при відповідній програмній реалізації, мати менший час виконання.
Ключові слова: оператор розтягу простору, r(α)-алгоритм, кусково-лінійна функція.
Цитувати так: Супрун А.А. Обчислювальні експерименти для r(𝛂)-алгоритму з прискореною реалізацією розтягу простору. Cybernetics and Computer Technologies. 2023. 2. С. 46–54. https://doi.org/10.34229/2707-451X.23.2.5
Список літератури
1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.
2. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
3. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57.
4. Стецюк П.І., Пилиповський О.В., Хом’як О.М. GNU Octave та Python реалізації r-алгоритму Шора з адаптивним регулюванням кроку. Cybernetics and Computer Technologies. 2022. 3. С. 98–112. https://doi.org/10.34229/2707-451X.22.3.10
5. Стецюк П.І., Жмуд О.О. Про прискорену реалізацію оператору розтягу простору. Питання прикладної математики і математичного моделювання. Тези доповідей ХVIІI міжнародної науково-практичної конференції «Математичне та програмне забезпечення інтелектуальних систем (MPZIS-2020)», м. Дніпро, 18–20 листопада 2020 р. Дніпро: ДНУ, 2020.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна