Многоблочный метод ADMM с ускорением Нестерова
Метод ADMM (alternating direction methods of multipliers) широко використовується для розв’язання багатьох оптимізаційних задач за допомогою паралельних обчислень. Цей метод є особливо важливим при розв’язанні задач, які виникають в машинному навчанні, математичній статистиці, розпізнаванні образів,...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2021 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/208947 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Многоблочный метод ADMM с ускорением Нестерова / В.А. Григоренко, Д.А. Клюшин, С.И. Ляшко // Проблемы управления и информатики. — 2021. — № 4. — С. 5–18. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862685345490927616 |
|---|---|
| author | Григоренко, В.А. Клюшин, Д.А. Ляшко, С.И. |
| author_facet | Григоренко, В.А. Клюшин, Д.А. Ляшко, С.И. |
| citation_txt | Многоблочный метод ADMM с ускорением Нестерова / В.А. Григоренко, Д.А. Клюшин, С.И. Ляшко // Проблемы управления и информатики. — 2021. — № 4. — С. 5–18. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Метод 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.
|
| first_indexed | 2025-12-07T16:00:48Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-208947 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:00:48Z |
| publishDate | 2021 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Григоренко, В.А. Клюшин, Д.А. Ляшко, С.И. 2025-11-09T18:58:59Z 2021 Многоблочный метод ADMM с ускорением Нестерова / В.А. Григоренко, Д.А. Клюшин, С.И. Ляшко // Проблемы управления и информатики. — 2021. — № 4. — С. 5–18. — Бібліогр.: 18 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208947 519.853.6 10.34229/1028-0979-2021-4-1 Метод 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Многоблочный метод ADMM с ускорением Нестерова Багатоблочний метод ADMM з прискоренням Нестерова Multiblock ADMM method with Nesterov acceleration Article published earlier |
| spellingShingle | Многоблочный метод ADMM с ускорением Нестерова Григоренко, В.А. Клюшин, Д.А. Ляшко, С.И. Методы оптимизации и оптимальное управление |
| title | Многоблочный метод ADMM с ускорением Нестерова |
| title_alt | Багатоблочний метод ADMM з прискоренням Нестерова Multiblock ADMM method with Nesterov acceleration |
| title_full | Многоблочный метод ADMM с ускорением Нестерова |
| title_fullStr | Многоблочный метод ADMM с ускорением Нестерова |
| title_full_unstemmed | Многоблочный метод ADMM с ускорением Нестерова |
| title_short | Многоблочный метод ADMM с ускорением Нестерова |
| title_sort | многоблочный метод admm с ускорением нестерова |
| topic | Методы оптимизации и оптимальное управление |
| topic_facet | Методы оптимизации и оптимальное управление |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/208947 |
| work_keys_str_mv | AT grigorenkova mnogobločnyimetodadmmsuskoreniemnesterova AT klûšinda mnogobločnyimetodadmmsuskoreniemnesterova AT lâškosi mnogobločnyimetodadmmsuskoreniemnesterova AT grigorenkova bagatobločniimetodadmmzpriskorennâmnesterova AT klûšinda bagatobločniimetodadmmzpriskorennâmnesterova AT lâškosi bagatobločniimetodadmmzpriskorennâmnesterova AT grigorenkova multiblockadmmmethodwithnesterovacceleration AT klûšinda multiblockadmmmethodwithnesterovacceleration AT lâškosi multiblockadmmmethodwithnesterovacceleration |