View syllabus
OPTIMIZATION METHODS AND GAME THEORY
GIANDOMENICO MASTROENI
Academic year2023/24
CourseARTIFICIAL INTELLIGENCE AND DATA ENGINEERING
Code696AA
Credits6
PeriodSemester 1
LanguageEnglish

ModulesAreaTypeHoursTeacher(s)
OPTIMIZATION METHODS AND GAME THEORYMAT/09LEZIONI60
GIANDOMENICO MASTROENI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Lo studente che parteciperà al corso sarà in grado di dimostrare una solida conoscenza delle metodologie e degli algoritmi relativi alla soluzione di problemi avanzati di ottimizzazione non lineare e di teoria dei giochi. Inoltre, acquisirà abilità nell'uso di MATLAB per risolvere problemi di ottimizzazione non lineare e di teoria dei giochi.

Knowledge

The student who successfully completes the course will be able to demonstrate a solid knowledge of the methodologies and algorithms concerning solution of advanced nonlinear optimization and game theory problems. He/she will acquire ability in the use of MATLAB for solving nonlinear optimization and game theory problems.

Modalità di verifica delle conoscenze

La verifica delle conoscenze sarà oggetto della valutazione della prova scritta e dell'eventuale colloquio orale previsto per ogni sessione d'esame.

Assessment criteria of knowledge

The examination of knowledge will be the subject of an assessment of the written examination script and the optional oral interview scheduled for each examination session.

Capacità

Al termine del corso lo studente sarà in grado di utilizzare il software MATLAB per risolvere problemi di ottimizzazione e di teoria dei giochi.

Skills

At the end of the course the student will be able to use the MATLAB software for solving optimization and game theory problems.

Modalità di verifica delle capacità

Durante le sessioni di laboratorio, verranno effettuati esercizi per comprendere l'uso del software MATLAB per risolvere problemi di ottimizzazione e di teoria dei giochi. L'esame scritto, che si svolge in un'aula PC, consiste nel risolvere problemi di ottimizzazione e di teoria dei giochi utilizzando il software MATLAB.

Assessment criteria of skills

During the computer laboratory sessions, exercises will be carried out to understand the use of MATLAB software for solving optimization and equilibrium problems. The written test, which takes place in a PC room, consists in solving optimization and game theory problems using the MATLAB software. 

Comportamenti

Gli studenti potranno acquisire le capacità di formulare, analizzare e risolvere problemi di ottimizzazione e di teoria dei giochi.

Behaviors

Students can acquire the ability to formulate, analyse and solve optimization and game theory problems.

Modalità di verifica dei comportamenti

Durante le sessioni di laboratorio e l'esame scritto, verrà valutata la capacità dello studente di analizzare e risolvere un problema di ottimizzazione o di teoria dei giochi.

Assessment criteria of behaviors

During the laboratory sessions and the written exam, the ability of the student to analyze and solve an optimization or game theory problem will be evaluated.

Prerequisiti (conoscenze iniziali)

Concetti di base di algebra lineare e calcolo differenziale.

Prerequisites

Fundamentals of Linear algebra and Calculus.

Teaching methods

Delivery: Frontal lessons, with the help of transparencies, laboratory exercises using computer classroom PCs or students' personal PCs.

Course elearning site: download teaching materials, publication of tests for home exercises.

Learning activities:

  • attending lectures
  • individual study

Attendance: Advised

Programma (contenuti dell'insegnamento)

Ottimizzazione nonlineare: esistenza e unicità delle soluzioni ottime, condizioni di ottimalità,dualità metodi del gradiente,  metodi di Newton, metodi active set e di penalizzazione penalization methods. Support Vector Machines per la classificazione e problemi di regressione classification. Clustering problems: algoritmi k-means and k-median.

Ottimizzazione multiobbiettivo: soluzioni ottime di  Pareto, esistenza delle soluzioni ottime, condizioni di ottimalità, metodi di scalarizzazione  optimal solutions, , goal method.

Teoria dei giochi non-cooperativi:   equilibrio di Nash, giochi matriciali, strategie pure e miste, esistenza dei punti di equilibrio, giochi bimatriciali, giochi con infinite strateglie, funzioni di merito  functions.

Syllabus

Nonlinear optimization: existence and uniqueness of optimal solutions, optimality conditions, duality, gradient methods, Newton and quasi-Newton methods, active-set method, penalization methods, barrier methods. Support Vector Machines for classification and regression problems. Clustering problems: k-means and k-median algorithms.

Multiobjective optimization: Pareto optimal solutions, existence of optimal soluitons, optimality conditions, scalarization approach, goal method.

Non-cooperative game theory: Nash equilibrium, matrix games, pure and mixed strategies, existence of equilibria, bimatrix games, games with infinite strategies, merit functions.

Bibliografia e materiale didattico

Piattaforma Microsoft Teams del corso

Bibliography

Lecture notes are available online. Recommended reading includes the following works:

  • S. Boyd and L. Vandenberghe, Convex optimization, Cambridge University Press, 2004.
  • M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley-Interscience, 2006.
  • J. Nocedal, S. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2006
  • A.R. Conn, K. Scheinberg, L.N. Vicente, Introduction to Derivative-Free Optimization, SIAM series on Optimization, 2009
  • D.T. Luc, Theory of Vector Optimization, Springer, 1989
  • Y. Sawaragi, H. Nakayama, T. Tanino, Theory of Multiobjective Optimization, Academic Press, 1985
  • M.J. Osborne, A. Rubinstein, A Course in Game Theory, MIT press, 1994
  • N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007 
Modalità d'esame

Prova scritta in laboratorio ed esame orale

Assessment methods

The exam is made up of one written test and an oral test.

The written test consists in solving optimization and game theory problems, takes place in a PC room, has a duration of 3 hours, if passed it remains valid until the end of the same exam session.

The  oral test consists of an interview between the candidate and the teacher. During the oral test the candidate may be asked to resolve written exercises.

Altri riferimenti web

https://commalab.di.unipi.it

 

Updated: 21/10/2023 08:56