Governo Federal

Dados do Trabalhos de Conclusão

UNIVERSIDADE FEDERAL DO PARANÁ
MÉTODOS NUMÉRICOS EM ENGENHARIA (40001016030P0)
Algoritmos para o Problema de Equilibrio Aplicados ao Problema de Equilibrio de Nash
EUDA MARA DA SILVA
TESE
20/09/2013

Nesta pesquisa são apresentados dois novos algoritmos para resolução do Problema de Equilíbrio de Nash (NEP), ambos baseados na resolução de um sistema não linear G(x) = 0, sendo G : IRn → IRn contínua, mas não diferenciável em todos os pontos do domínio. Assim, a origem desses métodos é o artigo de IUSEM e NASRI (2007a) em que foi introduzido o método de Lagrangeano Aumentado, para a resolução de um Problema de Equilíbrio geral, do qual o Problema de Equilíbrio de Nash é um caso particular. Existem algumas diculdades com relação à solução do sistema G(x) = 0, a saber: a falta de diferenciabilidade e de convexidade. O que pode ser garantido é a continuidade da G(x). Para superar as diculdades apresentadas serão desenvolvidas duas metodologias diferentes para resolver G(x) = 0. A primeira consiste na suavização do termo não diferenciável para tornar as funções que denem G(x) = 0 continuamente diferenciáveis. Após a suavização, será aplicado o Método de Newton para resolver o sistema não linear. A segunda consiste em resolver o sistema G(x) = 0 por meio de um problema de otimização, ou seja, ao invés de resolver G(x) = 0 será resolvido o problema minimizar{f(x) : x ∈ IRn } com f(x) = 1 2 ||G(x)||2 . Para isto, será utilizado um procedimento similar ao Método do Gradiente. Primeiramente, suaviza-se as funções em G(x) que são não diferenciáveis, como realizado para o Método de Newton, aplica-se o Método do Gradiente com busca Barzilai Borwein para resolver G(x) = 0. Uma vez que o Método do Gradiente tem convergência lenta, do ponto de vista computacional pode até não convergir, este será substituído por Métodos Subgradientes para resolver o sistema G(x) = 0. Portanto, a principal contribuição deste trabalho é a apresentação de duas novas metodologias para a resolução do Problema de Equilíbrio de Nash. A primeira, baseada no Método de Newton, e a segunda, em Métodos Subgradientes para resolver um sistema não linear e não diferenciável G(x) = 0.

Problema de Equilíbrio de Nash; Problema de Equilíbrio de Nash Generalizado; Métodos Subgradientes; Método de Newton; Problema de Equilíbrio; Algoritmos para solução de um NEP.
This research presents two new algorithms in order to resolve the Nash Equilibrium Problem (NEP), both are based on the resolution of a none linear G(x) = 0 system, where G : IRn → IRn is continuous, but not dierentiable in all points of domain. Therefore, the origin of these methods is the article of IUSEM e NASRI (2007a) where the method of increased lagrangian was introduced, for solving a Generalized Nash Equilibrium Problem, where the equilibrium is a particular case. There are certain diculties in relation with the solution of the G(x) = 0 system, such as, the lack of dierentiability and convexity, however the continuity of G(x) is certain. To overcome the presented diculties, two dierent methodologies shall be developed to resolver G(x) = 0. The rst one consists in smoothing the nondierentiable term, for the functions that dene G(x) = 0 become continuously dierentiable. After the smoothing a Newton method shall be applied to resolve the none-linear system. And, the second one consists in resolving the G(x) = 0 system through a problem of optimization, that is, instead of resolving G(x) = 0 the problem of minimize{f(x) : x ∈ IRn } shall be resolved with f(x) = 1 2 ||G(x)||2 . Thereby, a similar procedure to the gradient method shall be used. Firstly, the functions in G(x) that are dierentiable, shall be smoothed, as held in the Newton method, by applying the method of gradient with Barzilai Borwein research to resolve G(x) = 0. Once the method of gradient has a slow convergence and from a computational point of view might even not converge, this method shall be replaced by Subgradient Methods to resolve the G(x) = 0 system. Thence, the main contribution of this paper is the presentation of two new methodologies for the resolution of the Nash Equilibrium Problem, where the rst is based on the Newton Method and the second on the Subgradient Methods for resolving a none-linear and not dierentiable G(x) = 0.
Nash Equilibrium Problem; Generalized Nash Equilibrium Problem; Subgradient Methods; Newton Method; Equilibrium Problem; Algorithms for a NEP solution.
01
116
PORTUGUES
UNIVERSIDADE FEDERAL DO PARANÁ

Contexto

PROGRAMAÇÃO MATEMÁTICA
ABORDAGEM DE PROBLEMAS DE OTIMIZAÇÃO E DE ANÁLISE NUMÉRICA
-

Banca Examinadora

LUIZ CARLOS MATIOLI
Sim
Nome Categoria
JULIANO DE BEM FRANCISCO Participante Externo
SOLANGE REGINA DOS SANTOS Participante Externo
MAEL SACHINE Participante Externo
SUSANA SCHEIMBERG DE MAKLER Participante Externo

Vínculo

CLT
Empresa Privada
Ensino e Pesquisa
Não