Métodos de subgradientes em otimização não suave para problemas de porte enorme
Subgradients methods in nonsmooth optimization for huge-scale problems
| dc.creator | Paiva, Francisco Aulísio dos Santos, 1990- | |
| dc.date | 2015 | |
| dc.date | 2017-04-02T19:55:39Z | |
| dc.date | 2017-06-21T18:35:44Z | |
| dc.date | 2017-04-02T19:55:39Z | |
| dc.date | 2017-06-21T18:35:44Z | |
| dc.date.accessioned | 2018-03-29T02:58:17Z | |
| dc.date.available | 2018-03-29T02:58:17Z | |
| dc.identifier | PAIVA, Francisco Aulísio dos Santos. Métodos de subgradientes em otimização não suave para problemas de porte enorme. 2015. 1 recurso online (70 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica, Campinas, SP. Disponível em: <http://www.bibliotecadigital.unicamp.br/document/?code=000953587>. Acesso em: 2 abr. 2017. | |
| dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/305791 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1324146 | |
| dc.description | Orientador: Paulo José da Silva e Silva | |
| dc.description | Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica | |
| dc.description | 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. | |
| dc.description | 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 | |
| dc.description | Mestrado | |
| dc.description | Matematica Aplicada e Computacional | |
| dc.description | Mestre em Matemática Aplicada | |
| dc.description | FAEPEX | |
| dc.format | 1 recurso online (70 p.) : il., digital, arquivo PDF. | |
| dc.format | application/pdf | |
| dc.publisher | [s.n.] | |
| dc.relation | Requisitos do sistema: Software para leitura de arquivo em PDF | |
| dc.subject | Métodos subgradientes | |
| dc.subject | Otimização não diferenciável | |
| dc.subject | Subgradient methods | |
| dc.subject | Nonsmooth optimization | |
| dc.title | Métodos de subgradientes em otimização não suave para problemas de porte enorme | |
| dc.title | Subgradients methods in nonsmooth optimization for huge-scale problems | |
| dc.type | Tesis |