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.