📈Optimization

This is also known as Lagrange Optimization or undetermined multipliers. Some of these notes are based on Appendix E of (Bishop 2006), others were found when studying bits of rational mechanics. Also (Boyd & Vandenberghe 2004) chapter 5 should be a good resource on this topic. $$ \begin{array} \\ \min f_{0}(x) \\ \text{subject to } f_{i}(x) \leq 0 \\ h_{j}(x) = 0 \end{array} $$Lagrangian function $$ \mathcal{L}(x, \lambda, \nu) = f_{0}(x) + \sum \lambda_{i}f_{i}(x) + \sum\nu_{j}h_{j}(x) $$ We want to say something about this function, because it is able to simplify the optimization problem a lot, but first we want to study this mathematically. ...

I problem idi accoppiamento sono abbastanza comuni per ottimizzazione a grafi. In questa serie di note andiamo a trattare brevemente i problemi principali, con un accenno veloce ad alcuni algoritmi di soluzione per esse. Grafo bipartito🟩 Un grafo bipartito è un insieme $(O \cup D), (A)$ di nodi e di archi. Tutti i nodi sono o fra i nodi di origine oppure fra i nodi di destinazione, e gli archi sono solamente collegati fra nodi di origine e nodi di destinazione. ...

Questi problemi sono una sottoclasse della programmazione lineare con variabili reali. (Alcuni riescono a riconoscere se un problema è in questa forma, e lo risolvono in modo istantaneo se questo succede). Un problema dei router è un classico problema di flusso, che si risolvono con questi algoritmi polinomiali Note introduttive Rete, terminologia In questo caso andiamo ad indicare con rete un grafo con $G = (N, A)$ con $N$ nodi e $A$ archi, che solitamente sono diretti con pesi associati. Possiamo interpretare gli archi come canali in cui fluiranno un qualcosa (ad esempio acqua in un tubo). Questi possono essere discreti o continui (mi sembra di ricordare che il discreto stranamente è più facile del continuo, non so se vale anche in questo caso). Abbiamo poi i nodi che sono punti di ingresso e uscita della nostra rete. ...

Questa sezione la tengo separata rispetto agli altri per favorire lo studio, così questa roba nuova la ripasso più spesso, in seguito si può accorpare. Goldberg Tarjan/Push-relabel Questo algoritmo è importante perché introduce ragionamenti sul minimo locale che possa alla fine essere ricomposto come soluzione globale. Questa lezione youtube lo spiega da Dio Preflusso 🟩 Slide La parte nuova di questa cosa è che i vincoli di bilanciamento possono diventare una disuguaglianza. (cioè quello che arriva è di più rispetto quanto va fuori. ...

Vogliamo cercare di restare nel nostro spazio delle soluzioni ammissibili, senza dover stare ad esplorare tutto, vogliamo andare a concentrarci su una parte specifica di essa. Vogliamo utilizzare una struttura fondamentale per i problemi di programmazione lineare, che è quello con cui vogliamo andare a fare. Il fatto è che spostandoci leggermente da un punto tra le soluzioni, possiamo gestire in modo molto semplice il modo con cui si sposta la retta dei valori. ...

È una branca dell’algebra lineare che ci permette di semplificare tutti i concetti. Intro dualità🟩 <img src="/images/notes/image/universita/ex-notion/Programmazione lineare/Untitled 8.png" style="width: 100%" class="center" alt="image/universita/ex-notion/Programmazione lineare/Untitled 8"> Si fa una sorta di trasposta alla matrice di A. y è pari al numero di righe di A La trasformazione al duale è molto facile, ed è abbastanza intuitiva una volta che capiamo che vogliamo andare a fare l’upper bound. Dualità asimmetrica 🟥+ Teorema debole di dualità 🟩 Slide ...

L’ottimizzazione combinatoria è un altro nome per la ricerca operativa. È uno strumento utile a prendere le decisioni migliori, fatto sta che è anche molto utile al machine learning e si potrebbe dire che ne sia una base, questa è una cosa molto buona. Ricerca operativa Questo è un campo a forte impatto economico perché prova a minimizzare i costi e massimizzare i profitti. Steps 🟩, 🟨 Individuazione del problema (almeno riconoscere che ci sia un problema) Raccoglimento dei dati Modellizzazione del problema Ricerca di una soluzione Analisi dei risultati della soluzione La ricerca operativa si interessa principalmente degli step 3 e 4, nonostante gli steps non sempre vengono eseguiti in maniera lineare, ma c’è un ciclo di feedback a riguardo. ...

Programmazione lineare Programmazione lineare contiene alcuni algoritmi utili per risolvere certi problemi di ottimizzazione. Introduzione Andiamo in questa sezione a definire un problema di programmazione lineare Definizione 🟩- Variabili reali che saranno le variabili del nostro problema, sono in numero finito (eg. tutti in Rn) Funzione obiettivo che ci definisce il costo $f: \R^n \to \R$ Vincoli lineari che limitano il dominio delle variabili reali e li mettono in relazione fra di loro Se le variabili appartengono agli interi andiamo a parlare di programmazione lineare intera. ...

Algoritmo del simplesso Ricerca della direzione migliore Ricerca dello step Pseudocodice Slide B sono gli indici di partenza, poi questi vengono aggiornati In riga 5 vado a checkare se ho direzioni di crescita possibili, se è tutto positivo non ne ho. in riga 6, si sceglie il più piccol per evitare loop. L’idea in generale va in questo modo Cerco di trovare il duale e confrontarlo con la x attuale Se sono uguali, allora ho trovato l’ottimo ed esco Altrimenti cerco una direzione di crescita che sia anche ammissibile Continuo fino a trovare un vertice, se ho il vertice allora mi muovo lì e riapplico, altrimenti è illimitata, se non esiste un vertice. Correttezza Slide ...