Relative-error inexact versions of Douglas-Rachford and ADMM splitting algorithms

Abstract

Nesta tese, propomos e analisamos novas versões do método Douglas-Rachford splitting (DRS) para operadores monótonos maximais e do alternating direction method of multipliers (ADMM) para otimização convexa. Inicialmente, apresentamos um método Douglas-Rachford splitting (DRS) inexato e um método Douglas-Rachford-Tseng forwardbackward (F-B) splitting para resolver inclusões monótonas de dois e quatro operadores, respectivamente. Provamos complexidade computacional em iteração, tanto no sentido pontual quanto no sentido ergódico, mostrando que ambos os algoritmos admitem duas iterações diferentes: uma que pode ser incorporada ao hybrid proximal extragradient (HPE) method de Solodov e Svaiter, para a qual a complexidade em iteração é conhecida desde o trabalho de Monteiro e Svaiter, e outra que exige uma análise em separado. Em seguida, estudamos o comportamento assintótico de novas variantes dos algoritmos DRS e ADMM, ambos com efeito de relaxação e inércia, e com critério de erro relativo para os subproblemas. Por fim, com objetivo de demonstrar a aplicabilidade dos métodos propostos neste trabalho, realizamos experimentos numéricos aplicando nosso método ADMM (relaxado e com inércia) aos problemas LASSO e regressão logística.

Abstract: In this thesis, we propose and analyze new versions of the Douglas-Rachford splitting (DRS) method for maximal monotone operators and the alternating direction method of multipliers (ADMM) for convex optimization. Firstly, we present an inexact DouglasRachford splitting (DRS) method and a Douglas-Rachford-Tseng?s forward-backward (F-B) splitting method for solving two-operator and four-operator monotone inclusions, respectively. We prove iteration-complexity bounds for both algorithms in the pointwise (non-ergodic) as well as in the ergodic sense by showing that they admit two different iterations: one that can be embedded into the Solodov and Svaiter?s hybrid proximal extragradient (HPE) method, for which the iteration-complexity is known since the work of Monteiro and Svaiter, and another one that demands a separate analysis. We also study the asymptotic behavior of new variants of the DRS and ADMM splitting methods, both under relaxation and inertial effects, and with inexact (relative-error) criterion for subproblems. To demonstrate the applicability of the proposed methods, we performed numerical experiments applying the ADMM (relaxed and inertial) on LASSO and logistic regression problems.