Tesis
Métodos de subgradientes em otimização não suave para problemas de porte enorme
Subgradients methods in nonsmooth optimization for huge-scale problems
Registro en:
Autor
Paiva, Francisco Aulísio dos Santos, 1990-
Institución
Resumen
Orientador: Paulo José da Silva e Silva Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Em otimização convexa, surgem muitas vezes problemas de minimização para os quais as funções não são diferenciáveis em todo seu o domínio, isto é, possuem gradientes descontínuos. Por exemplo, o máximo de funções convexas. Assim, faz-se necessário definir uma noção generalizada desse conceito que é chamada de subgradiente. Isso é possível graças ao fato de que funções convexas possuem derivadas direcionais. As técnicas computacionais que usam subgradientes são muito úteis, principalmente pela simplicidade dos métodos associados. Em um trabalho recente, Nesterov considera uma classe de problemas de porte enorme com subgradientes esparsos e propõe uma implementação eficiente das iterações dos subgradientes, em que o custo total depende logaritmicamente da dimensão do problema. Essa técnica consiste em uma atualização dos resultados do produto matriz vetor e dos valores de funções simétricas através de árvores computacionais. O autor mostra que esse procedimento pode ser usado em métodos de subgradientes simples, como por exemplo os métodos de minimização propostos por Polyak e Shor. Esta dissertação fundamentou-se nos estudos desses métodos, descrevendo-os, analisando a convergência e sua implementação eficiente. Abordamos também todas as ideias e conceitos envolvidos, em particular de análise convexa. Por fim, realizamos experimentos numéricos comparando o tempo computacional do método de Polyak com atualizações de tempo logarítmico e o mesmo método com o cálculo esparso simples do produto matriz-vetor. Ambos os métodos foram testados em um problema chamado PageRank cuja aplicação mais usual é posicionar websites conforme o grau de importância que possui. Abstract: Convex optimization usually deals with minimization schemes for which the functions are not differentiable in their entire domain, i.e., these functions have discontinuous gradients. For example, the maximum of convex functions. That is why it is necessary to define a generalized gradient called subgradient. This is possible for convex functions because they have directional derivatives. The computational techniques that use subgradients are very useful, mainly because of their simplicity. In a recent work, Nesterov deals with a class of huge-scale problems with sparse subgradients.
He proposes an efficient implementation of subgradient iterations whose total
cost depends logarithmically on the problem dimension. This technique is based on a
recursive update of the results of matrix/vector products and the values of symmetric
functions through the use of short computational trees. The author shows that the updating
technique can be used efficiently when coupled with simple subgradient methods,
such as the minimization methods proposed by Polyak and Shor. The work presented here was based on the study of those techniques, describing them, as well as analyzing the convergence of the respective methods and the efficiency of their implementation. It also took into account the proposal of the sparse update of the matrix/vector product as well as all the main mathematical theory involved, including convex analysis. Finally, numerical experiments that compare the computational time of the Polyak method using logarithmic time updates with the same method using the simple calculation of the sparse matrix-vector product are presented. Both techniques were tested using the so-called PageRank problem, an application that aims to rank websites according to their degree of relevance Mestrado Matematica Aplicada e Computacional Mestre em Matemática Aplicada FAEPEX