Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Matioli, Luiz Carlos, 1967- | - |
Autor(es): dc.contributor | Monteiro, Renato | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Matemática | - |
Autor(es): dc.creator | Kolossoski, Oliver | - |
Data de aceite: dc.date.accessioned | 2019-08-21T23:13:46Z | - |
Data de disponibilização: dc.date.available | 2019-08-21T23:13:46Z | - |
Data de envio: dc.date.issued | 2017-05-18 | - |
Data de envio: dc.date.issued | 2017-05-18 | - |
Data de envio: dc.date.issued | 2016 | - |
Fonte completa do material: dc.identifier | http://hdl.handle.net/1884/44659 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/44659 | - |
Descrição: dc.description | Orientador : Luiz Carlos Matioli | - |
Descrição: dc.description | Coorientador : Renato Monteiro | - |
Descrição: 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 | - |
Descrição: dc.description | Inclui referências : f. 106-108 | - |
Descrição: dc.description | 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]. Palavras-chaves: programação convexa, complexidade, convergência ergódica, operador monótono maximal, método híbrido extragradiente proximal, método de gradiente acelerado, problema de ponto de sela, problema de equilíbrio de Nash, distância de Bregman. | - |
Descrição: dc.description | 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]. Key-words: convex programming, complexity, ergodic convergence, maximal monotone operator, hybrid proximal extragradient method, accelerated gradient method, inexact proximal method, saddle point problem, Nash equilibrium problem, Bregman distances. | - |
Formato: dc.format | 108 f. : il. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Relação: dc.relation | Disponível em formato digital | - |
Palavras-chave: dc.subject | Matemática aplicada | - |
Palavras-chave: dc.subject | Teoria dos jogos | - |
Palavras-chave: dc.subject | Jogos de probabilidades (Matemática) | - |
Palavras-chave: dc.subject | Algoritmos | - |
Palavras-chave: dc.subject | Teses | - |
Título: dc.title | Algoritmos híbridos proximais extragradientes para os problemas de ponto de sela e equilíbrio de Nash | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: