Algoritmos híbridos proximais extragradientes para os problemas de ponto de sela e equilíbrio de Nash

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorMatioli, Luiz Carlos, 1967--
Autor(es): dc.contributorMonteiro, Renato-
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Matemática-
Autor(es): dc.creatorKolossoski, Oliver-
Data de aceite: dc.date.accessioned2019-08-21T23:13:46Z-
Data de disponibilização: dc.date.available2019-08-21T23:13:46Z-
Data de envio: dc.date.issued2017-05-18-
Data de envio: dc.date.issued2017-05-18-
Data de envio: dc.date.issued2016-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/1884/44659-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/44659-
Descrição: dc.descriptionOrientador : Luiz Carlos Matioli-
Descrição: dc.descriptionCoorientador : Renato Monteiro-
Descrição: dc.descriptionTese (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.descriptionInclui referências : f. 106-108-
Descrição: dc.descriptionResumo: 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.descriptionAbstract: 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.format108 f. : il.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectMatemática aplicada-
Palavras-chave: dc.subjectTeoria dos jogos-
Palavras-chave: dc.subjectJogos de probabilidades (Matemática)-
Palavras-chave: dc.subjectAlgoritmos-
Palavras-chave: dc.subjectTeses-
Título: dc.titleAlgoritmos híbridos proximais extragradientes para os problemas de ponto de sela e equilíbrio de Nash-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.