Algoritmos para o problema de equilíbrio aplicados ao problema de equilíbrio de NASH

Abstract

Resumo: 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 dificuldades 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 dificuldades 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 definem 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 {(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.

Abstract: 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 differentiable 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 difficulties in relation with the solution of the G(x) = 0 system, such as, the lack of differentiability and convexity, however the continuity of G(x) is certain. To overcome the presented difficulties, two difficulties methodologies shall be developed to resolver G(x) = 0. The first one consists in smoothing the no differentiable term, for the functions that define G(x) = 0 become continuously differentiable. 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 {(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 differentiable, 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 first is based on the Newton Method and the second on the Subgradient Methods for resolving a none-linear and not differentiable G(x) = 0.