dc.contributor.advisor | Matioli, Luiz Carlos, 1961- | pt_BR |
dc.contributor.other | Monteiro, Renato | pt_BR |
dc.contributor.other | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Matemática | pt_BR |
dc.creator | Kolossoski, Oliver | pt_BR |
dc.date.accessioned | 2024-04-29T18:56:45Z | |
dc.date.available | 2024-04-29T18:56:45Z | |
dc.date.issued | 2016 | pt_BR |
dc.identifier.uri | https://hdl.handle.net/1884/44659 | |
dc.description | Orientador: Luiz Carlos Matioli | pt_BR |
dc.description | Coorientador: Renato Monteiro | pt_BR |
dc.description | Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa: Curitiba, 02/09/2016 | pt_BR |
dc.description | Inclui referências : f. 106-108 | pt_BR |
dc.description.abstract | Resumo: Neste trabalho são descritos métodos para determinar uma solução (aproximada) para os problemas de ponto-de-sela (PS) e equilíbrio de Nash. Os algoritmos são instâncias especiais do método híbrido extragradiente proximal introduzido por Svaiter e Solodov [Solodov; Svaiter, 2000] onde os sub-problemas de inclusão são resolvidos com o uso de um método de gradiente acelerado. Os métodos propostos generalizam o algoritmo acelerado de [He; Monteiro, 2014] das seguintes maneiras: a) em uma generalização os problemas considerados são problemas PS gerais ao invés de problemas PS com estrutura bilinear; b) em outra generalização o algoritmo é baseado em distâncias de Bregman ao invés da distância Euclidiana; c) em outra generalização o problema considerado é o de equilíbrio de Nash ao invés do problema de ponto-de-sela. Assim como no método de He e Monteiro, os métodos propostos têm a vantagem de que qualquer escolha de escalar para o tamanho do passo pode ser utilizada. Ainda, no contexto de problemas de ponto-de-sela, para certa escolha do tamanho do passo pode-se obter uma complexidade ótima para o método. Resultados computacionais ilustram a performance dos métodos em comparação com o método de suavização de Nesterov [Nesterov, 2005]. | pt_BR |
dc.description.abstract | Abstract: In this work we describe methods to find an (approximate) solution for the saddle-point (SP) and Nash equilibrium problems. The algorithms are special instances of a hybrid extragradient proximal method introduced by Svaiter and Solodov [Solodov; Svaiter, 2000] where the inclusion sub-problems are solved using an accelerated gradient method. The proposed methods generalize the accelerated algorithm of [He; Monteiro, 2014] in the following ways: a) in a generalization, the considered problems are general SP problems instead of SP problems with a bilinear structure; b) in other generalization, the algorithm is based on Bregman distances rather than the Euclidian one; c) in other generalization, the considered problem is the Nash equilibrium problem instead of the saddle-point. As in He and Monteiro's method, the proposed methods have the advantage that any scalar choice for the stepsize can be used. Also, for the saddle-point problems, a certain choice for the stepsize can yield an optimal complexity for the method. Computational results show the performance of the methods in comparison with Nesterov's suavization scheme [Nesterov, 2005]. | pt_BR |
dc.format.extent | 108 f. : il. | pt_BR |
dc.format.mimetype | application/pdf | pt_BR |
dc.language | Português | pt_BR |
dc.relation | Disponível em formato digital | pt_BR |
dc.subject | Matemática aplicada | pt_BR |
dc.subject | Teoria dos jogos | pt_BR |
dc.subject | Jogos de probabilidades (Matemática) | pt_BR |
dc.subject | Algorítmos | pt_BR |
dc.title | Algoritmos híbridos proximais extragradientes para os problemas de ponto de sela e equilíbrio de Nash | pt_BR |
dc.type | Tese | pt_BR |