Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/332887
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Métodos de descenso coordenado por blocos e identificação das restrições ativas em otimização de porte enorme
Title Alternative: Block-coordinate descent methods and active-set identification for huge-scale problems
Author: Lopes, Ronaldo, 1988-
Advisor: Santos, Sandra Augusta, 1964-
Abstract: Resumo: 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órica

Abstract: 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 relevance
Subject: Otimização matemática
Algoritmos
Convergência global
Processamento paralelo (Computadores)
Problemas de grande porte (Matemática)
Language: Português
Editor: [s.n.]
Date Issue: 2018
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Lopes_Ronaldo_D.pdf1.33 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.