• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016041P1 Programa de Pós-Graduação em Matemática
    • Teses
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016041P1 Programa de Pós-Graduação em Matemática
    • Teses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    R - T - OLIVER KOLOSSOSKI.pdf (1.498Mb)
    Date
    2016
    Author
    Kolossoski, Oliver
    Metadata
    Show full item record
    Subject
    Matemática aplicada
    Teoria dos jogos
    Jogos de probabilidades (Matemática)
    Algoritmos
    Teses
    xmlui.dri2xhtml.METS-1.0.item-type
    Tese
    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]. 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.
     
    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.
     
    URI
    http://hdl.handle.net/1884/44659
    Collections
    • Teses [45]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV