Research On Models And Algorithms For Distributed Optimization Based On The Non-cooperative Games

The solution procedures of many problems in the real world may boil down to the optimization process on complex objectives. Among many optimization problems, the distributed optimization problem is one typical problem because it provides the groundwork for a decision making architecture that is oriented to large-scale and dynamically changing network environments. And in the solving mechanism of distributed optimization, lots of decision makers with local information make rational decisions in responses to the dynamically evolving information exchange environment and the regional knowledge of the problem. Also the distributed decision making architecture possesses several desirable attributes such as real-time adaptation and guarantees of the desirable global behavior with respect to the given system level objective. However, realizing these benefits requires addressing the analytical difficulties for the large-scale interacting decision makers under incomplete information. Furthermore, the time-varying characters resulting from the dynamically evolving information exchange environment bring additional complexity to the implement of distributed solving mechanism.Non-cooperative games are beginning to emerge as a powerful tool to analyze and model the interacting behaviors in the distributed problems. In this dissertation, the novel game based approaches for solving the distributed optimization problem are presented. Depending on the different information exchange environments, the different game models and distributed decision learning algorithms are proposed respectively, which together construct the game theory based framework and make sure the desirable global optimization objective can be ensured through the evolving of decisions of the distributed and adaptive solvers.Specifically speaking, the main work of this dissertation is as follows:(1) The existing research methods for solving distributed optimization problems have been analyzed and summarized. After that, the profound relationship between optimization problems and dynamical games is disclosed, and the possibility of developing a systematic game theory based framework for distributed decision making in local and time-varying environment is established.(2) In order to solve the distributed optimization problem under bidirectional and time-varying information exchange, the state based ordinal potential games are employed to build game models for the distribution of the optimization problems. Not only the payoff function is provided for each decision maker to make rational decisions under local and time varying information, but also the degree of freedom of designing game models for each decision makers is improved and the real-time adaptation to the dynamically changing information topologies is ensured. Moreover, all the equilibriums of the game model designed are verified to be optimal solutions to the distributed optimization problem.(3) Based on the historical information of decision maker’s decisions and payoffs of its own, the payoff based baseline learning algorithm is provided for the state based ordinal potential games to implement the dynamical update of decisions. And the learning algorithm is proved to ensure the decisions of all decision makers converge to the equilibrium of the state based ordinal potential game.(4) In order to solve the distributed optimization problem under the directed and time varying information exchange among individual decision makers, the state based weakly acyclic games are developed to formulate and accommodate the directed and dynamical interactions of decision makers under the game framework. In particular, the adaptation to local and time varying information conditions is ensured by designing payoff functions for each decision makers. Moreover, by making optimal decisions with local and directed information, the efficiency of resulting equilibriums in the game model is guaranteed with respect to the given system level objective.(5) As for the state based weakly acyclic game model, by using the directed and local information gathered over previous game stages, the inertial based learning algorithm is provided to determine how individuals update their strategies at any stage. And the algorithm ensures the decision process converges to the equilibrium of the state based weakly acyclic game.