📈Optimization

È 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" 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. ...

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. ...

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. ...

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. ...