Elementi introduttivi. Generalita’ sui problemi di ottimizzazione. Richiami sugli insiemi convessi e sull’Algebra Lineare Numerica: fattorizzazione LU di una matrice, pivoting, fattorizzazione LDL^T per matrici simmetriche e definite positive. Cenni sul linguaggio MATLAB.

Problemi di Programmazione Lineare. Forma standard di un problema di programmazione lineare. Il teorema fondamentale della programmazione lineare. Il metodo del simplesso standard. Trattamento di soluzioni basiche degeneri. Il metodo del simplesso a due fasi. Variabili con limite superiore. Forma matriciale del metodo del simplesso. Il metodo del simplesso rivisto, forma prodotta e reinversione. Metodo del simplesso e fattorizzazione LU. Il metodo di decomposizione di Dantzig-Wolfe. Problema duale di un problema PL e teorema della dualita’. Moltiplicatori del simplesso ed utilizzo della teoria della dualita’ in teoria dei giochi. Stabilita’ della soluzione di un problema PL. Proprieta’ di scarto complementare. Il metodo del simplesso duale. Il metodo primale-duale del simplesso.

Problemi di ottimizzazione su grafo. Il problema del trasporto bilanciato: l’algoritmo del Nord-Ovest per il calcolo di una soluzione basica accettabile, triangolarita’ delle basi, interezza delle soluzioni. L’algoritmo del trasporto: degenerazione e problema delle assegnazioni. Problemi di flusso su rete: il problema del flusso del minimo costo. Il metodo del simplesso rivisto per problemi di flusso di minimo costo. Procedura ad albero. Problema del massimo flusso. Il metodo primale-duale per il problema del trasporto: algoritmo e forma matriciale. Il metodo ungherese per il problema delle assegnazioni.

Problemi di ottimo non vincolato. Condizioni necessarie e/o sufficienti per un punto di minimo. Funzioni convesse. Algoritmi iterativi di discesa. Teorema di convergenza globale. Velocita' di convergenza. Metodi line-search: generalita', il metodo di Fibonacci, il metodo della sezione aurea, il metodo di Newton, il metodo della falsa posizione, fit quadratico e fit cubico. Criteri di arresto per algoritmi line-search. Il metodo del Gradiente. Il metodo di Newton e sue varianti. Il metodo delle direzioni coniugate ed il metodo del Gradiente Coniugato, estensioni al caso non quadratico. Metodi quasi-Newtoniani: modifica di rango 1, il metodo di Davidon-Fletcher e Powell, metodi della famiglia di Broyden, varianti. Cenni sui metodi "trust region": punto di Cauchy e metodo "dogleg". Applicazioni: il problema lineare dei minimi quadrati; metodo di Gauss-Newton e tipo Levemberg-Marquardt.

Problemi di ottimo vincolato (cenni). Generalita', vincoli attivi, condizioni necessarie del primo e secondo ordine. Condizioni sufficienti del secondo ordine. Esempi. Condizionamento del problema. Caso dei vincoli con diseguaglianza: Teorema di Kuhn-Tucker; condizioni del secondo ordine. Cenni sui metodi di penalita' e con barriera, esempio.

Testo consigliato: D.G.Luenberger, Linear and nonlinear programming, Addison Wesley, 1984.