Resumo: Uma classe de problemas de interesse relativamente recente e de diversas aplicações práticas,porém de difícil análise e solução, é o de minimização de uma função continuamentediferenciável limitada inferiormente sobre um conjunto separável em blocos disjuntos,envolvendo uma penalidade e/ou limitação que implica na esparsidade desses blocos. Essadissertação aborda esse tema sob a ótica da recente metodologia e teoria apresentada noartigo "Optimization problems involving group sparsity terms" de Amir Beck e NadavHallak (BECK; HALLAK, 2018a) com o intuito de comparar abordagens e apresentarintuições e ferramentas para o tratamento de problemas relevantes em campos comoteoria dos grafos, compressed sensing e portfólios de investimentos. Serão abordados, nessecontexto, conceitos de mapeamento proximal, além de algoritmos eficientes para resolveros problemas estudados, enfatizando variações não monótonas. Particularmente, foramexploradas duas estratégias alternativas, sendo elas a aceleração de Nesterov com estratégiade inércia tipo FISTA (BECK; TEBOULLE, 2009a; BECK; TEBOULLE, 2009b) e métodosde segunda ordem quasi-Newton unidimensional (espectral ou Barzilai-Borwein-Raydan(BARZILAI; BORWEIN, 1988)) e algumas de suas variações, ademais incluindo pesquisaspreliminares sobre o tema de modelos de segunda ordem com maior número de variáveis.Para ambas essas estratégias gerais, extensa pesquisa foi efetuada na literatura que traduzos resultados clássicos para o contexto dos nossos problemas, tendo em vista tanto adescontinuidade e não-convexidade da norma l0 e a natureza compósita do problema quedifere dos problemas que originaram os métodos espectrais. Condições de continuidadede Lipschitz sobre o gradiente da parte suave para métodos com buscas lineares nãomonótonas foram abandonadas em favor de condições de continuidade uniforme, seguindoa tendência que (KANZOW; MEHLITZ, 2021) estabeleceu para versões monótonas. Foramproduzidos novos resultados de convergência para hipóteses alternativas que permitemtanto descontinuidade quanto não monotonia dos algoritmos, elementos não conciliadosanteriormente. Essas estratégias de demonstração também foram aplicadas em um novoalgoritmo que utiliza ideias de aceleração FISTA com variável de monitoramento para lidarcom funções não convexas, adaptado do trabalho (LI; LIN, 2015). Resultados numéricospreliminares apontam a eficácia de algumas dessas alternativas para o contexto investigadoe estimulam um futuro aprofundamento no tema. Uma nova generalização do operadorproximal para uma classe de funções envolvendo a norma l0 é também apresentada edemonstrada, com potencial emprego em modelagens que se beneficiariam de um maiorcontrole da esparsidade das soluções Ver menos

Abstract: A class of problems of relatively recent interest and of diverse practical applications,yet difficult to analyze and solve, is the minimization of an lower bounded continuouslydifferentiable function over a disjoint block separable set, involving a penalty and/orconstraint that result in the sparsity of such blocks. This dissertation covers this themefrom the perspective of the recent methodology and theory presented in the article"Optimization problems involving group sparsity terms" by Amir Beck and Nadav Hallak(BECK; HALLAK, 2018a) in order to compare approaches and present insights andtools for the treatment of relevant problems in areas such as graph theory, compressedsensing and investment portfolios. In this context, concepts of proximal mappings willbe treated, in addition to efficient algorithms to solve the studied problems, focusingon nonmonotone variants. Particularly, two alternative strategies were explored, namely Nesterov acceleration with a FISTA-type inertia strategy (BECK; TEBOULLE, 2009a;BECK; TEBOULLE, 2009b) and one-dimensional quasi-Newton second-order methods(spectral or Barzilai-Borwein-Raydan step methods (BARZILAI; BORWEIN, 1988)) andsome of their variations, furthermore including preliminary research on the topic ofsecond order models with higher number of variables. For both of these general strategies,extensive research was carried out in the literature that translates the classical results tothe context of our problems, taking into account both the discontinuity and non-convexityof the l0 norm and the composite nature of the problem that differs from spectralmethods’ origins. Lipschitz continuity conditions on the gradient of the smooth part formethods with nonmonotone line searches were abandoned in favor of uniform continuityconditions, following the trend that (KANZOW; MEHLITZ, 2021) established for monotoneversions. New convergence results have been produced for alternative hypotheses thatallow for both discontinuity and non-monotonicity of the algorithms, elements that werenot previously reconciled. These proof strategies were also applied to a new algorithm thatincorporates FISTA acceleration ideas with a monitoring variable to handle non-convexfunctions, adapted from the work (LI; LIN, 2015). Preliminary numerical results indicatethe effectiveness of some of these alternatives for the investigated context and encouragefuture delving into the topic. A new generalization of the proximal operator for a classof functions involving the l0 norm is also presented and demonstrated, with potentialapplications in modeling approaches that would benefit from greater control over thesparsity of the solutions Ver menos