Block-coordinate descent methods and active-set identification for huge-scale problems

Orientadores: Sandra Augusta Santos, Paulo José da Silva e SilvaTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação CientíficaResumo: Neste trabalho desenvolvemos estratégias de identificação das restrições ativas para o método de descenso coordenado por blocos aplicado a problemas de otimização irrestritos, ou em caixas, cuja função objetivo é a soma de uma função suave e outra convexa. Mostramos que, em certas situações, o método tem a capacidade intrínseca de identificação e também apresentamos um exemplo de função identificadora compatível com a simplicidade computacional exigida pelos problemas de porte enorme. Combinando essas estratégias, desenvolvemos um método de descenso coordenado por blocos, denominado \emph{Active BCDM}, que busca explorar as restrições ativas do problema com restrições de caixa ou, no caso irrestrito, de uma reformulação auxiliar relacionada que possui variáveis não negativas. Analisamos nosso método em duas classes de problemas com muita relevância no contexto de otimização de porte enorme: \textit{LASSO} e regressão logística com regularização $\ell_1$. Preparamos uma ampla discussão de resultados numéricos utilizando problemas reais extraídos da literatura. Isso permite a comparação do \emph{Active BCDM} com vários métodos bem estabelecidos e do estado da arte para estes problemas, tanto no caso sequencial quanto no paralelo. Em ambas implementações, a proposta de identificação apresentou desempenho computacional superior aos métodos com os quais foi comparada. Além disso, resultados de convergência global acompanham os algoritmos propostos, reforçando sua consistência e relevância teóricaAbstract: This work is concerned with the development of strategies to identify active constraints for the block-coordinate descent method applied to unconstrained, or box-constrained, optimization problems whose objective function is the sum of a smooth component and a convex one. We show that, under appropriate assumptions, the method has an intrinsic identification capacity. We also present an example of an identification function compatible with the computational simplicity required to address large-scale problems. Combining these strategies, we have developed a block-coordinate descent method, called Active BCDM, which aims to explore the active constraints in box-constrained problems, or, in the unconstrained case, of a related auxiliary reformulation with non negative variables. We analyze the performance of our method for solving two classes of problems with great relevance in the context of huge-scale optimization: LASSO and $\ell_1$-regularized logistic regression. We have prepared an extensive discussion of numerical results using real problems from the literature. This allows the comparison of Active BCDM with several well-established and state-of-the-art methods for such problems, with sequential and parallel implementations. In both implementations, the identification strategy presented better computational performance among the methods under comparison. In addition, global convergence results have been proved for the proposed algorithms, reinforcing their consistency and theoretical relevanceDoutoradoMatematica AplicadaDoutor em Matemática Aplicada2014/14228-6FAPES