Lehrinhalte
[b]Part I: Classical theory of unconstrained and constrained optimization:[/b]
[list]
[*]useful facts from analysis (differentiable functions, gradients, Hessian matrices, convex functions)
[*]necessary and sufficient conditions of extremum
[*]unconstrained optimization problem: existence, uniqueness, and stability of solution, gradient descent in convex optimization, its convergence and convergence rate
[*]Karush-Kuhn-Tucker condition
[*]optimization subjected to convex simple constraints, gradient projection method and its convergence properties
[*]optimization subjected to inequality constraints, primal-dual approach, Lagrangian, Arrow-Hurwicz-Uzawa iterative procedure
[/list]
[b]Part II: Optimization in multi-agent systems: Distributed (cooperative) optimization[/b]
[list]
[*]consensus in multi-agent systems, motivating examples
[*]communication protocols: gossip, weight-balanced communication
[*]consensus algorithm and its convergence (with the proof for weight-balanced communication)
[*]distributed optimization problems in multi-agent systems, motivating examples
[*]gradient-based procedure with weight-balanced communication and its convergence
[*]constrained distributed optimization (motivating examples, projected gradient-based procedure with weight-balanced communication and its convergence, discussion on the primal-dual approach)
[*]state of the art (convergence rate discussion, unbalanced communication, modern applications and their challenges)
[/list]
[b]Part III: Optimization in multi-agent systems: Game-theoretic (non-cooperative) optimization[/b]
[list]
[*]general game formulation, examples
[*]Nash equilibrium concept
[*]discrete action games, existence of a mixed-strategy Nash equilibrium
[*]continuous action games (continuous action games with convex cost functions, examples)
[*]variational inequalities, game mappings, and their connection to Nash equilibria problems in convex games
[*]existence and uniqueness of Nash equilibrium in convex games
[*]gradient methods in convex games (convergence in the case of games with strongly monotone mappings, non-convergence in the case of games with purely monotone mappings, regularized algorithms and their convergence)
[*]state of the art (convergence rate discussion, information settings in the system: communication- and payoff-based methods, modern applications and their challenges)
[/list]
Literature
[list=1]
[*]Nedic and A. Ozdaglar "Cooperative Distributed Multi-Agent Optimization" in the book "Convex Optimization in Signal Processing and Communications" by Y. Eldar and D. Palomar
[*]F. Facchinei J.-S. Pang "Finite-Dimensional Variational Inequalities and Complementarity Problems"
[/list]
Voraussetzungen
Mathematics I, II, III
[b]Part I: Classical theory of unconstrained and constrained optimization:[/b]
[list]
[*]useful facts from analysis (differentiable functions, gradients, Hessian matrices, convex functions)
[*]necessary and sufficient conditions of extremum
[*]unconstrained optimization problem: existence, uniqueness, and stability of solution, gradient descent in convex optimization, its convergence and convergence rate
[*]Karush-Kuhn-Tucker condition
[*]optimization subjected to convex simple constraints, gradient projection method and its convergence properties
[*]optimization subjected to inequality constraints, primal-dual approach, Lagrangian, Arrow-Hurwicz-Uzawa iterative procedure
[/list]
[b]Part II: Optimization in multi-agent systems: Distributed (cooperative) optimization[/b]
[list]
[*]consensus in multi-agent systems, motivating examples
[*]communication protocols: gossip, weight-balanced communication
[*]consensus algorithm and its convergence (with the proof for weight-balanced communication)
[*]distributed optimization problems in multi-agent systems, motivating examples
[*]gradient-based procedure with weight-balanced communication and its convergence
[*]constrained distributed optimization (motivating examples, projected gradient-based procedure with weight-balanced communication and its convergence, discussion on the primal-dual approach)
[*]state of the art (convergence rate discussion, unbalanced communication, modern applications and their challenges)
[/list]
[b]Part III: Optimization in multi-agent systems: Game-theoretic (non-cooperative) optimization[/b]
[list]
[*]general game formulation, examples
[*]Nash equilibrium concept
[*]discrete action games, existence of a mixed-strategy Nash equilibrium
[*]continuous action games (continuous action games with convex cost functions, examples)
[*]variational inequalities, game mappings, and their connection to Nash equilibria problems in convex games
[*]existence and uniqueness of Nash equilibrium in convex games
[*]gradient methods in convex games (convergence in the case of games with strongly monotone mappings, non-convergence in the case of games with purely monotone mappings, regularized algorithms and their convergence)
[*]state of the art (convergence rate discussion, information settings in the system: communication- and payoff-based methods, modern applications and their challenges)
[/list]
Literature
[list=1]
[*]Nedic and A. Ozdaglar "Cooperative Distributed Multi-Agent Optimization" in the book "Convex Optimization in Signal Processing and Communications" by Y. Eldar and D. Palomar
[*]F. Facchinei J.-S. Pang "Finite-Dimensional Variational Inequalities and Complementarity Problems"
[/list]
Voraussetzungen
Mathematics I, II, III
- Lehrende: Jürgen Adamy
- Lehrende: Tatiana Tatarenko
Semester: Verão 2022