Багатоблочний метод ADMM з прискоренням Нестерова
Метод ADMM (alternating direction methods of multipliers) широко используется для решения многих оптимизационных задач с помощью параллельных вычислений. Этот метод особенно важен при решении задач, возникающих в машинном обучении, математической статистике, распознавании образов, восстановлении сиг...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2021
|
| Теми: | |
| Онлайн доступ: | https://jais.net.ua/index.php/files/article/view/137 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems of Control and Informatics |
Репозитарії
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-137 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2024-03-14T10:43:57Z |
| collection |
OJS |
| language |
Russian |
| topic |
ADMM (alternating direction method of multipliers) багатоблочний ADMM прискорення Нестерова прискорений ADMM |
| spellingShingle |
ADMM (alternating direction method of multipliers) багатоблочний ADMM прискорення Нестерова прискорений ADMM Hrygorenko, Vladislav Klyushin, Dmitriy Lyashko , Sergey Багатоблочний метод ADMM з прискоренням Нестерова |
| topic_facet |
ADMM (alternating direction method of multipliers) multiblock ADMM fast ADMM Nesterov acceleration ADMM (alternating direction method of multipliers) багатоблочний ADMM прискорення Нестерова прискорений ADMM ADMM (alternating direction method of multipliers) многоблочный ADMM ускорение Нестерова |
| format |
Article |
| author |
Hrygorenko, Vladislav Klyushin, Dmitriy Lyashko , Sergey |
| author_facet |
Hrygorenko, Vladislav Klyushin, Dmitriy Lyashko , Sergey |
| author_sort |
Hrygorenko, Vladislav |
| title |
Багатоблочний метод ADMM з прискоренням Нестерова |
| title_short |
Багатоблочний метод ADMM з прискоренням Нестерова |
| title_full |
Багатоблочний метод ADMM з прискоренням Нестерова |
| title_fullStr |
Багатоблочний метод ADMM з прискоренням Нестерова |
| title_full_unstemmed |
Багатоблочний метод ADMM з прискоренням Нестерова |
| title_sort |
багатоблочний метод admm з прискоренням нестерова |
| title_alt |
Многоблочный метод ADMM с ускорением Нестерова Multi-block ADMM method with Nesterov acceleration |
| description |
Метод ADMM (alternating direction methods of multipliers) широко используется для решения многих оптимизационных задач с помощью параллельных вычислений. Этот метод особенно важен при решении задач, возникающих в машинном обучении, математической статистике, распознавании образов, восстановлении сигналов, обработке данных значительного объема. ADMM позволяет решать оптимизационные задачи, целевая функция которых представляет собой сумму гладкой и негладкой функций, что характерно для задач со штрафной функцией. Целью этой статьи является разработка улучшенной версии ADMM с лучшей скоростью сходимости, чем существующие методы. В статье описаны существующие подходы для улучшения эффективности ADMM-метода, приведены основные работы по данной тематике и предложен новый метод, базирующийся на комбинации двух уже существующих подходов - разбиение начальной оптимизационной задачи на N подзадач и применение многоблочного подхода для разрешение и вычисление ускорения Нестерова на каждой итерации. Приведены теоретическое обоснование сходимости данного метода и установлены условия сходимости. Реализован предлагаемый алгоритм языка программирования Python и применен для решения задачи обмена с генерируемыми случайным образом данными, задачи поиска базиса и задачи LASSO с ограничениями. Приведены результаты сравнения эффективности многоблочного ADMM с ускорением Нестерова и существующих многоблочного и стандартного двухблочного ADMM. Многоблочный ADMM с ускорением Нестерова показал лучшую вычислительную эффективность, чем уже существующие методы. Еще одним преимуществом предлагаемого метода является его удобство для проведения параллельных вычислений с применением современных многопроцессорных систем. В связи с большими объемами данных, обработка которых требует значительного времени при решении оптимизационных задач, предложенный метод имеет важное практическое значение, поскольку он значительно превышает по скорости известные аналоги. Использование предложенного метода позволит решить практически важные задачи большого объема, применив параллельные вычисления. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2021 |
| url |
https://jais.net.ua/index.php/files/article/view/137 |
| work_keys_str_mv |
AT hrygorenkovladislav mnogobločnyjmetodadmmsuskoreniemnesterova AT klyushindmitriy mnogobločnyjmetodadmmsuskoreniemnesterova AT lyashkosergey mnogobločnyjmetodadmmsuskoreniemnesterova AT hrygorenkovladislav bagatobločnijmetodadmmzpriskorennâmnesterova AT klyushindmitriy bagatobločnijmetodadmmzpriskorennâmnesterova AT lyashkosergey bagatobločnijmetodadmmzpriskorennâmnesterova AT hrygorenkovladislav multiblockadmmmethodwithnesterovacceleration AT klyushindmitriy multiblockadmmmethodwithnesterovacceleration AT lyashkosergey multiblockadmmmethodwithnesterovacceleration |
| first_indexed |
2025-10-30T02:48:41Z |
| last_indexed |
2025-10-30T02:48:41Z |
| _version_ |
1847373354854514688 |
| spelling |
oai:ojs2.jais.net.ua:article-1372024-03-14T10:43:57Z Многоблочный метод ADMM с ускорением Нестерова Багатоблочний метод ADMM з прискоренням Нестерова Multi-block ADMM method with Nesterov acceleration Hrygorenko, Vladislav Klyushin, Dmitriy Lyashko , Sergey ADMM (alternating direction method of multipliers) multiblock ADMM fast ADMM Nesterov acceleration ADMM (alternating direction method of multipliers) багатоблочний ADMM прискорення Нестерова прискорений ADMM ADMM (alternating direction method of multipliers) многоблочный ADMM ускорение Нестерова Метод ADMM (alternating direction methods of multipliers) широко используется для решения многих оптимизационных задач с помощью параллельных вычислений. Этот метод особенно важен при решении задач, возникающих в машинном обучении, математической статистике, распознавании образов, восстановлении сигналов, обработке данных значительного объема. ADMM позволяет решать оптимизационные задачи, целевая функция которых представляет собой сумму гладкой и негладкой функций, что характерно для задач со штрафной функцией. Целью этой статьи является разработка улучшенной версии ADMM с лучшей скоростью сходимости, чем существующие методы. В статье описаны существующие подходы для улучшения эффективности ADMM-метода, приведены основные работы по данной тематике и предложен новый метод, базирующийся на комбинации двух уже существующих подходов - разбиение начальной оптимизационной задачи на N подзадач и применение многоблочного подхода для разрешение и вычисление ускорения Нестерова на каждой итерации. Приведены теоретическое обоснование сходимости данного метода и установлены условия сходимости. Реализован предлагаемый алгоритм языка программирования Python и применен для решения задачи обмена с генерируемыми случайным образом данными, задачи поиска базиса и задачи LASSO с ограничениями. Приведены результаты сравнения эффективности многоблочного ADMM с ускорением Нестерова и существующих многоблочного и стандартного двухблочного ADMM. Многоблочный ADMM с ускорением Нестерова показал лучшую вычислительную эффективность, чем уже существующие методы. Еще одним преимуществом предлагаемого метода является его удобство для проведения параллельных вычислений с применением современных многопроцессорных систем. В связи с большими объемами данных, обработка которых требует значительного времени при решении оптимизационных задач, предложенный метод имеет важное практическое значение, поскольку он значительно превышает по скорости известные аналоги. Использование предложенного метода позволит решить практически важные задачи большого объема, применив параллельные вычисления. Метод ADMM (alternating direction methods of multipliers) широко використовується для розв’язання багатьох оптимізаційних задач за допомогою паралельних обчислень. Цей метод є особливо важливим при розв’язанні задач, які виникають в машинному навчанні, математичній статистиці, розпізнаванні образів, відновленні сигналів, обробці даних значного об’єму. ADMM дає змогу розв’язувати оптимізаційні задачі, цільова функція яких являє собою суму гладкої та негладкої функцій, що є характерним для задач з штрафною функцією. Метою цієї статті є розробка покращеної версії ADMM з кращою швидкістю збіжності, ніж вже існуючі методи. В статті описано існуючі підходи для покращення ефективності ADMM-методу, наведено основні роботи з даної тематики та запропоновано новий метод, який базується на комбінації двох вже існуючих підходів — розбиття початкової оптимізаційної задачі на N підзадач та застосування багатоблочного підходу для розв’язання і обчислення прискорення Нестерова на кожній ітерації. Наведено теоретичне обгрунтування збіжності даного методу та встановлено умови збіжності. Реалізовано запропонований алгоритм мовою програмування Python і застосовано для розв’язання задачі обміну з генерованими випадковим чином даними, задачі пошуку базису та задачі LASSO з обмеженнями. Наведено результати порівняння ефективності багатоблочного ADMM з прискоренням Нестерова та існуючих багатоблочного і стандартного двоблочного ADMM. Багатоблочний ADMM з прискоренням Нестерова показав кращу обчислювальну ефективність, ніж вже існуючі методи. Ще однією перевагою запропонованого методу є його зручність для проведення паралельних обчислень із застосуванням сучасних багатопроцесорних систем. В зв’язку з великими об’ємами даних, обробка яких вимагає значного часу при розв’язанні оптимізаційних задач, запропонований метод має важливе практичне значення, оскільки він значно перевищує за швидкістю відомі аналоги. Використання запропонованого методу дасть можливість розв’язати практично важливі задачі великого обсягу, застосувавши паралельні обчислення. ADMM (alternating direction methods of multipliers) is widely used to solve many optimization problems. This method is especially important for solving problems arising in great variety of fields, especially in machine learning, mathematical statistics and pattern recognition, signal denoising and big data analysis using parallel computations. ADMM also useful for solving optimization problems in cases when objective function presented as sum of smooth and non-smooth functions. Standard two block ADMM can be extended for solving problems where objective function can be represented as sum of N functions (multiblock approach). In this paper we described some most common used technics used for acceleration of ADMM and reviewed most significant works related to this topic. The aim of this paper is to develop an improved version of the ADMM with better convergence rate. For this, we used a combination of two already existing approaches: splitting the initial optimization problem into subtasks and solving them in parallel using multiblock approach and calculating the Nesterov acceleration at each iteration step. We provided a theoretical justification for the convergence of this method, defined necessary for convergence conditions, and also implemented the proposed algorithm in the Python programming language and applied it to solve the problem of exchange with random data, basis pursuit problem and LASSO with restrictions problem. The article presents the results of comparing the effectiveness of the multiblock ADMM method with Nesterov acceleration and the existing multiblock and standard two-block ADMM method. Multiblock ADMM with Nesterov acceleration demonstrates better performance that already existing methods and also can be easily adopted for parallel calculation. Proposed method has great practical value due to necessity to solve optimization problems with great volumes of data, which requires high performance, because it works much more faster than well-known analogies. The use of the proposed method will make it possible to solve practically important problems of large volume using parallel calculations. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2021-03-09 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/137 10.34229/1028-0979-2021-4-1 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 66 № 4 (2021): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5-18 International Scientific Technical Journal "Problems of Control and Informatics; Том 66 № 4 (2021): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-18 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 66 No. 4 (2021): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-18 2786-6505 2786-6491 10.34229/1028-0979-2021-4 ru https://jais.net.ua/index.php/files/article/view/137/228 Copyright (c) 2021 Vladislav Hrygorenko, Dmitriy Klyushin, Sergey Lyashko https://creativecommons.org/licenses/by-nc-nd/4.0 |