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

Author(s)

Ronaldo Lopes

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Defense date: 2018-04-23

Examining board members

Sandra Augusta Santos; José Mario Martínez Pérez; Lucio Tunes dos Santos; Ernesto Julián Goldberg Birgin; Geovani Nunes Grapiglia

• Advisor: Paulo José da Silva e Silva; Sandra Augusta Santos

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 (AU)

• FAPESP's process: 14/14228-6 - Block-coordinate descent methods and identification of active constraints in huge-scale optimization
• Grantee: Ronaldo Lopes
• Support Opportunities: Scholarships in Brazil - Doctorate