Esta tese é um estudo acerca do Problema de Equilíbrio de Nash Generalizado (GNEP). Na primeira parte, faremos um resumo dos principais conceitos sobre GNEPs, a relação com outros problemas já conhecidos e comentaremos brevemente os principais métodos já feitos até esta data para resolver numericamente este tipo de problema. Na segunda parte, estudamos condições de otimalidade e condições de qualificação (CQ) para GNEPs, fazendo uma analogia como em otimização. Estendemos os conceitos de cone tangente, normal, gerado pelas restrições ativas, linearizado e polar para a estrutura dos GNEPs. Cada CQ de otimização gera dois tipos de CQ para GNEPs, sendo que a denotada por CQ-GNEP é mais forte e útil para a análise de algoritmos para GNEPs. Mostramos que as condições de qualificação para GNEPs deste tipo em alguns casos não guardam a mesma relação que em otimização. Estendemos também o conceito de Aproximadamente Karush-KuhnTucker (AKKT) de otimização para GNEPs, o AKKT-GNEP. É bem conhecido que AKKT é uma genuína condição de otimalidade em otimização, mas para o caso dos GNEPs mostramos que isto não ocorre em geral. Por outro lado, AKKT-GNEP é satisfeito, por exemplo, em qualquer solução de um GNEP conjuntamente convexo, desde que seja um equilíbrio bvariacional. Com isso em mente, definimos um método do tipo Lagrangiano Aumentado para o GNEP usando penalidades quadráticas e exponenciais e estudamos as propriedades de otimalidade e viabilidade dos pontos limites de sequências geradas pelo algoritmo. Finalmente alguns critérios para resolver os subproblemas e resultados numéricos são apresentados. / This thesis is a study about the generalized Nash equilibrium problem (GNEP). In the first part we will summarize the main concepts about GNEPs, the relationship with other known problems and we will briefly comment on the main methods already done in order to solve these problems numerically. In the second part we study optimality conditions and constraint qualification (CQ) for GNEPs making an analogy with the optimization case. We extend the concepts of the tangent, normal and generated by the active cones, linear and polar cone to the structure of the GNEPs. Each optimization CQ generates two types of CQs for GNEPs, with the one called CQ-GNEP being the strongest and most useful for analyzing the algorithms for GNEPs. We show that the qualification conditions for GNEPs of this type in some cases do not have the same relation as in optimization. We also extend the Approximate Karush- Kuhn-Tucker (AKKT) concept used in optimization for GNEPs to AKKT-GNEP. It is well known that AKKT is a genuine optimality condition in optimization but for GNEPs we show that this does not occur in general. On the other hand, AKKT-GNEP is satisfied, for example, in any solution of a jointly convex GNEP, provided that it is a b-variational equilibrium. With this in mind, we define Augmented Lagrangian methods for the GNEP, using the quadratic and the exponential penalties, and we study the optimality and feasibility properties of the sequence of points generated by the algorithms. Finally some criteria to solve the subproblems and numerical results are presented.
Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-27032018-114413 |
Date | 14 March 2018 |
Creators | Frank Navarro Rojas |
Contributors | Gabriel Haeser, Luis Felipe Cesar da Rocha Bueno, Ernesto Julian Goldberg Birgin, Antoine Laurain, Jefferson Divino Gonçalves de Melo, José Mario Martinez Perez |
Publisher | Universidade de São Paulo, Matemática Aplicada, USP, BR |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | Portuguese |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0522 seconds