Métodos numéricos para equilíbrio de Nash com critério de descenso

• Processo: 21/05007-0
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de julho de 2021
• Data de Término da vigência: 31 de julho de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Matemática - Matemática Aplicada
• Pesquisador responsável: Gabriel Haeser
• Beneficiário: Oliver Kolossoski
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 18/24293-0 - Métodos computacionais de otimização, AP.TEM
• Assunto(s): Otimização Métodos numéricos Método de lagrangiano aumentado
• Palavra(s)-Chave do Pesquisador: condições de otimalidade | Equilibrio De Nash | Lagrangeano Aumentado | Otimização

Resumo

Este trabalho tem como objetivo desenvolver um algoritmo baseado em Lagrangeano aumentado para encontrar um ponto de equilíbrio para o problema de equilíbrio de Nash de dois jogadores. Os métodos da literatura para este tipo de problema usam da teoria de condições de otimalidade para encontrar pontos estacionários via condições de Karush-Kuhn-Tucker (KKT) fazendo uso de alguma condição de qualificação. Embora estas condições sejam necessárias para que um ponto limite da sequência gerado pelos algoritmos seja um ponto de equilíbrio, ela não é suficiente, conforme ilustra Haeser et. al. em trabalhos anteriores. Por conta disso, métodos baseados em KKT para problemas de equilíbrio de Nash encontram pontos de sela ou máximos locais com frequência, ao invés de determinar soluções do problema. O método aqui proposto fará o uso da estrutura de minimização dos subproblemas de otimização gerados pela abordagem de Lagrangeano aumentado para encontrar um critério de parada do algoritmo que seja baseado em descenso, e não levando em conta as condições de KKT. Visamos também estudar a possibilidade de uso de condições de otimalidade sequenciais, similares a estudos realizados por Haeser et. al., em trabalhos recentes para outros tipos de problemas. Neste projeto visa-se estabelecer as propriedades de convergência deste algoritmo, bem como demonstrar a boa performance prática em relação aos demais métodos para este tipo de problema do estado da arte. (AU)