Многоблочный метод ADMM с ускорением Нестерова

Abstract

Метод 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.