• Averaging Scheme
• Averaging Scheme
• composite optimization.
• constrained optimization
• convex-concave function
• EG method
• funzione convessa-concava
• Metodo del Gradiente Proiettato
• metodo EG
• metodo OGDA
• OGDA method
• ottimizzazione composta
• ottimizzazione vincolata
• Projected Gradient Method
• punto di sella
• saddle point

La tesi tratta il problema della ricerca di punti di sella vincolati di una funzione convessa-concava. Assumendo la convessità e la chiusura del vincolo, vengono presentati e analizzati alcuni metodi iterativi per l'approssimazione delle soluzioni ottime di tale problema di ottimizzazione, al variare delle ipotesi sulla regolarità e la struttura della funzione coinvolta.
Nella prima parte vengono passati in rassegna alcuni dei principali algoritmi, facendo attenzione alla rigidità delle ipotesi necessarie alla loro convergenza.
Successivamente viene presentata la tecnica dell'Averaging Scheme, la quale permette un netto miglioramento delle performance asintotiche dei metodi.
La terza parte del lavoro analizza le proprietà di convergenza del Metodo OGDA (Optimistic Gradient Descent Ascent) e del Metodo EG (ExtraGradient) nel caso in cui la funzione convessa-concava coinvolta sia composta da un addendo sufficientemente regolare e da uno non differenziabile. Lo studio si sviluppa interpretando tali algoritmi come opportune approssimazioni di un metodo iterativo implicito (Metodo Proximal Point), per il quale si ha un risultato di convergenza con velocità O(1/k).

English:
The thesis deals with the problem of finding saddle points for a constrained convex-concave function. Considering a closed and convex constraint, some iterative methods for the approximation of the optimal solutions of this optimization problem are presented and analyzed, varying the regularity and structural assumptions of the function involved.
The first part is a review of some of the main algorithms, paying attention to the rigidity of the hypotheses necessary for their convergence.
Then the Averaging Scheme technique is presented, which allows a strong improvement of the asymptotic performance of the methods.
The third part of the work analyzes the convergence properties of the OGDA Method (Optimistic Gradient Descent Ascent) and the EG Method (ExtraGradient) for a convex-concave function composed by a smooth term and a non-differentiable one. The study develops interpreting these algorithms as explicit approximations of an implicit iterative method (Proximal Point Method) for which there is a convergence result with rate O(1/k).