Il corso classifica i modelli in LP, QP e NLP. Quale classe ha funzione obiettivo quadratica e solo vincoli lineari?
LP
NLP con vincoli conici
QP
LP stocastico
Spiegazione. QP (*Quadratic Programming*): obiettivo quadratico, vincoli lineari. Nell'LP tutto è lineare; nell'NLP obiettivo o vincoli sono funzioni non lineari generali.
Nella dispensa del corso un problema di ottimizzazione si dice *convesso* quando:
ogni minimo locale è anche un minimo globale
tutti i suoi vincoli sono funzioni lineari
la sua soluzione ottima è unica
il suo obiettivo è derivabile ovunque
Spiegazione. È la definizione operativa della dispensa: per gli LP vale sempre, per QP e NLP dipende dalle funzioni. Linearità, unicità e derivabilità sono proprietà diverse.
Il corso classifica i modelli in LP (tutto lineare), QP (obiettivo quadratico, vincoli lineari) e NLP (obiettivo o vincoli non lineari generali). Un modello con obiettivo lineare e il vincolo $x_1^2 + x_2^2 \le d^2$ è:
un LP, perché l'obiettivo è lineare
un QP, perché contiene termini quadratici
un NLP, perché un vincolo è non lineare
non classificabile in queste tre classi
Spiegazione. Un QP richiede vincoli lineari; un vincolo quadratico rende il modello un NLP (qui convesso, come i vincoli conici del capitolo sulla localizzazione).
Il corso trasforma problemi gestionali in modelli di ottimizzazione continua e li risolve con Gurobi. Secondo la dispensa, qual è la domanda giusta alla fine di ogni esercitazione?
Qual è il valore ottimo del modello?
Quale solver trova l'ottimo più in fretta?
Quale decisione suggeriamo, e quanto è robusta?
Quante variabili e vincoli ha il modello?
Spiegazione. Il valore di un modello sta nella qualità della raccomandazione che permette di formulare: l'ottimo è il punto di partenza, non la risposta.
Nel corso un modello risolto non si legge soltanto: lo si *interroga*. Quale di queste è un esempio di interrogazione di un piano di produzione?
Quanto vale un'ora di capacità in più?
Quante iterazioni del simplesso sono servite a Gurobi?
Quale versione di Python ha eseguito lo script?
Quante cifre decimali stampa il solver?
Spiegazione. Interrogare vuol dire porre domande economiche alla soluzione: il valore di una risorsa (prezzi ombra), la robustezza ai cambi dei dati, i compromessi da consigliare.
Il corso usa la programmazione matematica come strumento di *decisione*. Secondo la dispensa, in che cosa sta il valore di un modello?
Nella precisione del valore ottimo che calcola
Nella velocità del solver che lo risolve
Nella qualità della raccomandazione che permette
Nel numero di vincoli che riesce a gestire
Spiegazione. La dispensa lo dice esplicitamente: il valore di un modello sta nella qualità della raccomandazione che permette di formulare; il valore ottimo è solo il punto di partenza.
Dopo aver risolto un modello del corso lo si *interroga* con tre tipi di domande: valore marginale, robustezza, compromesso. Quale domanda riguarda la **robustezza**?
La soluzione resiste se i dati cambiano del 5%?
Quanto vale un'ora di capacità in più?
Quale compromesso consiglieremmo al decisore?
Qual è il valore ottimo dell'obiettivo?
Spiegazione. La robustezza chiede se la raccomandazione sopravvive a una perturbazione dei dati. Un'ora di capacità in più è un valore marginale (un prezzo ombra), il compromesso è un trade-off, il valore ottimo non è un'interrogazione.
Il corso classifica i modelli in LP (tutto lineare), QP (obiettivo quadratico, vincoli lineari) e NLP (funzioni non lineari generali). Per quale classe la dispensa dice che la convessità (ogni minimo locale è globale) vale **sempre**?
QP
NLP
Nessuna: va sempre verificata
LP
Spiegazione. Per gli LP la convessità vale sempre; per QP e NLP dipende dalle funzioni (per un QP, dalla matrice $\mathbf Q$), e la dispensa lo segnala capitolo per capitolo.
Nella mappa dei modelli di Modellazione PNL, a quale classe appartiene la regressione ai minimi quadrati?
NLP non convesso
QP convesso
LP a scenari
NLP convesso con vincoli conici
Spiegazione. La somma dei quadrati dei residui è una funzione quadratica convessa e i vincoli che definiscono i residui sono lineari: è un QP convesso.
Tre capitoli di Modellazione PNL (produzione, ricarica EV, minimi quadrati) sono varianti di casi trattati in Modellazione PL. Che cosa cambia rispetto al caso lineare?
I dati, che vengono generati di nuovo
Le variabili, che diventano intere
I vincoli, che diventano quadratici
L'obiettivo, con un termine quadratico
Spiegazione. Dati, variabili e vincoli restano quelli del caso lineare: cambia l'obiettivo, a cui si aggiunge (o in cui si sostituisce) un termine quadratico convesso.
Nella mappa dei modelli di Modellazione PNL, quale applicazione è un NLP non convesso?
Il pricing con domanda dipendente dal prezzo
Il portafoglio di Markowitz con tetti sulle quote
La localizzazione di Weber con vincoli conici
La SVM soft margin con kernel lineare
Spiegazione. Nel pricing il ricavo $p \cdot q$ è bilineare e il modello non è convesso; Markowitz e la SVM sono QP convessi, Weber è un NLP convesso con vincoli conici.
Il percorso essenziale di Modellazione PNL ha quattro laboratori. Che cosa tratta il primo?
La produzione con smoothing quadratico
Il pricing o il budget pubblicitario
Il portafoglio di Markowitz
Un progetto a scelta
Spiegazione. Il primo laboratorio è Markowitz (QP convesso e frontiera), il secondo la produzione con smoothing, il terzo pricing o budget, il quarto un progetto.
Nel secondo laboratorio di Modellazione PNL (produzione con smoothing) quale obiettivo di apprendimento è centrale?
Formulare un LP multiperiodale da zero
Leggere e verificare i moltiplicatori di un QP
Stimare una regressione quantile
Usare variabili binarie per i cambi di ritmo
Spiegazione. Il laboratorio aggiunge un termine quadratico a un modello lineare noto e insegna a leggere i moltiplicatori del QP e a verificarli per perturbazione.
Modellazione PNL presuppone un altro corso della collana per notazione, comandi generali del solver e protocollo di sensitività. Quale?
Modellazione PL
Modellazione MIP
Algoritmi euristici
Programmazione dinamica
Spiegazione. Il corso segue Modellazione PL, da cui riprende notazione, comandi generali di Gurobi e protocollo di sensitività; Ottimizzazione convessa fornisce le nozioni di convessità.
Un modello ha obiettivo lineare e il vincolo $x_1^2 + x_2^2 \le d^2$. Sotto quale ipotesi su $d$ il problema è convesso?
Solo per $d$ intero, come i dati di conteggio
Solo per $d > 1$, perché il disco non degeneri
Per ogni $d$: $x_1^2 + x_2^2 \le d^2$ è un disco
Mai: un vincolo quadratico non è mai convesso
Spiegazione. Il vincolo descrive un disco (vuoto o un punto per $d = 0$), che è convesso; con obiettivo lineare il problema è convesso: un NLP convesso, non un QP.
Un QP ha obiettivo $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ con $\mathbf Q \succeq 0$ e vincoli lineari. Che cosa si può dire di un punto che soddisfa le condizioni KKT?
È soltanto un punto stazionario, forse una sella
È un ottimo globale
È un ottimo locale ma non necessariamente globale
È ammissibile ma non ottimo
Spiegazione. Con $\mathbf Q \succeq 0$ il QP è convesso: le KKT sono anche sufficienti e ogni punto KKT è un ottimo globale.
Un vincolo di uguaglianza $h(\mathbf x) = 0$ compare in un modello. Sotto quale ipotesi su $h$ l'insieme che definisce è sicuramente convesso?
$h$ convessa in tutte le variabili
$h$ derivabile con continuità
$h$ quadratica con matrice $\succeq 0$
$h$ affine (lineare più una costante)
Spiegazione. Una uguaglianza con una funzione non lineare, per esempio $x_1 x_2 = 1$, definisce in generale un insieme non convesso; con $h$ affine l'insieme è un iperpiano.
Problema $\min f(x)$ soggetto a $g_i(x) \le 0$ e $h_k(x) = 0$, con funzioni derivabili. Quale affermazione sulle condizioni KKT è corretta?
Ogni punto che le soddisfa è un ottimo globale, qualunque siano $f$, $g_i$ e $h_k$
Valgono in ogni ottimo locale regolare e, con la convessità, sono anche sufficienti
Sono necessarie e sufficienti non appena tutti i vincoli sono lineari
Garantiscono l'ottimalità globale se tutti i moltiplicatori sono strettamente positivi
Spiegazione. Le KKT sono necessarie negli ottimi regolari e diventano sufficienti quando il problema è convesso. Vincoli lineari non rendono innocua una $f$ non convessa. Per un LP si riducono agli scarti complementari.
Un QP ha obiettivo $\tfrac12 \sum_{i}\sum_{j} q_{ij} x_i x_j + \sum_j c_j x_j$ (da minimizzare) e vincoli lineari. È convesso:
se e solo se la matrice $Q = (q_{ij})$ è semidefinita positiva
sempre, perché i suoi vincoli sono lineari
se e solo se tutti gli elementi $q_{ij}$ sono non negativi
se e solo se $Q$ è diagonale con elementi positivi
Spiegazione. La regione ammissibile è un poliedro (convesso); l'obiettivo quadratico è convesso esattamente quando $Q \succeq 0$. Elementi non negativi non sono né necessari né sufficienti, e la diagonale è solo un caso particolare.
Un punto soddisfa le KKT di $\min f(x)$ soggetto a $g_i(x) \le 0$, $h_k(x) = 0$ (moltiplicatori $\lambda_i \ge 0$ per le $g_i$). Che cosa serve per concludere che è un ottimo **globale**?
Il problema deve essere convesso: $f$ e le $g_i$ convesse, le $h_k$ affini
Tutti i vincoli di disuguaglianza $g_i$ devono essere attivi nel punto
Tutti i moltiplicatori $\lambda_i$ devono essere strettamente positivi
Basta che $f$ sia derivabile nel punto
Spiegazione. La convessità rende sufficienti le KKT. Vincoli attivi o moltiplicatori positivi non garantiscono la globalità in un problema non convesso.
QP convesso: $\min x_1^2 + 2x_2^2$ soggetto a $x_1 + x_2 \ge 6$, $x_1, x_2 \ge 0$. All'ottimo il vincolo è attivo e le derivate parziali sono uguali al suo moltiplicatore $\lambda$: $2x_1 = 4x_2 = \lambda$. Quanto valgono $\tilde x$, il valore ottimo e $\lambda$?
$\tilde x = (3, 3)$, valore $27$, $\lambda = 6$
$\tilde x = (4, 2)$, valore $24$, $\lambda = 8$
$\tilde x = (2, 4)$, valore $36$, $\lambda = 16$
$\tilde x = (6, 0)$, valore $36$, $\lambda = 12$
Spiegazione. $x_1 = 2x_2$ e $x_1 + x_2 = 6$ danno $(4, 2)$, valore $16 + 8 = 24$, $\lambda = 8$. Per perturbazione, con termine noto 7 il valore diventa $32{,}67 \approx 24 + 8$.
Per quali valori del parametro $\gamma$ la funzione $f(x_1, x_2) = x_1^2 + \gamma x_1x_2 + x_2^2$ è convessa? (Una funzione quadratica $\tfrac12\mathbf x'\mathbf Q\mathbf x$ è convessa se e solo se $\mathbf Q \succeq 0$.)
Per ogni $\gamma \ge 0$
Per $|\gamma| \le 1$
Per $|\gamma| \le 2$
Per ogni $\gamma$ reale
Spiegazione. Qui $\mathbf Q = \begin{pmatrix} 2 & \gamma \\ \gamma & 2 \end{pmatrix}$: elementi diagonali positivi e $\det\mathbf Q = 4 - \gamma^2 \ge 0$, cioè $|\gamma| \le 2$. Dimenticare il fattore $\tfrac12$ porta a $|\gamma| \le 1$.
QP convesso $\min\ x_1^2 + 2x_2^2$ soggetto a $x_1 + x_2 \ge d$, $x \ge 0$: con $d = 6$ il valore ottimo è $24$ e il moltiplicatore $\lambda = 8$. Con $d = 7$ il valore ottimo è $32{,}67$, non $24 + 8 = 32$. Perché?
Il moltiplicatore è esatto solo al margine (curvatura)
Il solver usa una tolleranza di ammissibilità troppo larga
Con $d = 7$ il vincolo non è più attivo
Il moltiplicatore di un QP non è mai un valore marginale
Spiegazione. Qui $\tilde f(d) = \tfrac23 d^2$, quindi $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: il moltiplicatore dà il termine del primo ordine, e il termine quadratico della curvatura aggiunge $0{,}67$ per $\varepsilon = 1$.
Condizioni KKT per $\min f(\mathbf x)$ soggetto a $g_i(\mathbf x) \le 0$ ($i = 1, \dots, m$) e $h_j(\mathbf x) = 0$ ($j = 1, \dots, q$). Come si scrive la Lagrangiana nella dispensa?
$f - \sum_i\lambda_ig_i - \sum_j\nu_jh_j$, con $\lambda_i \le 0$
$f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, con $\nu_j \ge 0$ e $\lambda_i$ libere
$\sum_i\lambda_ig_i + \sum_j\nu_jh_j$, con $\lambda_i \ge 0$
$f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, con $\lambda_i \ge 0$
Spiegazione. $L = f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$: i moltiplicatori delle disuguaglianze $g_i \le 0$ sono non negativi, quelli delle uguaglianze liberi. La stazionarietà chiede $\partial L/\partial x_k = 0$, la complementarietà $\lambda_ig_i = 0$.
Che cosa diventano le condizioni KKT applicate a un LP (scritto come $\min$ con vincoli $g_i \le 0$)?
Perdono senso, perché un LP non ha derivate
Esattamente gli scarti complementari, con l'ammissibilità duale
Solo le condizioni di ammissibilità primale dell'LP
Condizioni più deboli, necessarie ma mai sufficienti
Spiegazione. Per un LP i moltiplicatori $\lambda_i$ sono i duali $\pi_i$, quelli dei vincoli di segno sono i costi ridotti; la stazionarietà è l'ammissibilità duale e la complementarietà sono gli scarti complementari. E poiché un LP è convesso, sono anche sufficienti.
Il teorema KKT della dispensa vale «in un punto di ottimo **regolare**». Che cosa può succedere in un ottimo dove l'ipotesi di regolarità non vale?
Il punto non può essere affatto un minimo locale
I moltiplicatori esistono ma sono tutti uguali a zero
Possono non esistere moltiplicatori KKT
Le condizioni diventano sufficienti senza convessità
Spiegazione. La regolarità (una qualificazione dei vincoli) è ciò che garantisce l'esistenza dei moltiplicatori: senza di essa un ottimo può non soddisfare la stazionarietà per nessuna scelta di $\lambda_i \ge 0$, $\nu_j$.
Per il problema $\min f(x)$ con vincoli $g_i(x) \le 0$, sotto quale ipotesi le condizioni KKT sono anche *sufficienti* per l'ottimo globale?
Che i vincoli siano tutti uguaglianze
Che il problema sia convesso: $f$ e le $g_i$ convesse
Che i moltiplicatori siano tutti positivi
Che il punto stia nell'interno della regione
Spiegazione. In un problema convesso un punto che soddisfa le KKT è un ottimo globale; senza convessità le KKT sono solo necessarie (in un punto regolare).
Nella Lagrangiana $L = f + \sum_i \lambda_i g_i$ per vincoli $g_i(x) \le 0$ di un problema di minimo, quale segno devono avere i moltiplicatori $\lambda_i$?
Qualunque segno
$\lambda_i \le 0$
$\lambda_i = 0$ per ogni vincolo attivo
$\lambda_i \ge 0$
Spiegazione. Per vincoli di disuguaglianza nella forma $g_i \le 0$ i moltiplicatori sono non negativi; solo quelli dei vincoli di uguaglianza $h_j = 0$ sono liberi.
QP con obiettivo $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ e vincoli lineari. Quale ipotesi su $\mathbf Q$ rende il QP convesso?
Qualunque segno, a seconda del vincolo
$\lambda_i \le 0$ per ogni vincolo
$\lambda_i = 0$ per ogni vincolo attivo
$\lambda_i \ge 0$
Spiegazione. Il QP è convesso se e solo se $\mathbf Q \succeq 0$; elementi non negativi o invertibilità non bastano (per esempio $q_{12}$ grande rompe la convessità).
Per un LP, a che cosa si riducono le condizioni KKT?
A una condizione sul gradiente dell'obiettivo soltanto
Alla sola ammissibilità primale
A nulla: le KKT non valgono per gli LP
All'ammissibilità duale e agli scarti complementari
Spiegazione. Per un LP la stazionarietà della Lagrangiana è l'ammissibilità del duale e la complementarietà è lo scarto complementare: le KKT generalizzano la teoria degli LP.
Nello stesso QP ($\min\ x_1^2 + 2x_2^2$, $x_1 + x_2 \ge 6$) perché all'ottimo le derivate parziali $2x_1$ e $4x_2$ sono uguali?
Perché la regione ammissibile è simmetrica rispetto alla bisettrice
Altrimenti converrebbe spostare quantità fra le variabili
Perché i due coefficienti dell'obiettivo sono uguali
Perché il vincolo di soglia non è attivo all'ottimo
Spiegazione. Se una derivata fosse minore, spostare un po' di quantità sulla variabile più economica al margine ridurrebbe l'obiettivo restando sul vincolo; la derivata comune è il moltiplicatore, $8$.
Con le KKT si risolve $\min\ (x-3)^2 + (y-1)^2$ con $x + 2y \le 2$, $x, y \ge 0$. Quale punto è ottimo?
$(3, 1)$, il centro delle curve di livello
$(0, 1)$, sul vincolo $x + 2y = 2$
$(1{,}6;\ 0{,}2)$, proiezione senza i limiti
$(2, 0)$, con $x + 2y \le 2$ e $y \ge 0$ attivi
Spiegazione. Il centro $(3, 1)$ non è ammissibile; con il solo vincolo $x + 2y \le 2$ attivo si avrebbe $y < 0$. Con anche $y \ge 0$ attivo: $(2, 0)$, moltiplicatori $\lambda = 2$ e $\mu = 2$, entrambi non negativi.
Nel QP $\min\ x_1^2 + 2x_2^2$ con $x_1 + x_2 \ge d$ il valore ottimo è $\tilde f(d) = \tfrac23 d^2$. Quanto vale il moltiplicatore del vincolo in $d = 6$?
$24$
$4$
$8$
$\tfrac23$
Spiegazione. Il moltiplicatore è la derivata del valore ottimo rispetto al termine noto: $\tilde f'(d) = \tfrac43 d = 8$ in $d = 6$, come $\lambda = 2\tilde x_1 = 4\tilde x_2$.
Si stima un moltiplicatore per perturbazione: $\tilde f(d + \varepsilon) \approx \tilde f(d) + \lambda\,\varepsilon$. Sotto quale ipotesi l'approssimazione è buona in un QP?
$\varepsilon$ piccolo: la curvatura è trascurabile
$\varepsilon$ grande: gli errori numerici pesano meno
Il vincolo perturbato non è attivo all'ottimo
Il QP non è convesso, così la stima è lineare
Spiegazione. Nel QP dell'esempio $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: il termine quadratico è trascurabile solo per $\varepsilon$ piccolo.
Un modello gurobipy contiene il prodotto $p \cdot q$ di due variabili decisionali (prezzo per quantità, un termine bilineare). Quale parametro va impostato perché Gurobi lo risolva?
`m.Params.NonConvex = 2`
`m.Params.FuncNonlinear = 1`
`m.Params.QCPDual = 1`
Nessuno: i termini bilineari sono convessi
Spiegazione. I termini bilineari (non convessi) richiedono `NonConvex = 2`; `FuncNonlinear = 1` serve per le funzioni generali introdotte con `addGenConstrLog/Exp/Pow`.
L'obiettivo di un modello gurobipy deve contenere $\log(1 + k x)$, con $x$ variabile decisionale e $k > 0$ un dato. Come si introduce questo termine?
Direttamente in `setObjective`, scrivendo `gp.log(1 + k*x)`
Con un'approssimazione lineare a tratti del logaritmo scritta a mano
Con variabili ausiliarie $g = 1 + kx$, $z$ e il vincolo `m.addGenConstrLog(g, z)`
Non si può: Gurobi accetta solo espressioni lineari e quadratiche
Spiegazione. Le funzioni non lineari entrano come vincoli funzionali su variabili ausiliarie; con `FuncNonlinear = 1` sono trattate in modo esatto e l'ottimo è certificato globale.
Per un modello gurobipy con vincoli funzionali (per esempio `addGenConstrLog`) il solver non restituisce i duali. Come si stima il moltiplicatore di un vincolo?
Si prende nullo, perché questi vincoli non hanno duale
Si alza il termine noto di $\varepsilon$, si riottimizza e si fa il rapporto incrementale
Dai costi ridotti `RC` delle variabili del vincolo
Dagli attributi `SARHSLow` e `SARHSUp` del vincolo
Spiegazione. La perturbazione è lo strumento generale del corso: nuovo ottimo $\approx$ vecchio ottimo $+$ moltiplicatore $\cdot\,\varepsilon$.
Il corso usa un solo solver, Gurobi, per tutti i modelli, compresi quelli non convessi (pricing). Perché?
Perché i solver locali sono più lenti sui problemi convessi, i più comuni
Perché certifica un ottimo globale anche nei modelli non convessi, con una sola sintassi
Perché Gurobi riformula ogni modello come un LP equivalente
Perché Gurobi restituisce i duali per ogni classe di modelli
Spiegazione. Con un solver locale ogni risultato porterebbe il dubbio «è solo un ottimo locale?». I duali non sono disponibili con vincoli funzionali o bilineari.
Un QP convesso (per esempio Markowitz) si risolve con gurobipy, e l'attributo `Pi` dei suoi vincoli lineari non è disponibile. Che cosa suggerisce il corso?
Dichiarare il modello con `NonConvex = 2`
Leggere `SARHSLow`/`SARHSUp` al posto di `Pi`
Impostare `m.Params.QCPDual = 1`, oppure verificare il moltiplicatore per perturbazione
Supporre nulli tutti i moltiplicatori
Spiegazione. Per i QP i duali non sono restituiti di default: `QCPDual = 1` li richiede, e perturbare il termine noto di $\varepsilon$ li verifica.
Gurobi tratta i modelli non lineari con parametri speciali: `NonConvex = 2` per i termini bilineari, `FuncNonlinear = 1` per funzioni come $\log$. Quale modello del corso non richiede né l'uno né l'altro, essendo puramente conico?
Il pricing, con il termine $p \cdot q$
Il budget pubblicitario, con $\log(1 + k_ix_i)$
La coda M/M/1, con il vincolo $w(\mu - \lambda) = 1$
La localizzazione di Weber, con $d_x^2 + d_y^2 \le d_i^2$
Spiegazione. Le strutture quadratiche o coniche convesse (un QCP convesso) non richiedono nulla di speciale; i termini bilineari richiedono `NonConvex = 2`, i vincoli funzionali `FuncNonlinear = 1`.
Un modello del corso contiene il tempo medio in una coda M/M/1, $w = 1/(\mu - \lambda)$, con la capacità $\mu$ variabile decisionale. Come si scrive per Gurobi?
Direttamente come `w == 1/(mu - lam)` in `addConstr`
Con `addGenConstrLog` applicato a $\mu - \lambda$
Con il vincolo bilineare $w(\mu - \lambda) = 1$
Fissando $\mu$ e risolvendo un LP per ogni valore di $\mu$
Spiegazione. I rapporti si riformulano con una variabile ausiliaria e un vincolo bilineare, `m.addQConstr(w * (mu - lam) == 1)`, che richiede `NonConvex = 2`; gurobipy non accetta una divisione per una variabile.
Uno script del corso stima differenze fra due valori ottimi vicini (un'analisi marginale). Quali parametri di Gurobi la dispensa stringe a $10^{-9}$?
`TimeLimit` e `OutputFlag`
`FeasibilityTol` e `OptimalityTol`
`NonConvex` e `FuncNonlinear`
`Threads` e `Seed` del solver
Spiegazione. Per analisi marginali accurate si stringono le tolleranze: `MIPGap`, `FeasibilityTol` e `OptimalityTol` a $10^{-9}$. Gli altri parametri controllano tempo, log e funzionalità non lineari.
Un modello di pricing con domanda a elasticità costante richiede il vincolo $q \le A\,p^{-\varepsilon}$ ($p$ prezzo, $q$ quantità, $\varepsilon > 1$), dove $p^{-\varepsilon}$ è minuscolo. Come lo riscrive la dispensa?
Come $q\cdot r \le A$ con un'ausiliaria $r = p^{\varepsilon}$
Come $\log q \le \log A + \varepsilon\log p$
Come $q \le A$, lasciando cadere il termine di prezzo
Come $q\,p \le A$, un vincolo bilineare
Spiegazione. Scalatura: con $r = p^{\varepsilon}$ (un vincolo di potenza) la condizione diventa $q\,r \le A$, che tiene i numeri in un range sano. La forma logaritmica ha il segno dell'esponente sbagliato.
Un moltiplicatore si stima per perturbazione: si alza il termine noto di $\varepsilon$, si risolve di nuovo e si divide per $\varepsilon$ la differenza dei due valori ottimi. Perché gli script del corso stringono per questo le tolleranze del solver a $10^{-9}$?
Perché altrimenti Gurobi rifiuta di risolvere due volte
Perché il moltiplicatore deve essere intero
Per rendere più veloci le due soluzioni
Altrimenti l'errore numerico domina la differenza
Spiegazione. Il rapporto incrementale divide una differenza piccola per un $\varepsilon$ piccolo: con le tolleranze predefinite (intorno a $10^{-6}$) il rumore numerico di ciascun ottimo può essere paragonabile alla differenza stessa.
Un modello con un vincolo funzionale (`addGenConstrLog`) non fornisce i duali. Il vincolo di budget passa da $100$ a $100{,}1$ e il valore ottimo da $500$ a $501{,}2$. Qual è la stima per perturbazione del suo moltiplicatore?
$1{,}2$
$12$
$0{,}12$
$120$
Spiegazione. Rapporto incrementale: $(501{,}2 - 500)/0{,}1 = 12$ per unità di termine noto. Dimenticare di dividere per $\varepsilon = 0{,}1$ dà $1{,}2$.
In un QP convesso con vincoli lineari risolto con gurobipy, dove si legge il moltiplicatore KKT di un vincolo lineare?
Nell'attributo `RC` della variabile
Non si legge: va sempre stimato per perturbazione
Nell'attributo `Pi` del vincolo
Nell'attributo `SARHSUp` del vincolo
Spiegazione. Nei QP convessi con vincoli lineari Gurobi restituisce i moltiplicatori come negli LP: l'attributo `Pi` di ogni vincolo è il moltiplicatore KKT.
QP $\min\ x_1^2 + 2x_2^2$ con $x_1 + x_2 \ge d$: il valore ottimo è $\tilde f(d) = \tfrac{2}{3}d^2$ e il moltiplicatore in $d = 6$ è $8$. Ri-ottimizzando con $d = 7$ il valore sale da $24$ a $32{,}67$, non a $32$. Perché?
Perché il moltiplicatore di un QP vale solo se il vincolo non è attivo
Perché Gurobi restituisce i moltiplicatori dei QP con un errore numerico
Perché con $d = 7$ il vincolo smette di essere attivo
Perché il valore ottimo ha curvatura: il moltiplicatore è esatto solo al margine
Spiegazione. $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac{2}{3}\varepsilon^2$: il moltiplicatore dà il termine lineare, la curvatura aggiunge $\tfrac23$ per $\varepsilon = 1$. Per questo la verifica si fa con un $\varepsilon$ piccolo.
Un modello gurobipy ha un termine bilineare $p \cdot q$ (prezzo per quantità). Che cosa serve perché Gurobi lo risolva all'ottimo globale?
Nulla: ogni termine quadratico è convesso
`m.Params.QCPDual = 1`
`m.Params.NonConvex = 2`
`m.Params.FuncNonlinear = 1` e un vincolo funzionale
Spiegazione. Un termine bilineare non è convesso; con `NonConvex = 2` Gurobi lo risolve con tecniche globali. `QCPDual` riguarda i duali, `FuncNonlinear` le funzioni come log ed exp.
Un modello contiene il vincolo funzionale $z = \log(1 + k x)$ scritto con `addGenConstrLog`. Si vuole il moltiplicatore del limite $x \le b$: come si ottiene?
Per perturbazione: $b$ un po' più alto, poi rapporto incrementale
Dall'attributo `Pi` del limite $x \le b$ all'ottimo
Dall'attributo `RC` della variabile ausiliaria $z$
Dall'attributo `QCPi` del vincolo funzionale
Spiegazione. Con vincoli funzionali il solver non fornisce i duali: il moltiplicatore si stima per perturbazione.
Si vogliono confrontare due ottimi molto vicini di un modello non lineare (per stimare un moltiplicatore per differenza). Quale accorgimento consiglia il corso?
Ridurre il numero di variabili ausiliarie del modello
Usare un solver locale più veloce di Gurobi
Arrotondare tutti i dati alla seconda cifra decimale
Stringere le tolleranze di Gurobi a $10^{-9}$
Spiegazione. Le differenze fra due ottimi vicini sono piccole: con le tolleranze standard l'errore numerico può superarle, quindi si stringono a $10^{-9}$.
Perché il corso usa un solo solver (Gurobi) anche per i problemi non convessi, invece di un solver locale?
Perché i solver locali non accettano vincoli lineari
Perché Gurobi certifica l'ottimo globale anche nei non convessi
Perché i problemi non convessi del corso sono in realtà lineari
Perché un solver locale non calcola i moltiplicatori
Spiegazione. Con un solver locale ogni risultato andrebbe accompagnato dalla domanda «è solo un ottimo locale?»; Gurobi dà un ottimo globale certificato con la stessa sintassi.
Perché conviene riscrivere $q \le A\,p^{-\varepsilon}$ come $q \cdot r \le A$ con $r = p^{\varepsilon}$?
Per rendere lineare il vincolo di domanda
Per evitare quantità minuscole e numeri mal scalati
Per eliminare del tutto la variabile prezzo $p$
Perché Gurobi non accetta esponenti negativi
Spiegazione. Con esponenti negativi compaiono numeri molto piccoli che peggiorano la scalatura; la riformulazione tiene i coefficienti in un range sano.
In un QP convesso con vincoli lineari `Pi` è il moltiplicatore KKT del vincolo. Per quali incrementi del termine noto la stima $\Delta f \approx \pi\,\Delta$ è esatta?
Solo al margine, per incrementi piccoli
Per ogni incremento, come succede negli LP
Dentro l'intervallo `SARHSLow`–`SARHSUp`
Per nessuno: nei QP `Pi` non ha significato
Spiegazione. A differenza degli LP, dove il valore ottimo è lineare a tratti, nei QP è curvo: il moltiplicatore è esatto solo al margine.
Si vuole il moltiplicatore di un vincolo *quadratico* (per esempio $d_x^2 + d_y^2 \le d^2$). Che cosa serve perché Gurobi lo restituisca?
Niente: basta leggere l'attributo `Pi`
Impostare `NonConvex = 2` prima di ottimizzare
`QCPDual = 1`, poi l'attributo `QCPi`
Riscriverlo come vincolo funzionale `addGenConstrPow`
Spiegazione. Per i vincoli quadratici i duali si chiedono con `QCPDual = 1` e si leggono in `QCPi`; altrimenti si stima il moltiplicatore per perturbazione.
Un modello contiene $z = \log(g)$ scritto con `addGenConstrLog`. Sotto quale impostazione Gurobi tratta la funzione in modo esatto, con ottimo globale?
`m.Params.MIPGap = 1`
`m.Params.FuncNonlinear = 1`
`m.Params.NonConvex = 0`
`m.Params.Method = 2`
Spiegazione. Con `FuncNonlinear = 1` le funzioni dei vincoli funzionali sono trattate in modo esatto e l'ottimo resta globale certificato.
Come vanno scelti gli iperparametri dei modelli del corso ($C$ e $\gamma$ della SVM, il peso $\lambda$ di un termine di rischio o di regolarizzazione)?
Su dati di validazione, mai sul test set o sugli scenari di decisione
Massimizzando l'accuratezza sull'insieme di test
Sempre pari a $1$, il valore neutro
Sugli stessi scenari usati poi per decidere
Spiegazione. Sceglierli sull'insieme di test (o sugli scenari di decisione) dà risultati ottimistici che non si trasferiscono a dati nuovi.
Un parametro stimato dai dati (per esempio un rendimento atteso) cambia alla seconda cifra decimale quando il campione cambia di poco. Quante cifre deve mostrare una relazione di laboratorio?
Sei, per essere il più precisi possibile
Poche: sei decimali di una stima che oscilla alla seconda ingannano
Nessuna: le stime non vanno riportate
Tutte quelle stampate dal solver
Spiegazione. La precisione fittizia è nella checklist degli errori: le cifre mostrate devono riflettere l'affidabilità della stima.
Nel percorso essenziale di Modellazione PNL, che cosa si fa nel quarto laboratorio?
Si formula da zero un LP multiperiodale
Si stima una regressione quantile sui dati
Si risolve un MIP con variabili binarie
Un progetto a scelta, presentato ai decisori
Spiegazione. Il quarto laboratorio è un progetto a scelta (supply chain, localizzazione, ricarica EV, code, SVM o minimi quadrati) con presentazione dei risultati.
Nel terzo laboratorio di Modellazione PNL (pricing oppure budget) quali sono gli obiettivi di apprendimento?
Funzioni non lineari, concavità e verifica delle KKT
Leggere i prezzi ombra e i costi ridotti di un LP
Tracciare la frontiera efficiente di Markowitz
Stimare i parametri di una SVM con kernel
Spiegazione. Pricing e budget hanno funzioni non lineari (ricavo bilineare, risposte concave): si studia la concavità e si verificano numericamente le KKT.
In un'edizione di Modellazione PNL orientata al machine learning, quali capitoli possono sostituire il terzo laboratorio?
Produzione con smoothing e ricarica EV
Pricing e budget pubblicitario
SVM e minimi quadrati
Supply chain e code
Spiegazione. I capitoli di ottimizzazione e machine learning (SVM e minimi quadrati) possono sostituire il laboratorio 3 o diventare progetti individuali.
Una voce della checklist degli errori è «credere convesso un problema che non lo è». Perché è grave?
Perché Gurobi rifiuta sempre i problemi non convessi
Perché i moltiplicatori diventano tutti nulli
Perché il modello diventa inammissibile
Perché si scambia un ottimo locale per globale
Spiegazione. Senza convessità un punto stazionario può essere solo un ottimo locale; dichiarare la non convessità (`NonConvex = 2`) fa cercare il globale.
Quali sono gli obiettivi di apprendimento del primo laboratorio (Markowitz)?
Scrivere un LP multiperiodale e leggerne i prezzi ombra
Usare variabili binarie per scegliere quali titoli tenere
Addestrare una SVM con il kernel RBF e scegliere $C$
Costruire un QP convesso, tracciare la frontiera, discutere le stime
Spiegazione. Il primo laboratorio costruisce il QP convesso di Markowitz, ne traccia la frontiera e discute quanto le stime dei rendimenti siano fragili.
Perché è un errore leggere `.X` o `.Pi` subito dopo `m.optimize()`, senza guardare `m.Status`?
Perché `.X` si legge solo prima di chiamare `m.optimize()`
Perché il modello può non avere un ottimo da leggere
Perché leggere `m.Status` cambia i valori delle variabili
Perché `.Pi` esiste soltanto nei modelli a variabili intere
Spiegazione. Prima si controlla che lo stato sia ottimo: se il modello è inammissibile, illimitato o interrotto non c'è una soluzione ottima da leggere.
Un problema ha due obiettivi in conflitto (rischio e rendimento). Che cosa consiglia la checklist invece di ottimizzarne uno solo?
Sommarli con pesi uguali e riportare un solo ottimo
Tenere soltanto l'obiettivo con il valore più grande
Trasformare entrambi in vincoli di uguaglianza
Studiare il compromesso, tracciando la frontiera
Spiegazione. Ottimizzare un solo obiettivo quando ce ne sono due è nella checklist degli errori: si studia il compromesso, come la frontiera di Markowitz.
In gurobipy il vincolo `x + 5 <= 10` viene salvato come $x \le 5$. Sotto quale condizione il valore assegnato a `c.RHS` è proprio il numero a destra del vincolo così come lo si è scritto?
Sempre: `RHS` è il numero scritto a destra del vincolo
Solo se il modello è convesso e senza termini bilineari
Solo dopo aver chiamato `m.update()` sul modello
Solo se il vincolo ha tutte le costanti a destra
Spiegazione. Le costanti a sinistra vengono spostate nel termine noto: qui `RHS` vale 5, non 10, e porlo a 12 dà $x \le 12$. È l'errore 5 della checklist.
LP di produzione e scorte a costo minimo (prodotti $i$, mesi $t$; $x_{it}$ = unità prodotte, $s_{it}$ = scorta a fine mese $t$, $d_{it}$ = domanda). Al costo minimizzato si aggiunge il termine $\gamma \sum_{t=2}^{m} (v_t - v_{t-1})^2$, con $\gamma > 0$ e $v_t = \sum_i x_{it}$ produzione totale del mese $t$. A che cosa serve?
A penalizzare la scorta tenuta a fine di ogni mese
A mantenere il problema un LP aggiungendo un costo
A livellare il piano, penalizzando i cambi di ritmo fra i mesi
A ridurre la domanda da servire nei mesi di picco
Spiegazione. È la variante QP: nel caso di studio, con $\gamma = 0{,}5$ il profilo diventa quasi piatto con un costo di appena lo $0{,}35\%$.
LP di produzione e scorte a costo minimo (prodotti $i$, mesi $t$; $x_{it}$ = unità prodotte, $s_{it}$ = scorta a fine mese $t$, $d_{it}$ = domanda). La variante di livellamento aggiunge al costo lineare $\gamma\sum_{t=2}^m (v_t - v_{t-1})^2$, con $v_t = \sum_i x_{it}$ e $\gamma > 0$. A quale classe appartiene il modello che si ottiene?
Un QP non convesso, per via dei quadrati
Un LP, perché i vincoli sono lineari
Un NLP non convesso che richiede `NonConvex = 2`
Un QP convesso: somma di quadrati con $\gamma > 0$ più termini lineari
Spiegazione. Ogni $(v_t - v_{t-1})^2$ è il quadrato di una funzione lineare, quindi convesso; con $\gamma > 0$ e vincoli lineari il modello è un QP convesso e il suo ottimo è globale.
Nel caso di produzione e scorte il piano lineare a costo minimo ha una produzione totale che passa da 219,5 a 389,0 unità al mese. Perché si aggiunge una penalità quadratica sui salti?
Perché ogni cambio di ritmo ha costi che il modello lineare non vede
Perché il modello lineare è inammissibile nei mesi di picco
Perché la penalità riduce la domanda da servire
Perché senza penalità Gurobi non trova l'ottimo globale
Spiegazione. Straordinari, turni da riorganizzare e fornitori da riallineare rendono costosi i cambi di ritmo; il modello lineare li ignora, la penalità li prezza.
Penalità quadratica $\gamma \sum_t (v_t - v_{t-1})^2$ sui salti della produzione totale. Rispetto a un salto di 10 unità, quanto costa un salto di 20 unità?
Lo stesso, perché la penalità conta solo i cambi di segno
Il doppio
Il quadruplo
Otto volte tanto
Spiegazione. Il costo è proporzionale al quadrato del salto: $20^2 / 10^2 = 4$. Per questo il modello preferisce molti piccoli aggiustamenti a pochi grandi salti.
Nel modello di produzione con smoothing, che cosa resta uguale al modello lineare di Modellazione PL?
Solo l'obiettivo
Dati, variabili e vincoli
Solo i vincoli di capacità
Nulla: il caso è nuovo
Spiegazione. Si aggiunge un solo dato, il peso $\gamma$; dati, variabili $x_{it}$, $s_{it}$ e vincoli di bilancio e capacità restano quelli del caso lineare.
Produzione con smoothing: all'obiettivo lineare si aggiunge $\gamma \sum_{t=2}^{m} (\sum_i x_{it} - \sum_i x_{i,t-1})^2$ con $\gamma \ge 0$; i vincoli sono lineari. Quale proprietà garantisce che ogni minimo locale sia globale?
I vincoli di bilancio sono uguaglianze e non disuguaglianze
Le variabili di produzione e di scorta sono non negative
Il numero di mesi dell'orizzonte è finito e piccolo
Il quadrato di una funzione lineare è convesso, la somma pesata pure
Spiegazione. Ogni salto è lineare nelle variabili, il suo quadrato è convesso e una somma con pesi non negativi di funzioni convesse è convessa: con vincoli lineari il QP è convesso.
Nel QP di produzione con smoothing il termine è $\gamma \sum_t (v_t - v_{t-1})^2$. Per quali valori di $\gamma$ il modello resta un QP convesso?
Solo per $\gamma > 1$
Per ogni $\gamma \ge 0$
Solo per $\gamma \le 1/160$
Per ogni valore reale di $\gamma$
Spiegazione. Con $\gamma \ge 0$ si somma una funzione convessa; con $\gamma < 0$ si sottrarrebbe un quadrato e il problema diventerebbe non convesso (premierebbe i salti).
Nello stesso esempio (un prodotto, due mesi, $h = 1$, salto $40 - 2s_1$) la derivata in $s_1 = 0$ è $f'(0) = 1 - 160\gamma$. Per quali valori di $\gamma$ conviene tenere scorta?
Per ogni $\gamma > 0$
Solo per $\gamma \ge 1$
Solo per $\gamma > 1/160$
Mai: la giacenza costa sempre
Spiegazione. Se $f'(0) \ge 0$ (cioè $\gamma \le 1/160$) aumentare $s_1$ non conviene e l'ottimo è $s_1 = 0$; con $\gamma = 0{,}004$ il solver dà infatti scorta nulla.
Esempio a due mesi con smoothing ($h = 1$): all'ottimo con scorta positiva i moltiplicatori dei due bilanci sono $\tilde\pi_1 = 9{,}5$ e $\tilde\pi_2 = 10{,}5$. Che cosa dicono le KKT sulla loro differenza?
Che è uguale a $\gamma$
Che è uguale al costo di giacenza $h$
Che è nulla, perché la scorta è libera
Che è uguale al salto ottimo
Spiegazione. La stazionarietà rispetto a $s_1 > 0$ dà $h + \tilde\pi_1 - \tilde\pi_2 = 0$: un'unità di domanda in più nel mese 2 costa una giacenza in più di una nel mese 1.
Nello script di produzione con smoothing `tot[t]` è la produzione totale del mese $t$ e `costo` il costo lineare. Come si scrive l'obiettivo in gurobipy?
`m.addConstr(costo + gamma * salti <= 0)` con `salti` somma dei quadrati dei salti
`m.setObjective(costo, GRB.MINIMIZE)` e poi `m.Params.NonConvex = 2` per i salti
`m.addGenConstrPow(salti, costo, 2)` e poi `m.setObjective(costo, GRB.MINIMIZE)`
`m.setObjective(costo + gamma * salti, GRB.MINIMIZE)` con `salti` somma dei quadrati dei salti
Spiegazione. Il termine quadratico si scrive come prodotto di espressioni lineari e si somma al costo nell'obiettivo; il QP è convesso e non servono parametri speciali.
Lo script di produzione con smoothing non legge i dati da un file: li scrive nel codice con gli stessi valori del caso lineare. Perché?
Perché gira anche in Colab; i CSV stanno nel repository di Modellazione PL
Perché Gurobi non sa leggere i file CSV dei casi di studio
Perché i dati del caso quadratico sono diversi da quelli lineari
Perché i notebook di Colab non possono importare pandas
Spiegazione. I dati stanno in un solo repository (Modellazione PL); lo script NLP li riscrive con gli stessi valori, ed è così autosufficiente anche in Colab.
Caso di studio della produzione: il piano lineare costa 32.889,33 €; con $\gamma = 0{,}5$ il costo di produzione e giacenza è 33.000,96 € e il salto massimo scende da 81,4 a 1,2 unità. Quanto costa, in percentuale, la regolarità?
Circa il 3,4%
Circa lo 0,34%
Circa il 34%
Nulla: il costo non cambia
Spiegazione. $33.000{,}96 - 32.889{,}33 = 111{,}63$ €, cioè lo $0{,}34\%$ del costo lineare: un piano quasi piatto costa pochissimo.
Con lo smoothing ($\gamma = 0{,}5$) a scorta va soprattutto il prodotto 1 ($a_1 = 0{,}9$ ore per unità), mentre nel piano lineare la scorta anticipata era del prodotto 3 ($a_3 = 2{,}1$). Perché?
Perché il prodotto 1 ha il costo di giacenza più alto dei tre
Perché la penalità riduce la domanda da servire del prodotto 3
Perché nel QP il prodotto 3 non può mai stare a scorta
Perché la penalità conta le unità: il prodotto 1 ne dà di più per ora
Spiegazione. Il termine quadratico livella la produzione totale in *unità*; per alzare le unità dei primi mesi a parità di ore conviene il prodotto che ne usa meno per unità, il prodotto 1.
QP di produzione con $\gamma = 0{,}5$: il moltiplicatore della capacità del mese 6 è $-3{,}134$ €/ora. Con un'ora in più il valore ottimo scende di $3{,}060$; con $0{,}01$ ore il rapporto incrementale è $-3{,}133$. Che cosa si conclude?
Che Gurobi calcola male i moltiplicatori dei QP convessi
Che il vincolo di capacità del mese 6 non è attivo
Che il moltiplicatore vale al margine: si verifica con $\varepsilon$ piccolo
Che il moltiplicatore va moltiplicato per il peso $\gamma$
Spiegazione. Il valore ottimo di un QP ha curvatura: per incrementi finiti la variazione si scosta dal moltiplicatore, che è la derivata. Con $\varepsilon = 0{,}01$ il rapporto torna al moltiplicatore.
Con lo smoothing ($\gamma = 0{,}5$) i moltiplicatori della capacità dei mesi 1–3 sono nulli, mentre nel modello lineare quelli dei mesi 2 e 3 erano negativi. Perché?
Perché nel QP i moltiplicatori dei primi mesi non vengono calcolati
Perché il piano livellato non satura le ore nei primi mesi
Perché la capacità dei primi mesi è stata aumentata nel QP
Perché la domanda dei primi tre mesi è nulla
Spiegazione. Il piano regolare produce circa 325 unità ogni mese e nei primi mesi non usa tutte le ore: i vincoli di capacità non sono attivi e, per complementarietà, il loro moltiplicatore è zero.
Frontiera costo-regolarità della produzione: con $\gamma = 0{,}01$ la somma dei salti al quadrato scende da 13.699 a 2.075 e il costo sale di 48 €. Che forma ha la frontiera?
Lineare: ogni riduzione dei salti costa sempre lo stesso
Piatta: la regolarità non costa nulla a nessun livello
Crescente all'inizio e poi decrescente verso destra
Ripida all'inizio: i primi passi verso la regolarità costano poco
Spiegazione. Le prime riduzioni dei salti costano pochissimo; per arrivare a un piano quasi piatto si spendono in tutto circa 112 € su 33.000.
5. Supply chain con congestione e sostenibilità (27)
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Nel vincolo di conservazione del flusso $\sum_{j:(i,j)\in A} x_{ij} - \sum_{j:(j,i)\in A} x_{ji} = b_i$ (flusso uscente meno entrante), un mercato, cioè un nodo di domanda, ha:
$b_i > 0$
$b_i < 0$
$b_i = 0$
$b_i = \sum_{j:(j,i)\in A} u_{ji}$
Spiegazione. Uscente meno entrante è uguale al bilancio: positivo negli stabilimenti (offerta), negativo nei mercati (domanda), nullo negli hub (transito).
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Al costo di ogni arco si aggiunge il termine di congestione $\alpha\,c_{ij}\,x_{ij}^2/u_{ij}$, con $\alpha > 0$. Che effetto ha sui flussi ottimi?
Satura ancora di più le rotte più economiche
Rende il modello non convesso e più difficile
Distribuisce il flusso su più rotte invece di saturarne una
Riduce la domanda totale da servire
Spiegazione. Il termine è convesso e cresce con l'utilizzo $x_{ij}/u_{ij}$: nel caso di studio nessun arco resta saturo, come sceglierebbe un pianificatore prudente.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Ai costi degli archi si aggiunge un prezzo interno della CO$_2$ $\tau$ (€/kg), $c_{ij} + \tau e_{ij}$ ($e_{ij}$ = emissioni per unità). Al crescere di $\tau$ la frontiera costo-emissioni dell'LP procede a salti. Perché?
Gli ottimi degli LP stanno nei vertici: l'ottimo resta su un vertice, poi salta a un altro
I dati sulle emissioni $e_{ij}$ sono arrotondati al chilogrammo
Il solver si ferma prima dell'ottimo per alcuni valori di $\tau$
Le capacità $u_{ij}$ cambiano a scalini con $\tau$
Spiegazione. Nel caso di studio fino a $\tau = 1$ €/kg non cambia nulla e il salto principale avviene a $\tau = 1{,}25$. Un modello strettamente convesso (con congestione) si muoverebbe con continuità.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. All'ottimo un arco di costo $c_{ij} = 7$ €/unità non porta flusso e ha costo ridotto $+2$ (attributo `RC` di Gurobi). Sotto quale costo comincerebbe a portare flusso?
Sopra $9$ €/unità
Sotto $7$ €/unità
Mai: un `RC` positivo vuol dire inutile
Sotto $5$ €/unità
Spiegazione. In un problema di minimo il costo ridotto di una variabile a zero è il miglioramento che le serve: soglia $7 - 2 = 5$ €/unità (`SAObjLow`); sopra la soglia l'arco resta inutilizzato.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. $e_{ij}$ sono i kg di CO$_2$ emessi per unità inviata sull'arco $(i,j)$. Come si introduce nel modello un prezzo interno della CO$_2$ $\tau$ (€/kg)?
Con una variabile binaria per ogni arco inquinante
Sostituendo $c_{ij}$ con $c_{ij} + \tau\,e_{ij}$ nell'obiettivo
Aggiungendo il vincolo $\sum e_{ij}x_{ij} = \tau$
Moltiplicando ogni capacità $u_{ij}$ per $\tau$
Spiegazione. È l'approccio «a peso», senza nuovi vincoli; l'alternativa impone $\sum e_{ij}x_{ij} \le \bar e$ e legge il duale di quel vincolo.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Il modello minimax «puro» dell'utilizzo minimizza $z$ soggetto a $x_{ij}/u_{ij} \le z$ su ogni arco e ai vincoli di flusso. Perché non si usa da solo?
Qualunque instradamento con utilizzo al più $\tilde z$ è ottimo, anche costosissimo
Non è convesso per via dei rapporti $x_{ij}/u_{ij}$
È sempre inammissibile quando qualche arco è saturo
Gurobi non risolve problemi con obiettivo minimax
Spiegazione. Il minimax puro è degenere rispetto al costo; in pratica si minimizza costo $+\,\rho\, z$ oppure si limita $z$ e si minimizza il costo.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. La domanda di ogni mercato è un vincolo di conservazione del flusso. Nel caso di studio i prezzi ombra di questi vincoli vanno da $8$ a $10{,}50$ €/unità. Che cosa rappresentano?
I prezzi di vendita praticati nei mercati
Le capacità residue degli archi entranti nei mercati
Il costo marginale di servire un'unità in più in ciascun mercato
La CO$_2$ emessa per unità consegnata a ciascun mercato
Spiegazione. Sono i costi marginali di servizio: il numero da confrontare con il margine commerciale prima di accettare nuovi ordini.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Con il termine di congestione $\alpha c_{ij}x_{ij}^2/u_{ij}$ ($\alpha > 0$) i flussi ottimi si muovono con continuità al variare dei dati, mentre nell'LP possono saltare. Quale proprietà ne è responsabile?
La linearità dei vincoli di conservazione del flusso
La stretta convessità dell'obiettivo, che dà un ottimo unico
La non negatività dei flussi $x_{ij}$
L'interezza delle capacità $u_{ij}$
Spiegazione. Con un obiettivo strettamente convesso l'ottimo è unico e varia con continuità con i dati; un LP può far saltare l'ottimo fra vertici.
Supply chain con congestione: 100 unità viaggiano su due rotte; la rotta 1 costa $2x_1 + x_1^2/40$ (costo $c_1 = 2$, capacità $u_1 = 80$, $\alpha = 1$), la rotta 2 costa $5$ €/unità con capacità abbondante. All'ottimo i costi marginali sono uguali. Qual è la ripartizione $(x_1, x_2)$?
$(80, 20)$
$(100, 0)$
$(60, 40)$
$(50, 50)$
Spiegazione. Costo marginale della rotta 1: $2 + x_1/20$; uguagliandolo a $5$ si ha $x_1 = 60$, $x_2 = 40$. L'LP senza congestione riempirebbe la rotta 1 fino alla capacità, $(80, 20)$.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. I bilanci dei nodi $b_i$ sono positivi negli stabilimenti (offerta), negativi nei mercati (domanda), nulli negli hub. Quale condizione sui bilanci è necessaria perché il modello sia ammissibile?
$\sum_{i \in N} b_i \ge 0$: l'offerta totale copre la domanda totale
$b_i \le u_{ij}$ per ogni arco uscente da $i$
$\sum_{i \in N} b_i < 0$: la domanda supera l'offerta
Tutti i $b_i$ devono essere interi
Spiegazione. Se la domanda totale supera l'offerta totale nessun flusso soddisfa tutti i vincoli di conservazione; le capacità possono rendere il modello inammissibile anche quando la condizione sui bilanci vale.
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. $e_{ij}$ = kg di CO$_2$ per unità sull'arco $(i,j)$. Invece di un prezzo interno, l'azienda impone un tetto $\sum e_{ij}x_{ij} \le \bar e$ alle emissioni totali. Che cosa rappresenta il prezzo ombra di questo vincolo?
Le emissioni risparmiate per euro speso
Il costo totale della rete diviso per $\bar e$
Le emissioni della rotta più economica
Il prezzo implicito della CO$_2$: variazione del costo per kg di tetto in più
Spiegazione. Il duale del tetto è il costo marginale di abbattimento: è il prezzo interno $\tau$ che darebbe lo stesso instradamento con l'approccio «a peso».
LP di flusso a costo minimo della supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$. Versione con congestione: ogni arco costa $c_{ij}x_{ij} + \alpha c_{ij}x_{ij}^2/u_{ij}$. Quali fatti rendono convesso questo modello?
Spiegazione. $x_{ij}^2$ è convessa ed è moltiplicata per il coefficiente non negativo $\alpha c_{ij}/u_{ij}$; i vincoli di conservazione e di capacità sono lineari, quindi la regione ammissibile è un poliedro.
Il capitolo del corso sulla supply chain pone tre domande manageriali su una rete con costi, capacità e impronte di CO$_2$. Quale riguarda la CO$_2$?
Quanti stabilimenti conviene aprire o chiudere?
Quale mercato conviene abbandonare per primo?
Quanto lo Stato dovrebbe tassare ogni arco?
Quale prezzo della CO$_2$ fa convenire le rotte pulite?
Spiegazione. Le tre domande: come instradare i flussi al minimo costo, che cosa cambia penalizzando la congestione, e quanto alto deve essere un prezzo interno della CO$_2$ perché le rotte «pulite» diventino convenienti.
Secondo la dispensa del corso, perché conviene imparare bene la struttura a flusso su rete del modello di supply chain?
È l'unica struttura che Gurobi sa risolvere
È fra le strutture più riutilizzabili della RO
Ha sempre soluzioni ottime intere
Non richiede capacità sugli archi
Spiegazione. Rotte, carichi per arco, investimenti in capacità e contabilità del carbonio condividono la stessa struttura; i modelli di flusso tornano in logistica, energia e telecomunicazioni.
Nel capitolo sulla supply chain, il costo effettivo di una tratta «cresce rapidamente quando si avvicina alla saturazione». Che cosa rappresenta in pratica?
Straordinari, code, premi assicurativi
Tasse sulle emissioni di CO$_2$
Il costo fisso di aprire una nuova tratta
Sconti concessi per grandi volumi
Spiegazione. I costi di congestione crescono più che linearmente con l'uso di un arco; il capitolo li modella con un termine quadratico convesso $\alpha c_{ij}x_{ij}^2/u_{ij}$.
Quali decisioni quotidiane di un responsabile logistico affronta il capitolo del corso sulla supply chain?
Assumere e licenziare gli autisti
Fissare i prezzi di vendita dei prodotti
Rotte, carichi, capacità, carbonio
Programmare la manutenzione dei camion
Spiegazione. Instradare, decidere quanto caricare ogni tratta, valutare investimenti in capacità e rendicontare l'impronta carbonica: tutto leggibile dal modello di flusso e dai suoi duali.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Un mercato chiede $100$ unità; la rotta 1 costa $2$ €/unità con capacità $80$, la rotta 2 costa $5$ €/unità con capacità abbondante. Che cosa fa l'LP puro, e a che costo?
Divide 50 e 50, costo $350$ €
Riempie la rotta 1, trabocca: $260$ €
Usa solo la rotta 2, costo $500$ €
Usa solo la rotta 1, costo $200$ €
Spiegazione. La rotta economica si satura ($x_1 = 80$) e il resto va sulla rotta 2 ($x_2 = 20$): $2\cdot 80 + 5\cdot 20 = 260$ €. La rotta 1 da sola non porta 100 unità.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Un mercato chiede $100$; la rotta 1 ($2$ €/unità, capacità $80$) è satura, la rotta 2 ($5$ €/unità) porta 20. Quanto valgono i prezzi ombra della domanda e della capacità della rotta 1?
Domanda $2$, capacità $5$
Domanda $3$, capacità $-2$
Domanda $0$, capacità $0$
Domanda $5$, capacità $-3$
Spiegazione. La 101-esima unità viaggerebbe sulla rotta 2, al costo di 5; un'unità di capacità in più sulla rotta 1 sposta un'unità dalla rotta 2 alla 1, risparmiando $5 - 2 = 3$ (duale $-3$ per una capacità $\le$ in un minimo).
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Due rotte per 100 unità; con la congestione ($\alpha = 1$) la rotta economica porta $60$ unità invece di $80$ benché la sua capacità sia 80. Perché il modello la lascia non satura?
I costi marginali delle rotte si eguagliano
Un vincolo di capacità nascosto a 60 unità
Il solver si ferma prima dell'ottimo
Perché la congestione rende la rotta 1 più cara in media della rotta 2
Spiegazione. Con il termine quadratico il costo marginale della rotta 1, $2 + x_1/20$, cresce col flusso; a $x_1 = 60$ eguaglia i 5 € della rotta 2, e spostare altro flusso costerebbe di più: un margine di sicurezza, come terrebbe un pianificatore prudente.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Nel codice gurobipy gli stabilimenti si scrivono `x.sum(s, '*') <= offerta[s]`. Perché una disuguaglianza?
Perché gli stabilimenti possono anche ricevere flusso
Perché Gurobi non accetta uguaglianze sulle somme
L'offerta totale 500 supera la domanda 450
Perché l'offerta è incerta
Spiegazione. Con offerta maggiore della domanda, obbligare ogni stabilimento a spedire tutta la sua offerta renderebbe il modello inammissibile; gli hub invece si scrivono come uguaglianze (entra = esce).
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Nel codice le capacità degli archi sono limiti delle variabili, `x = m.addVars(A, ub=U)`, non vincoli. Dove si legge allora il valore di un'unità di capacità in più su un arco saturo?
Nel costo ridotto `RC` della variabile dell'arco
Nel `Pi` di un vincolo di capacità
Nello `Slack` del vincolo dell'hub
Da nessuna parte: i limiti non hanno duale
Spiegazione. Per una variabile al limite superiore, `RC` è il prezzo ombra del limite: un arco saturo in un minimo ha $\texttt{RC} < 0$, il risparmio per unità di capacità in più.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Come sono scelti costi ed emissioni degli archi nel caso di studio, e perché?
Proporzionali, per tenere semplice l'LP
Tutti uguali, per isolare l'effetto della capacità
Casuali, per verificare la robustezza
Non proporzionali: strada economica, ferro pulito
Spiegazione. Se le emissioni fossero proporzionali ai costi, minimizzare il costo minimizzerebbe anche le emissioni e non ci sarebbe compromesso; il caso è costruito perché costo e CO$_2$ siano in conflitto.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Nel codice gli hub si scrivono `x.sum('*', h) == x.sum(h, '*')`. Che cosa esprime?
Ogni hub spedisce tutta la sua capacità
Gli hub non trattengono nulla: ciò che entra esce
Ogni hub riceve da un solo stabilimento
Gli hub hanno saldo positivo
Spiegazione. È il vincolo di conservazione di un nodo di transito, saldo $b_h = 0$: il flusso entrante è uguale a quello uscente.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). I prezzi ombra delle quattro domande dei mercati sono $8{,}00$, $9{,}50$, $10{,}00$ e $10{,}50$ €/unità. A che cosa servono in pratica?
Sono i prezzi di vendita da applicare
Sono i costi medi di trasporto
Costi marginali di servizio dei mercati
Misurano la CO$_2$ di ogni mercato
Spiegazione. Ognuno è il costo di servire un'unità in più di quel mercato; M4 costa il $31\%$ più di M1. Sono anche la base corretta per un prezzo di trasferimento interno.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Risultati del caso: LP puro costo $3385$ €, utilizzo massimo $100\%$; con congestione ($\alpha = 1$) costo $3702{,}81$ €, utilizzo massimo $90\%$; minimax: $58{,}4\%$. Che cos'è il $58{,}4\%$?
Il più basso utilizzo massimo possibile
La quota di archi usati dal piano
L'utilizzo dell'arco più economico
L'aumento di costo del piano minimax
Spiegazione. Il modello minimax $\min z$ con $x_{ij}/u_{ij} \le z$ trova l'instradamento che tiene il più carico degli archi il più vuoto possibile: nessun piano carica ogni arco sotto il $58{,}4\%$.
LP di flusso a costo minimo di una supply chain sulla rete $G = (N, A)$: flussi $x_{ij}$ sugli archi, costi unitari $c_{ij}$, capacità $u_{ij}$, saldi $b_i$ (offerta $> 0$, domanda $< 0$, transito $= 0$). Rete del caso di studio: 2 stabilimenti (offerta 260 e 240), 2 hub, 4 mercati (domanda totale 450), 12 archi; archi economici «su strada» (inquinanti), costosi «su ferro» (puliti). Prezzo interno della CO$_2$ $\tau$ (€/kg) aggiunto ai costi degli archi: fino a $\tau = 1$ non cambia nulla; il salto principale avviene a $\tau = 1{,}25$ €/kg. Che cosa significa per il manager?
Le emissioni scendono linearmente con $\tau$
Qualunque $\tau$ positivo cambia le rotte
$\tau$ non ha alcun effetto su un LP
Sotto non cambia nulla; sopra, un salto
Spiegazione. Gli ottimi di un LP stanno nei vertici: la soluzione resta su un vertice e poi salta. Un prezzo della CO$_2$ sotto la soglia non cambia nulla; sopra, l'intera rete si sposta verso il ferro.
LP di flusso a costo minimo con costi $c_{ij} + \tau e_{ij}$ ($\tau$ = prezzo interno della CO$_2$, $e_{ij}$ = kg per unità): al crescere di $\tau$ le emissioni restano costanti a tratti e poi scendono a salti. Quale proprietà degli LP lo spiega?
L'LP ha un'unica soluzione per ogni $\tau$
Esiste sempre un vertice ottimo
L'obiettivo è convesso nei flussi
I flussi sono sempre numeri interi
Spiegazione. Per ogni $\tau$ esiste un vertice ottimo; resta ottimo su un intervallo di $\tau$ e poi lo sostituisce un vertice adiacente. Un modello strettamente convesso (congestione) si sposterebbe invece con continuità.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Da dove nasce la diversificazione?
Dalle covarianze $q_{ij}$ nella varianza, che premiano i titoli poco correlati
Dal vincolo di rendimento, che obbliga a mettere più titoli in portafoglio
Dai tetti $x_i \le u_i$, che vietano di investire tutto in un titolo
Dal vincolo di bilancio $\sum_i x_i = 1$, che distribuisce il capitale
Spiegazione. La varianza contiene le covarianze: combinare titoli poco correlati abbassa il rischio sotto quello di ogni componente, anche senza tetti.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Senza il vincolo di rendimento, il portafoglio di minima varianza ha già rendimento atteso $11{,}06\%$. Quanto vale il moltiplicatore del vincolo «rendimento atteso almeno $\bar r = 8\%$»?
Positivo, perché ogni punto di rendimento costa varianza
Negativo, perché il vincolo è un limite inferiore
Nullo, perché il vincolo non è attivo
Non definito, perché il modello è un QP
Spiegazione. Il vincolo non morde fino all'$11{,}06\%$, quindi per la complementarità il suo moltiplicatore è nullo; solo oltre quella soglia ogni punto di rendimento in più si paga in varianza.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Gli input $\mu_i$ e $q_{ij}$ si stimano da 60 mesi di rendimenti. Qual è la principale lezione pratica del caso di studio su queste stime?
Le covarianze sono molto più difficili da stimare dei rendimenti attesi
I rendimenti attesi sono molto meno stabili delle covarianze, e l'ottimo ne insegue gli errori
Sessanta mesi di dati danno stime abbastanza precise da fidarsi dell'ottimo
I tetti $x_i \le u_i$ tolgono gli errori di stima dagli input
Spiegazione. Un titolo con rendimento atteso vero dell'$11\%$ mostra un rendimento stimato dell'$1{,}6\%$ su 60 mesi. Rimedi: tetti, shrinkage, o il solo portafoglio di minima varianza.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. La frontiera efficiente raccoglie i portafogli di minima varianza per ogni $\bar r$. Nel caso di studio, come si colloca rispetto a essa il portafoglio equipesato $x_i = 1/n$?
Sta esattamente sulla frontiera efficiente
Coincide con il portafoglio di minima varianza
Sta sopra la frontiera, dominandola
È dominato: rendimento simile, volatilità quasi doppia
Spiegazione. La strategia «non so nulla» è chiaramente dominata; il portafoglio di minima varianza ha volatilità $6\%$ e rendimento $11\%$.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Al variare di $\bar r$ si traccia la frontiera efficiente. Quale formulazione **non** traccia la stessa frontiera?
$\max \sum_i\mu_ix_i - \lambda\sum_i\sum_j q_{ij}x_ix_j$, al variare di $\lambda \ge 0$
$\max \sum_i \mu_i x_i$, senza termine di rischio né limite sulla varianza
$\max \sum_i\mu_ix_i$ con varianza al più $\bar\sigma^2$, al variare di $\bar\sigma$
$\min$ varianza con rendimento atteso esattamente $\bar r$ sul ramo superiore
Spiegazione. Soglia sul rendimento, media-varianza e limite sulla varianza tracciano la stessa frontiera; massimizzare il solo rendimento ne dà un solo punto estremo.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Un mandato aggiunge il tetto $x_i \le 30\%$ per ogni titolo. Che effetto ha sulla frontiera efficiente?
Ne taglia la parte alta: i rendimenti più alti diventano irraggiungibili
Sposta in alto tutta la frontiera, migliorando ogni portafoglio
Non ha effetto, perché i portafogli ottimi sono già diversificati
Abbassa la varianza minima raggiungibile
Spiegazione. I vincoli di mandato restringono la regione ammissibile, quindi possono solo peggiorare la frontiera; il loro costo è la distanza fra le due frontiere, massima ai rendimenti alti.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Quale affermazione su questo QP è corretta?
È convesso solo se le vendite allo scoperto sono vietate ($x_i \ge 0$)
È convesso solo se i titoli sono non correlati ($q_{ij} = 0$ per $i \ne j$)
Ogni matrice di covarianza è semidefinita positiva, quindi il QP è convesso e l'ottimo globale
Ogni matrice di covarianza è definita positiva, quindi il portafoglio ottimo è unico
Spiegazione. Le matrici di covarianza sono $\succeq 0$, non necessariamente $\succ 0$: la convessità vale con qualunque vincolo lineare, l'unicità non è garantita.
Modello di Markowitz con due titoli non correlati di varianze $\sigma_1^2$, $\sigma_2^2$, senza vincolo di rendimento: si minimizza $\sigma_1^2x_1^2 + \sigma_2^2x_2^2$ con $x_1 + x_2 = 1$. Quali passi dimostrano che $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$ è ottimo?
Il vincolo di rendimento deve essere attivo all'ottimo
La dualità forte degli LP fra il QP e il suo duale
I tetti $x_i \le u_i$ devono essere non attivi all'ottimo
Si sostituisce $x_2 = 1 - x_1$: una parabola convessa, il cui punto stazionario è il minimo
Spiegazione. $f(x_1) = \sigma_1^2x_1^2 + \sigma_2^2(1-x_1)^2$ è convessa, quindi $f'(x_1) = 0$ dà il minimo globale; qui cade in $[0, 1]$.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. I limiti inferiori $x_i \ge \ell_i$ chiudono il modello. Che cosa esprime la scelta $\ell_i = 0$ per ogni titolo?
Che ogni titolo deve essere in portafoglio
Che i rendimenti attesi sono non negativi
Che le covarianze sono non negative
Che le vendite allo scoperto sono vietate
Spiegazione. Una quota negativa sarebbe una vendita allo scoperto; con $\ell_i = 0$ si ammettono solo quote non negative, mentre $\ell_i > 0$ imporrebbe una quota minima.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Nel caso di studio (otto ETF settoriali) il titolo singolo meno rischioso ha volatilità $7{,}53\%$, mentre il portafoglio di minima varianza ha volatilità $6{,}03\%$. Che cosa mostra?
Un errore di stima: nessun portafoglio batte il suo titolo migliore
La diversificazione: combinare titoli abbassa il rischio sotto il più sicuro
Che al titolo più sicuro andrebbe il $100\%$ del capitale
Che le covarianze sono state poste a zero
Spiegazione. Con titoli non perfettamente correlati la varianza del portafoglio è minore di quella di ogni componente; il portafoglio di minima varianza rende comunque l'$11\%$.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Nel caso di studio il portafoglio di minima varianza mette il $58{,}3\%$ nell'ETF delle utility (UTL), il titolo con la volatilità più bassa ($7{,}53\%$). Perché non il $100\%$?
Perché un mandato limita ogni titolo al $58{,}3\%$
Perché UTL ha il rendimento atteso più basso
Perché aggiungere titoli poco correlati abbassa ancora la varianza
Perché il vincolo di rendimento è attivo
Spiegazione. Spostarsi dal solo titolo più sicuro verso titoli poco correlati riduce la varianza, finché i contributi marginali alla varianza si bilanciano.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_j q_{ij}x_ix_j$ con $\sum_i x_i = 1$ e rendimento atteso almeno $\bar r$. Nel caso di studio, con $\bar r = 12\%$ il moltiplicatore del vincolo di rendimento vale circa $0{,}022$. Come si legge?
La volatilità del portafoglio è il $2{,}2\%$
Il rendimento atteso cresce di $0{,}022$ per unità di varianza
Il $2{,}2\%$ del capitale è nel titolo più rischioso
Alzare $\bar r$ di un'unità alza la varianza minima di circa $0{,}022$
Spiegazione. Il moltiplicatore è $d(\text{varianza})/d\bar r$: oltre l'$11{,}06\%$ ogni punto di rendimento richiesto in più si paga in varianza, e il prezzo cresce lungo la frontiera.
Il modello di Markowitz del corso non restituisce un solo numero ma una frontiera efficiente. A che cosa serve?
Dà il portafoglio migliore per chiunque
Elenca i titoli ordinati per rendimento
Un menu di compromessi rischio-rendimento
Mostra la storia dei rendimenti passati
Spiegazione. Ogni punto è un portafoglio di minima varianza per un rendimento richiesto; il decisore ne sceglie uno secondo la propria avversione al rischio.
Oltre la finanza, dove riappare la struttura del modello di Markowitz, secondo la dispensa?
Nei mix di progetti di R&S e simili
Solo nella gestione dei fondi pensione
Nell'instradamento di veicoli su una rete
Nella programmazione di lavori sulle macchine
Spiegazione. La struttura è «allocare un budget fra alternative rischiose e correlate»: portafogli di R&S, di clienti, perfino la capacità produttiva fra mercati volatili.
Il corso chiama Markowitz «il ponte naturale fra ottimizzazione e statistica». Perché?
Perché usa variabili intere
Perché non ha alcun vincolo
Perché si risolve con una regressione
I suoi dati sono stime
Spiegazione. Rendimenti attesi e covarianze si stimano dai dati storici; l'ottimizzatore li prende per veri, quindi gli errori di stima finiscono nel portafoglio.
Qual è la decisione di un investitore nel modello di Markowitz del corso?
Quale singolo titolo comprare
La quota investita in ogni titolo
Il numero di azioni da vendere allo scoperto
Il momento in cui vendere i titoli
Spiegazione. Le variabili sono le quote $x_i$ (sommano a 1); l'obiettivo è la varianza del rendimento del portafoglio, con un rendimento atteso minimo e limiti per titolo.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Due titoli non correlati con volatilità $\sigma_1 = 20\%$, $\sigma_2 = 30\%$, senza vincolo di rendimento. Quanto vale la quota di minima varianza $x_1$?
$x_1 = 2/5 = 40\%$
$x_1 = 9/13 \approx 69{,}2\%$
$x_1 = 1/2$
$x_1 = 3/5 = 60\%$
Spiegazione. Minimizzando $0{,}04x_1^2 + 0{,}09(1 - x_1)^2$: $x_1 = 0{,}09/(0{,}04 + 0{,}09) = 9/13$. I pesi sono inversamente proporzionali alle varianze (non alle volatilità, che darebbero il $60\%$).
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Due titoli non correlati, $\sigma_1 = 20\%$, $\sigma_2 = 30\%$: il portafoglio di minima varianza ha varianza $0{,}0277$. Quanto vale la sua volatilità, rispetto ai due titoli?
$25\%$, fra le due
$20\%$, come il titolo più sicuro
$30\%$, come il titolo più rischioso
$16{,}6\%$, sotto entrambe
Spiegazione. $\sqrt{0{,}0277} \approx 16{,}6\% < 20\%$: il portafoglio è meno rischioso di ciascun titolo, la diversificazione nella sua forma più pura.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Nell'esempio a due titoli ($\sigma_1 = 20\%$, $\sigma_2 = 30\%$, non correlati, $x_2 = 1 - x_1$), come si trova a mano la quota ottima?
Derivata nulla della varianza in $x_1$
Prendendo il titolo col rendimento più alto
Dividendo il capitale in parti uguali
Risolvendo un LP sulle due quote
Spiegazione. Sostituito il budget, la varianza è una parabola convessa in $x_1$: $0{,}08x_1 - 0{,}18(1 - x_1) = 0$ dà $x_1 = 9/13$.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Caso di studio: otto ETF settoriali (Exchange Traded Fund, fondi quotati che replicano un paniere di settore), 60 rendimenti mensili simulati. Come si ottengono $\mu_i$ e $q_{ij}$?
Sono forniti esatti dai gestori dei fondi
Sono posti uguali per tutti i titoli
Sono stimati dai 60 rendimenti mensili
Li calcola il solver
Spiegazione. Come nella pratica, gli input si stimano dai dati (e si annualizzano): per questo il capitolo si chiude con un avvertimento sulla fragilità delle stime.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Nel codice gurobipy le quote si creano con `x = m.addVars(n, ub=u)`. Quale vincolo del modello realizza `ub=u`?
I tetti per titolo $x_i \le u_i$
Il budget $\sum_ix_i = 1$
Il rendimento minimo $\sum_i\mu_ix_i \ge \bar r$
Solo il divieto di vendita allo scoperto
Spiegazione. I tetti sono limiti superiori delle variabili; il limite inferiore predefinito $0$ è il divieto di vendita allo scoperto ($\ell_i = 0$). Budget e rendimento sono vincoli espliciti.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Statistiche del caso di studio (annualizzate): TEC ha $\mu = 1{,}58\%$ e volatilità $29{,}27\%$, UTL $\mu = 11{,}99\%$ e volatilità $7{,}53\%$. Quale titolo è il meno rischioso da solo?
TEC, il più volatile
MAT, col rendimento più alto
ENE, con un rendimento alto
UTL, con volatilità $7{,}53\%$
Spiegazione. UTL ha la volatilità più bassa degli otto ETF; il portafoglio di minima varianza vi mette il $58{,}3\%$ e scende comunque sotto il suo rischio (6,03%) diversificando.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Nel codice gurobipy l'obiettivo è `quicksum(Q[i, j]*x[i]*x[j] for i in range(n) for j in range(n))`. Che modello riceve Gurobi?
Un LP, perché i vincoli sono lineari
Un QP convesso
Un QP non convesso che richiede `NonConvex = 2`
Un NLP con soli vincoli funzionali
Spiegazione. Una matrice di covarianza è semidefinita positiva, quindi l'obiettivo quadratico è convesso e Gurobi certifica un ottimo globale senza parametri speciali.
Modello di Markowitz: quote $x_i$ del capitale nei titoli $i$, rendimenti attesi $\mu_i$, covarianze $q_{ij}$; si minimizza la varianza $\sum_i\sum_jq_{ij}x_ix_j$ con $\sum_ix_i = 1$, rendimento atteso almeno $\bar r$ e limiti $\ell_i \le x_i \le u_i$. Caso di studio: fino a $\bar r = 11\%$ la volatilità resta $6{,}03\%$; a $\bar r = 12\%$ diventa $6{,}10\%$ con moltiplicatore circa $0{,}022$. Che cosa misura il moltiplicatore?
Il rendimento guadagnato per unità di varianza
La quota investita nel titolo migliore
Varianza pagata per punto di rendimento
La volatilità del portafoglio di minima varianza
Spiegazione. È $\partial(\text{varianza})/\partial\bar r$ per il vincolo di rendimento attivo; sotto l'$11{,}06\%$ il vincolo è inattivo e il moltiplicatore è nullo.
Markowitz con due titoli non correlati di varianze $\sigma_1^2$ e $\sigma_2^2$, budget $x_1 + x_2 = 1$, senza vincolo di rendimento. Quale affermazione sulle quote di minima varianza è corretta?
$x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$
$x_i$ è proporzionale a $\sigma_i^2$
$x_i$ è inversamente proporzionale a $\sigma_i$
$x_1 = x_2 = 1/2$, qualunque varianza
Spiegazione. Annullando la derivata di $\sigma_1^2x_1^2 + \sigma_2^2(1 - x_1)^2$ si ha $x_1\sigma_1^2 = x_2\sigma_2^2$: pesi inversamente proporzionali alle varianze, e varianza del portafoglio sotto entrambe.
Il QP di Markowitz minimizza $\sum_i\sum_jq_{ij}x_ix_j$; la dispensa lo dice convesso perché $\mathbf Q = (q_{ij})$ è una matrice di covarianza. Se $\mathbf Q$ fosse ricomposta da stime su campioni diversi e perdesse la semidefinitezza positiva, che cosa verrebbe meno?
Nulla: ogni matrice simmetrica dà un QP convesso
Solo il vincolo di budget del modello
La convessità del QP
La linearità del vincolo di rendimento
Spiegazione. Il QP è convesso se e solo se $\mathbf Q \succeq 0$; una vera matrice di covarianza lo è sempre, ma un collage incoerente può non esserlo, e allora l'obiettivo può essere non convesso (perfino illimitato inferiormente lungo qualche direzione).
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Da dove viene la non convessità di questo modello?
Dal vincolo di capacità $q \le k$
Dal termine bilineare $p \cdot q$ nell'obiettivo
Dalla non negatività del prezzo $p$
Dal vincolo di domanda, anche con $d$ lineare
Spiegazione. Il prodotto di due variabili non è convesso. Con domanda lineare, sostituendo $q = a - bp$, il problema ridotto è una parabola concava in $p$.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Con domanda lineare $d(p) = a - b\,p$ e senza limite di capacità, qual è il prezzo ottimo $p^\circ$?
$p^\circ = (a/b + c)/2$
$p^\circ = a/b$
$p^\circ = c$
$p^\circ = (a - c)/b$
Spiegazione. Il profitto $(p - c)(a - bp)$ è una parabola concava: annullando la derivata si ottiene $p^\circ = (a/b + c)/2$, a metà fra $c$ e il prezzo di soffocamento $a/b$.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Esempio del concerto: $d(p) = 1200 - 5p$, $c = 20$ €, $k = 400$ posti, prezzo ottimo $\tilde p = 160$ €. Il valore di un posto in più, $d\Pi/dk$ con $\Pi(k)$ profitto ottimo, è $60$ €, non il margine $\tilde p - c = 140$ €. Perché?
Perché il costo marginale $c$ cresce con la capacità $k$
Perché il posto in più resterebbe vuoto al prezzo $\tilde p$
Perché il vincolo di capacità diventa non attivo con $k = 401$
Perché il prezzo scende per tutti: $d\Pi/dk = (\tilde p - c) + k\,d\tilde p/dk = 140 - 80$
Spiegazione. Con $\tilde p = (a - k)/b$ il prezzo scende di $1/b$ per ogni posto in più, su tutti i $k$ biglietti. Ignorarlo è un errore classico nella valutazione degli investimenti in capacità.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Con domanda a elasticità costante $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$) e capacità attiva, l'ottimo è $\tilde p = (\theta/k)^{1/\varepsilon}$, dove $d(\tilde p) = k$. Che tipo di ottimo è?
Un punto stazionario del profitto $(p - c)\,d(p)$
Un minimo locale del profitto
Un punto di spigolo, dove nessuna derivata del profitto si annulla
Una soluzione illimitata tagliata dalla capacità
Spiegazione. Sotto $\tilde p$ la capacità si vende comunque (conviene alzare il prezzo), sopra il profitto scende: con vincoli l'ottimo non si cerca solo fra i punti stazionari.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Esempio del concerto $d(p) = 1200 - 5p$, $c = 20$ €: senza capacità la quantità ottima è $q^\circ = 550$ posti. Che cosa succede al valore della capacità $d\Pi/dk$ per $k > 550$?
Continua a crescere linearmente con $k$
È nullo: la capacità non è più un vincolo attivo
Diventa negativo: i posti vuoti costano
È pari al margine pieno $p^\circ - c$
Spiegazione. Oltre la quantità ottima senza vincolo la curva del profitto ottimo $\Pi(k)$ è piatta: la capacità aggiuntiva non vale nulla.
Modello di pricing con due categorie di posti (platea e galleria) e sostituzione: la domanda di ogni categoria dipende da entrambi i prezzi $p_1, p_2$. Perché i due prezzi vanno decisi insieme?
Perché ogni domanda dipende da entrambi i prezzi: uno alla volta si perde profitto
Perché le due categorie hanno lo stesso costo marginale
Perché le due categorie hanno la stessa capacità
Perché con due prodotti il modello diventa un LP
Spiegazione. Alzare il prezzo della platea sposta parte della domanda verso la galleria: il modello congiunto tiene cara la platea per sfruttare la sostituzione.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Con una funzione di domanda generale $d(p)$ (per esempio logistica) il profitto può non essere concavo. Che cosa raccomanda il corso prima di fidarsi della risposta del solver?
Sostituire $d(p)$ con una domanda lineare stimata sui dati
Togliere il vincolo di capacità, fonte di punti di spigolo
Porre il prezzo uguale al costo marginale $c$
Studiare dominio e derivate e disegnare il profitto
Spiegazione. Gurobi certifica l'ottimo globale, ma capire la forma del profitto (dominio, derivate, grafico sull'intervallo rilevante, più punti iniziali) resta parte del lavoro.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Il modello scrive $q \le d(p)$ invece di $q = d(p)$. Quale ipotesi garantisce che all'ottimo $\tilde q = \min\{d(\tilde p), k\}$?
$k > d(p)$ per ogni prezzo $p$
La domanda $d(p)$ è lineare in $p$
$\tilde p > c$: ogni unità venduta in più aggiunge profitto
$\tilde p = c$: il margine è nullo
Spiegazione. Con margine unitario positivo ogni unità venduta in più aumenta il profitto, quindi $q$ viene spinta fino al minimo fra domanda e capacità.
Pricing a due categorie (platea 1, galleria 2) con domande $d_1 = 500 - 2p_1 + 0{,}6\,p_2$ e $d_2 = 900 + 0{,}8\,p_1 - 4p_2$. Che cosa esprime il coefficiente positivo $0{,}6$ di $p_2$ in $d_1$?
Che la platea è piena al 60%
Che la domanda di platea scende quando sale il prezzo della galleria
Che le due categorie sono complementari
La sostituzione: una galleria più cara sposta domanda sulla platea
Spiegazione. Un coefficiente incrociato positivo indica prodotti sostituti; per questo i due prezzi vanno scelti insieme.
Pricing a due categorie: si massimizza $\sum_i (p_i - c_i)q_i$ con $q_i \le d_i(p_1, p_2)$ (domande lineari) e $q_i \le k_i$. Quale impostazione di Gurobi richiede questo modello?
Nessuna: con domande lineari è un LP
`NonConvex = 2`, per via dei termini bilineari $p_i q_i$
`FuncNonlinear = 1`, per via delle funzioni di domanda
`QCPDual = 1`, per renderlo convesso
Spiegazione. L'obiettivo contiene i prodotti di due variabili $p_iq_i$, come nel caso a un prodotto: bilineare, non convesso, risolto globalmente con `NonConvex = 2`.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Domanda a elasticità costante $d(p) = \theta p^{-\varepsilon}$ con $\varepsilon = 2{,}2$ e $c = 20$ €: senza capacità il prezzo ottimo sarebbe $c\,\varepsilon/(\varepsilon - 1) = 36{,}67$ €. Perché l'ottimo con capacità $k$ è invece $\tilde p = 79{,}11$ €?
A $36{,}67$ € la domanda supera di molto $k$: il prezzo sale finché $d(p) = k$
Perché la formula $c\varepsilon/(\varepsilon - 1)$ vale solo per $\varepsilon < 1$
Perché il solver si ferma in un ottimo locale
Perché a $36{,}67$ € il margine $p - c$ è negativo
Spiegazione. Vendere comunque $k$ a un prezzo più alto aumenta il profitto: l'ottimo è il punto di spigolo dove la domanda è pari alla capacità, $\tilde p = (\theta/k)^{1/\varepsilon}$.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Con domanda lineare $d(p) = a - bp$ ($b > 0$) e senza capacità, quali fatti rendono $p^\circ = (a/b + c)/2$ l'ottimo globale?
Con $q = a - bp$ il profitto $(p - c)(a - bp)$ è concavo in $p$: stazionario vuol dire globale
Il termine bilineare $p\,q$ è convesso, quindi ogni punto stazionario è un ottimo globale
Il vincolo di domanda non è attivo all'ottimo, quindi il modello si riduce a un LP
La dualità forte fra il modello di pricing e il suo duale
Spiegazione. Il coefficiente di $p^2$ è $-b < 0$: il profitto ridotto è concavo in $p$ e $\Pi'(p) = 0$ ne dà il massimo globale.
Che cosa c'è di nuovo nel capitolo del corso sul pricing rispetto ai modelli precedenti?
La domanda è un dato fisso del modello
Il prezzo è una variabile decisionale
Il modello ha variabili intere
La capacità si suppone illimitata
Spiegazione. Con il prezzo come decisione la quantità venduta ne dipende e il profitto $p\cdot q$ contiene un termine bilineare: il corso incontra per la prima volta la non convessità.
Perché la dispensa chiama il prezzo «forse la decisione aziendale a più alto impatto sul margine»?
Il prezzo muove il margine di ogni unità
Perché i prezzi non cambiano mai
Perché i costi non dipendono dal volume
Perché la domanda non risponde al prezzo
Spiegazione. Una variazione di prezzo colpisce il margine di ogni unità venduta, una di volume solo le unità in più; da qui l'attenzione ai modelli di pricing.
Un obiettivo del capitolo sul pricing è riconoscere gli «ottimi di spigolo». Che cosa sono?
Ottimi dei soli programmi lineari
Ottimi trovati arrotondando una soluzione
Ottimi dove nessuna derivata si annulla
Ottimi locali di funzioni non convesse
Spiegazione. Con la capacità vincolante l'ottimo può stare dove $d(p) = k$: lì il profitto non ha punti stazionari, e cercare solo fra i punti stazionari lo farebbe perdere.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Domanda lineare $d(p) = a - bp$. Sostituendo $q = a - bp$, che cosa diventa il profitto $(p - c)(a - bp)$ come funzione di $p$?
Una parabola convessa: il problema è difficile
Una funzione lineare: l'ottimo sta su un limite
Una parabola concava: il problema ridotto è facile
Una cubica con due massimi locali
Spiegazione. Il profitto ridotto è una quadratica concava in $p$, massima in $p^\circ = (a/b + c)/2$ senza capacità; la versione bilineare Gurobi la risolve comunque globalmente con `NonConvex = 2`.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Come tratta la dispensa in Gurobi le funzioni di domanda generali (elasticità costante $\theta p^{-\varepsilon}$, logistica)?
Con i vincoli funzionali
Linearizzandole intorno all'ottimo
Con un solver NLP locale da un punto
Sostituendole con la domanda lineare
Spiegazione. I vincoli funzionali di Gurobi (`addGenConstrPow`, `addGenConstrExp`) le gestiscono nello stesso solver, sempre con ottimo globale.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Caso del concerto ($d(p) = 1200 - 5p$, $c = 20$, $k = 400$): Gurobi dà $p^* = 160$, profitto $56.000$ €; risolvendo con $k = 401$ stima il valore di un posto in più in $59{,}80$ € (teoria: $60$). Perché il valore si stima risolvendo di nuovo?
Perché i duali dell'LP sono lenti da leggere
Perché il vincolo di capacità è inattivo
Perché il risultato deve essere intero
I QP non convessi non danno duali: si perturba
Spiegazione. Con l'obiettivo bilineare (`NonConvex = 2`) Gurobi non restituisce `Pi`; lo script pone `v_cap.RHS = K + 1`, riottimizza e fa la differenza.
Modello di pricing: si scelgono prezzo $p$ e quantità venduta $q$ per massimizzare $p\,q - c\,q$ soggetto a $q \le d(p)$ (domanda al prezzo $p$) e $q \le k$ (capacità). Domanda logistica $d(p) = m/(1 + e^{-\alpha + \beta p})$ con $m = 900$, $\alpha = 6$, $\beta = 0{,}045$, $c = 20$, $k = 400$: il solver dà $p^* = 138{,}29$ €. Che cosa raccomanda la dispensa prima di fidarsi di un risultato simile?
Nulla: Gurobi ha sempre ragione
Studiare e tracciare il profitto
Arrotondare prima il prezzo all'euro
Sostituire la logistica con una domanda lineare
Spiegazione. Con domande generali il profitto può non essere concavo: studiare dominio e derivate, tracciare il profitto sull'intervallo rilevante e, con solver locali, provare più punti iniziali.
Pricing con domanda lineare $d(p) = a - bp$, costo $c$, capacità $k$ vincolante: $p^* = (a - k)/b$ e profitto $\Pi(k) = (p^* - c)k$. Perché un posto in più vale meno del margine pieno $p^* - c$?
Perché il costo $c$ cresce con $k$
Perché la domanda diventa infinita
Perché il vincolo di capacità diventa inattivo
Riempirlo abbassa il prezzo a tutti
Spiegazione. $dp^*/dk = -1/b$, quindi $d\Pi/dk = (p^* - c) + k\,dp^*/dk$; nel concerto ($a = 1200$, $b = 5$, $c = 20$, $k = 400$) vale $140 - 80 = 60$ €, non 140.
Pricing con domanda a elasticità costante $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$), costo $c$, capacità $k$; l'ottimo non vincolato $c\varepsilon/(\varepsilon - 1)$ supererebbe la capacità. Perché l'ottimo sta in $p^* = (\theta/k)^{1/\varepsilon}$, dove $d(p) = k$?
È l'unico punto stazionario del profitto
Sotto il profitto cresce, sopra scende
Perché il profitto è lineare in $p$
Perché lì l'elasticità vale 1
Spiegazione. Per $p < p^*$ la domanda supera $k$, le vendite restano $k$ e $(p - c)k$ cresce; per $p > p^*$ il profitto $(p - c)\theta p^{-\varepsilon}$ decresce (siamo oltre il suo picco libero). L'ottimo è uno spigolo dove nessuna derivata si annulla.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Che cosa vale all'ottimo per ogni canale con $0 < \tilde x_i < u_i$?
$r_i'(\tilde x_i) = \lambda$: l'ultimo euro rende lo stesso in tutti questi canali
$\tilde x_i = b/n$: il budget si divide in parti uguali fra i canali
$r_i(\tilde x_i) = \lambda$: ogni canale dà la stessa risposta totale
$r_i'(\tilde x_i) = 0$: ogni canale è spinto fino alla saturazione
Spiegazione. Se i rendimenti marginali fossero diversi, spostare un euro dal canale con rendimento basso a quello con rendimento alto migliorerebbe la risposta totale.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Un canale resta a zero nell'allocazione ottima, $\tilde x_i = 0$. Che cosa si può dire?
Il suo rendimento marginale $r_i'(0)$ è pari a $\lambda$
Il suo tetto $u_i$ è troppo piccolo per servire
Il suo rendimento marginale iniziale $r_i'(0)$ è al più $\lambda$
Il vincolo di budget non è attivo
Spiegazione. Un canale a zero non vale neppure il primo euro: $r_i'(0) \le \lambda$. I canali al tetto possono invece avere rendimento marginale $\ge \lambda$.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel caso di studio i tetti sono $u = (60, 80, 120, 35)$ migliaia di € e $\lambda$ scende a zero quando il budget arriva a $b = 300$. Perché?
Perché le risposte $r_i$ diventano lineari per spese grandi
Perché il solver fallisce con budget grandi
Perché il vincolo di budget diventa un'uguaglianza
Perché tutti i canali sono al tetto: $60 + 80 + 120 + 35 = 295 < 300$
Spiegazione. Con tutti i canali al tetto il vincolo di budget non è più attivo, quindi il suo moltiplicatore è nullo. La curva del valore del budget è concava: $\lambda$ scende al crescere di $b$.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Le risposte sono $r_i(x) = a_i\log(1 + k_ix)$. Nel caso di studio la TV riceve meno dei social benché il suo tetto $u_i$ sia più alto. Che cosa lo spiega?
Il tetto della TV è attivo all'ottimo
La velocità di saturazione $k_i$ di ogni canale, non la sua dimensione
Un errore numerico del solver
Il solo coefficiente di scala $a_i$
Spiegazione. Conta la rapidità con cui cala il rendimento marginale $a_ik_i/(1 + k_ix)$, governata da $k_i$: un canale grande che satura presto riceve meno.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Con $r_i(x) = a_i\log(1 + k_ix)$, come si tratta in Gurobi l'obiettivo $\sum_i a_i\log(1 + k_ix_i)$?
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Che cosa dice a un direttore finanziario il moltiplicatore $\lambda$ del vincolo di budget?
La risposta totale della campagna all'ottimo
Il tetto del canale con la risposta migliore
La risposta in più comprata da un euro di budget in più
La risposta media per euro speso
Spiegazione. $\lambda$ è il valore marginale del budget: conviene aggiungere budget finché $\lambda$ supera il valore di un euro investito altrove, e $\lambda$ scende al crescere del budget.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Quale enunciato giustifica che questo modello ha un ottimo globale certificabile?
Ogni NLP con vincoli lineari ha un ottimo unico
Si massimizza una somma di funzioni concave su un poliedro: i massimi locali sono globali
Ogni funzione separabile è lineare su un poliedro
L'obiettivo è crescente, quindi il budget è attivo
Spiegazione. L'obiettivo è separabile e somma di funzioni concave, i vincoli sono lineari: il problema è convesso e ogni massimo locale è globale.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Quali ingredienti danno la condizione $r_i'(\tilde x_i) = \lambda$ per un canale all'ottimo?
Solo il fatto che il vincolo di budget sia attivo
La linearità delle funzioni di risposta $r_i$
La dualità forte degli LP applicata al vincolo di budget
Stazionarietà KKT, $r_i$ derivabile e $0 < \tilde x_i < u_i$ (moltiplicatori dei limiti nulli)
Spiegazione. Per i canali su un limite, i moltiplicatori di $x_i \ge 0$ o $x_i \le u_i$ entrano nella stazionarietà e l'uguaglianza con $\lambda$ non vale più.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Le risposte $r_i$ sono crescenti. Che cosa succederebbe senza il vincolo di budget $\sum_i x_i \le b$?
Il modello diventerebbe inammissibile
Ogni canale riceverebbe la stessa spesa
Il modello diventerebbe non convesso
Ogni canale andrebbe al suo tetto $u_i$
Spiegazione. Il budget è l'unico vincolo che lega i canali: con risposte crescenti e senza budget, ogni canale è spinto da solo fino al tetto.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel caso di studio, con $b = 100$ migliaia di €, i quattro canali stanno strettamente fra $0$ e i loro tetti e i loro rendimenti marginali $r_i'(\tilde x_i)$ valgono tutti $8{,}2693$. Che cosa conferma?
Che il solver si è fermato troppo presto
Che il vincolo di budget non è attivo
La condizione KKT $r_i'(\tilde x_i) = \lambda$, con $\lambda = 8{,}2693$
Che le quattro risposte sono identiche
Spiegazione. Per i canali interni la stazionarietà dà $r_i'(\tilde x_i) = \lambda$: l'ultimo euro rende ovunque lo stesso, e il valore comune è il moltiplicatore del budget.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel caso di studio $\lambda = 8{,}2693$; aggiungendo $1$ (migliaio di €) al budget e risolvendo di nuovo, la risposta cresce di $8{,}244$. Perché un po' meno di $\lambda$?
Un errore numerico dei vincoli funzionali
Perché un canale raggiunge il suo tetto
Perché il moltiplicatore è sbagliato di circa lo $0{,}3\%$
La concavità: il valore marginale scende al crescere del budget
Spiegazione. La risposta ottima $V(b)$ è concava: l'incremento finito su $[b, b + 1]$ è minore della pendenza $\lambda$ in $b$. La verifica conferma comunque la lettura del moltiplicatore.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_i r_i(x_i)$ soggetto a $\sum_i x_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Sia $V(b)$ la risposta totale ottima in funzione del budget $b$. Quale affermazione è corretta?
$V(b)$ è concava, con pendenza $\lambda(b)$ non crescente in $b$
$V(b)$ è convessa, quindi $\lambda(b)$ cresce con il budget
$V(b)$ è lineare, quindi $\lambda$ è lo stesso per ogni budget
$V(b)$ è decrescente quando tutti i canali sono attivi
Spiegazione. Massimizzare una funzione concava con il budget come termine noto dà una funzione valore concava: nel caso di studio $\lambda$ scende da $19$ ($b = 20$) a $4$ ($b = 260$).
Il capitolo sul budget chiama «schema universale» l'allocazione fra impieghi con rendimenti decrescenti. Quale esempio vi rientra?
Instradare camion su una rete stradale
Fondi fra progetti, tempo fra attività
Scegliere un fornitore su tre
Mettere in sequenza lavori su una macchina
Spiegazione. Canali di marketing, fondi fra progetti, tempo fra attività, fertilizzante fra campi: valgono lo stesso modello e la stessa regola di ottimalità.
Quale affermazione «forte e verificabile» fa la teoria sull'allocazione ottima del budget, secondo la dispensa?
All'ottimo i rendimenti marginali sono uguali
Tutti i canali ricevono la stessa spesa
Il canale più grande prende tutto
La spesa è proporzionale ai tetti
Spiegazione. All'ottimo i rendimenti marginali dei canali attivi coincidono, ed è ciò che il solver restituisce cifra per cifra (il caso di studio mostra $8{,}2693$ per tutti e quattro i canali).
Come si userà il moltiplicatore $\lambda$ del vincolo di budget, secondo gli obiettivi del capitolo?
Per fissare i tetti dei canali
Per scegliere le funzioni di risposta
Per negoziare l'ampiezza del budget
Per arrotondare le spese
Spiegazione. $\lambda$ è la risposta in più per euro di budget in più; la curva di $\lambda$ in funzione del budget è l'argomento quantitativo per decidere quanto dare al marketing.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Due canali, $r_1(x) = 100\log(1 + 0{,}2x)$, $r_2(x) = 60\log(1 + 0{,}1x)$, budget $b = 50$ (migliaia di €), senza tetti. Qual è la ripartizione ottima?
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Due canali, $r_1(x) = 100\log(1 + 0{,}2x)$, $r_2(x) = 60\log(1 + 0{,}1x)$, $b = 50$: l'ottimo è $x_1 = 35{,}6$, $x_2 = 14{,}4$. Quanto vale il prezzo ombra del budget?
$\lambda = 20{,}0$
$\lambda = 6{,}0$
$\lambda = 0{,}0$
$\lambda = 2{,}46$
Spiegazione. $\lambda = r_1'(35{,}6) = 20/(1 + 0{,}2\cdot 35{,}6) = 2{,}46$, uguale a $r_2'(14{,}4) = 6/2{,}44$: un euro di budget in più rende circa $2{,}46$ unità, da qualunque canale entri.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Esempio a due canali senza tetti e $b = 50$. Perché il vincolo di budget si può usare come uguaglianza, $x_2 = 50 - x_1$?
Il budget non speso andrebbe sprecato
Perché qui lo impongono i tetti
Perché $\lambda = 0$ all'ottimo
Perché i due canali sono identici
Spiegazione. Con risposte crescenti un euro non speso potrebbe sempre aggiungere risposta da qualche parte, quindi all'ottimo il budget è attivo (e $\lambda > 0$).
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Due canali con $r_1'(0) = 20$ e $r_2'(0) = 6$ (risposta marginale del primo euro). Che cosa implica la regola ottima per il canale 2 quando il budget è molto piccolo?
Riceve sempre metà del budget
Prende tutto, essendo il più economico
Resta a zero finché $r_1'$ non scende a 6
Riceve la stessa spesa del canale 1
Spiegazione. Il denaro va prima dove il rendimento marginale è più alto; il canale 2 entra solo quando il marginale del canale 1, decrescente con la spesa, è sceso al suo marginale iniziale di 6.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel codice gurobipy, con $r_i(x) = a_i\log(1 + k_ix)$, lo script crea `g = m.addVars(4, lb=1.0)` e `z = m.addVars(4, lb=-GRB.INFINITY)`, con `g[i] == 1 + k[i]*x[i]` e `addGenConstrLog(g[i], z[i])`. Perché `z` è libera?
Perché $z_i$ deve essere negativa
Perché Gurobi vuole variabili libere nell'obiettivo
Perché un logaritmo in generale può essere negativo
Perché $z_i$ è una variabile binaria
Spiegazione. `addGenConstrLog` impone $z = \log g$; il limite predefinito $z \ge 0$ taglierebbe i valori con $g < 1$. Qui $g \ge 1$ quindi comunque $z \ge 0$, ma dichiararla libera evita una restrizione nascosta.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel codice gurobipy del caso del budget lo script imposta `m.Params.FuncNonlinear = 1`. Che cosa fa?
Tratta il logaritmo in modo esatto
Trasforma il modello in un LP
Ammette spese intere sui canali
Stampa il log del solver
Spiegazione. Con `FuncNonlinear = 1` i vincoli funzionali sono trattati in modo esatto (non con un'approssimazione a tratti fissa), quindi l'ottimo è globale certificato.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Nel codice del budget l'obiettivo è `quicksum(a[i] * z[i] for i in range(4))`, con $z_i = \log(1 + k_ix_i)$ imposto da vincoli funzionali. Perché funziona?
Perché $\log$ è lineare in $x_i$
Perché Gurobi approssima $\log$ con una retta
Perché i tetti rendono $z_i$ costante
È lineare nelle ausiliarie $z_i$
Spiegazione. Tutta la non linearità passa nei vincoli $z_i = \log g_i$, $g_i = 1 + k_ix_i$; l'obiettivo è allora una combinazione lineare delle $z_i$.
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Caso di studio: risposta totale $1449{,}8$, quattro canali con marginali tutti uguali a $8{,}2693$; aggiungendo 1000 € di budget la risposta cresce di $8{,}244$. Che cosa verifica?
Che i tetti dei canali sono attivi
Che $\lambda$ è il valore del budget
Che le risposte sono lineari
Che un canale andrebbe eliminato
Spiegazione. La condizione KKT $r_i'(x_i) = \lambda$ si vede nei numeri, e il guadagno reale di un'unità di budget in più, $8{,}244$, conferma la lettura del moltiplicatore (un po' meno, per la concavità).
Modello del budget pubblicitario: spesa $x_i$ sul canale $i$, risposta concava $r_i(x_i)$, si massimizza $\sum_ir_i(x_i)$ soggetto a $\sum_ix_i \le b$ (budget, moltiplicatore $\lambda \ge 0$) e $0 \le x_i \le u_i$ (tetti). Caso di studio: $\lambda = 18{,}97$ con $b = 20$, $8{,}24$ con $b = 100$, $4{,}05$ con $b = 260$, e $0$ con $b = 300$ (tetti $60 + 80 + 120 + 35 = 295$). Perché $\lambda$ crolla a zero con $b = 300$?
Perché le risposte diventano convesse
Perché il solver fallisce
Tutti i canali sono ai tetti
Perché il budget va tutto su un canale
Spiegazione. Con $b \ge 295$ ogni canale è al suo tetto, quindi un euro in più non si può usare: il vincolo di budget è lasco e il suo moltiplicatore è nullo.
Modello del budget pubblicitario: si massimizza $\sum_ir_i(x_i)$ (concava) con $\sum_ix_i \le b$ (moltiplicatore $\lambda$) e $0 \le x_i \le u_i$. La regola $r_i'(\tilde x_i) = \lambda$ vale per i canali strettamente dentro $(0, u_i)$. Che cosa succede per un canale al suo tetto $u_i$?
$r_i'(u_i) \ge \lambda$
$r_i'(u_i) = \lambda$ in ogni caso
$r_i'(u_i) \le \lambda$
$r_i'(u_i) = 0$ al tetto
Spiegazione. La stazionarietà è $r_i'(\tilde x_i) = \lambda + \mu_i$ con $\mu_i \ge 0$ moltiplicatore di $x_i \le u_i$: un canale al tetto meriterebbe più denaro ma non può prenderlo. Togliendo l'ipotesi «interno» la condizione cambia.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Quale obiettivo ha un ottimo in forma chiusa?
Weber: somma pesata delle distanze
Minimax: distanza massima
Somma pesata delle distanze al quadrato
Nessuno dei tre obiettivi
Spiegazione. Annullando il gradiente di $\sum_i w_i[(x - a_i)^2 + (y - b_i)^2]$ si ottiene il baricentro pesato $\tilde x = \sum_i w_ia_i/\sum_i w_i$ (e analogamente per $y$).
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Quale proprietà caratterizza l'ottimo del modello minimax (minimizzare la distanza del quartiere più lontano)?
È il centro del più piccolo cerchio che contiene tutti i quartieri
È il baricentro pesato dei quartieri
È la mediana pesata dei quartieri, coordinata per coordinata
Coincide sempre con il punto di Weber
Spiegazione. Dipende solo dai quartieri estremi e ignora i pesi: per questo il minimax protegge le periferie, indipendentemente dalla loro popolazione.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Modello di Weber: si minimizza $\sum_i w_i\,d_i$, con $d_i$ distanza euclidea dal quartiere $i$. Quale condizione vale nell'ottimo, quando non è un punto di quartiere?
La struttura è equidistante da tutti i quartieri
Si annulla il gradiente delle distanze al quadrato
La distanza massima $\max_i d_i$ è minima
$\sum_i w_i\,\mathbf u_i = \mathbf 0$, con $\mathbf u_i$ versore verso il quartiere $i$
Spiegazione. Le «trazioni» unitarie pesate si bilanciano; la funzione non è derivabile nei punti dei quartieri e non ha forma chiusa.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Come si scrivono le distanze euclidee nel modello Gurobi del caso di studio?
Con un'approssimazione lineare a tratti della radice
Con una variabile $d_i$ e il vincolo conico convesso $(x - a_i)^2 + (y - b_i)^2 \le d_i^2$
Con `NonConvex = 2` e le distanze al quadrato nell'obiettivo
Con variabili binarie che scelgono il quartiere più vicino
Spiegazione. Weber minimizza $\sum_i w_id_i$, il minimax una variabile $z$ con $d_i \le z$: le strutture puramente coniche (convesse) non richiedono parametri speciali in Gurobi.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). La frontiera efficienza-equità mette a confronto la distanza media pesata e la distanza massima. Nel caso di studio è quasi piatta. Che cosa significa?
Efficienza ed equità sono in forte conflitto
Il modello con i due obiettivi è inammissibile
Ridurre la distanza massima costa pochissima distanza media
I punti di Weber e del minimax coincidono
Spiegazione. Garantire $0{,}63$ km in meno al quartiere più lontano costa solo $47$ metri di distanza media: un argomento forte in una discussione pubblica.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Come si costruisce la frontiera efficienza-equità (distanza media contro distanza massima) con il metodo $\varepsilon$-constraint?
Si minimizza la distanza media con un tetto $D$ su ogni distanza, variando $D$
Si minimizza la somma della distanza media e della distanza massima
Si risolvono Weber e minimax separatamente e si fa la media delle posizioni
Si variano i pesi $w_i$ dei quartieri e si risolve di nuovo Weber
Spiegazione. Ogni valore di $D$ dà un punto della frontiera; gli estremi sono la soluzione minimax ($D$ minimo ammissibile) e il punto di Weber ($D$ grande).
Localizzazione su una retta: clienti nelle posizioni $a_i$ con pesi $w_i \ge 0$. Quale affermazione su $\min_x \sum_i w_i|x - a_i|$ (Weber in una dimensione) è corretta?
L'ottimo è la media pesata $\sum_i w_ia_i/\sum_i w_i$
Un ottimo è la mediana pesata: almeno metà del peso da ciascun lato
L'ottimo è il punto medio fra i due clienti estremi
L'ottimo è la mediana non pesata delle posizioni
Spiegazione. Allontanandosi dalla mediana pesata il costo cresce sul lato più pesante più di quanto cali sull'altro. La media pesata risolve le distanze al quadrato, il punto medio il minimax.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Quali fatti rendono convesso in $(x, y)$ l'obiettivo di Weber $\sum_i w_i\sqrt{(x - a_i)^2 + (y - b_i)^2}$?
È derivabile in tutto il piano
La distanza al quadrato è convessa e la radice è crescente
I quartieri sono in numero finito e numerati
La norma di una mappa affine è convessa, $w_i \ge 0$, somme di convesse sono convesse
Spiegazione. Ogni termine è la norma euclidea di una funzione affine di $(x, y)$; i pesi sono non negativi. La derivabilità manca nei punti dei quartieri, ma la convessità vale. Nota: crescente $\circ$ convessa è convessa solo se la funzione esterna è anche convessa, e la radice è concava.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). La struttura deve stare entro la distanza $r$ da una sottostazione elettrica in $(a_0, b_0)$. Come si scrive questo vincolo, ed è convesso?
$|x - a_0| + |y - b_0| \ge r$, non convesso
$(x - a_0)^2 + (y - b_0)^2 \le r^2$, convesso
$(x - a_0)^2 + (y - b_0)^2 \ge r^2$, convesso
Solo $x \le a_0 + r$, lineare
Spiegazione. Un disco è un insieme convesso; aggiungerlo a qualunque obiettivo di localizzazione convesso mantiene il problema convesso. La versione $\ge$ descriverebbe l'esterno di un disco, che non è convesso.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Nel caso di studio la struttura deve stare entro 2 km da una sottostazione; l'ottimo di Weber vincolato sta sul bordo di quel disco e costa solo il $+0{,}2\%$. Qual è la lezione manageriale?
Il vincolo non è attivo e si potrebbe togliere
Il modello di Weber non è adatto ai problemi vincolati
Equità ed efficienza sono in forte conflitto
Un vincolo temuto può rivelarsi quasi gratis: va misurato
Spiegazione. Il vincolo è attivo (ottimo sul bordo) ma il suo costo è minimo: scoprirlo è un risultato importante quanto l'ottimo stesso.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Nel caso di studio (12 quartieri) il punto di Weber $(4{,}886;\ 5{,}310)$ quasi coincide con il baricentro pesato $(4{,}897;\ 5{,}397)$, mentre il punto minimax si sposta di mezzo chilometro. Perché Weber e baricentro sono così vicini?
Perché i pesi sono distribuiti in modo abbastanza uniforme attorno al centro
Perché Weber e baricentro coincidono sempre
Perché il minimax ignora i pesi
Perché il vincolo della sottostazione è attivo
Spiegazione. Weber (somma delle distanze) e baricentro (somma delle distanze al quadrato) differiscono quando pochi quartieri pesanti o lontani tirano in modo diverso; con pesi equilibrati sono vicini, mentre il minimax segue i quartieri estremi.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). La frontiera efficienza-equità mette la distanza media minima contro un tetto $D$ sulla distanza massima. Che cosa significherebbe una frontiera **ripida**?
Che l'equità è quasi gratis
Che il modello è scalato male
Che Weber e minimax coincidono
Un vero conflitto: ogni km in meno al più lontano costa molta distanza media
Spiegazione. Nel caso di studio la frontiera è quasi piatta (equità quasi gratis); una ripida segnalerebbe che proteggere le periferie ha un alto costo di efficienza.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Il capitolo confronta tre significati di «vicino alla domanda». Quale obiettivo esprime l'**equità** verso l'utente più sfortunato?
La distanza media pesata (Weber)
La distanza quadratica pesata
La distanza massima (minimax)
Il numero di quartieri serviti
Spiegazione. La distanza media misura l'efficienza, quella quadratica porta al baricentro, la distanza massima protegge il quartiere più lontano.
Quali strutture cita il corso come esempi per il modello di localizzazione continua?
Magazzini scelti da un elenco fisso
Macchine su una linea di produzione
Filiali bancarie da chiudere
Una stazione di ricarica o un micro-hub
Spiegazione. Nella versione continua le coordinate sono libere sul piano: una stazione di ricarica, un micro-hub logistico o un presidio sanitario collocati «vicino» alla domanda.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Tre clienti su una strada ai km $0$, $4$ e $10$, pesi $1$, $1$ e $3$. Dove sta il baricentro (distanza quadratica pesata)?
$x = 4{,}67$, la media semplice
$x = 6{,}8$
$x = 10$
$x = 5$
Spiegazione. $(1\cdot 0 + 1\cdot 4 + 3\cdot 10)/5 = 34/5 = 6{,}8$: a differenza della mediana dipende da quanto sono lontani i punti, non solo da che parte stanno.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Tre clienti su una strada ai km $0$, $4$ e $10$, pesi $1$, $1$ e $3$. Dove sta la localizzazione minimax (distanza massima minima)?
$x = 10$
$x = 6{,}8$
$x = 4$
$x = 5$
Spiegazione. Il punto medio dei clienti estremi, $(0 + 10)/2 = 5$, qualunque siano i pesi: tre obiettivi ragionevoli danno $10$, $6{,}8$ e $5$.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Tre clienti su una strada ai km $0$, $4$, $10$, pesi $1$, $1$, $3$: Weber (somma delle distanze pesate) dà $x = 10$. Perché spostarsi a sinistra di $\delta$ da $10$ peggiora?
I primi due risparmiano $2\delta$, il terzo paga $3\delta$
Tutti e tre i clienti pagano di più
Lì la funzione di costo è costante
La strada finisce al km 10
Spiegazione. Spostandosi a sinistra si accorciano le distanze dei due clienti a sinistra (peso 2 in tutto) e si allunga quella del cliente di peso 3: saldo $+\delta$. L'ottimo è la mediana pesata.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Caso di studio: nel codice gurobipy ogni distanza è una variabile $d_k$ con `dx[k]**2 + dy[k]**2 <= d[k]*d[k]`. Che tipo di vincolo è?
Un vincolo lineare in $d_k$
Un vincolo bilineare non convesso
Un vincolo conico convesso
Un vincolo funzionale su un logaritmo
Spiegazione. $\sqrt{d_x^2 + d_y^2} \le d_k$ è un cono del secondo ordine: convesso, gestito da Gurobi senza `NonConvex`; minimizzare $\sum_kw_kd_k$ spinge ogni $d_k$ giù fino alla distanza vera.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Caso di studio: dodici quartieri, e la stazione deve stare entro $r = 2$ km dalla cabina elettrica in $(7, 6)$. Come si scrive?
$(x - 7)^2 + (y - 6)^2 \le 4$
$|x - 7| + |y - 6| = 2$
$x \le 7$ e $y \le 6$, un rettangolo
Come penalità nell'obiettivo
Spiegazione. Un disco intorno alla cabina è una regione convessa, quindi il Weber vincolato resta convesso; il vincolo è una disuguaglianza quadratica.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Caso di studio: come usa il modello minimax le variabili di distanza $d_k$?
Minimizza $\sum_kw_kd_k$
Minimizza $\sum_kd_k^2$
Fissa ogni $d_k$ allo stesso valore
Minimizza $z$, con $d_k \le z$
Spiegazione. Stesse distanze coniche di Weber, ma l'obiettivo è un'ausiliaria $z$ limitata dal basso da ogni distanza: si minimizza la distanza più grande.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Risultati del caso: Weber $(4{,}886; 5{,}310)$ con media $3{,}344$ km e massimo $6{,}314$ km; minimax $(5{,}496; 5{,}029)$ con media $3{,}391$ km e massimo $5{,}680$ km. Come si legge lo spostamento del punto minimax?
Un errore: i due dovrebbero coincidere
Si sposta verso i quartieri periferici
Si sposta verso il quartiere più popoloso
Si sposta sulla cabina elettrica
Spiegazione. Il punto minimax si sposta di oltre mezzo km verso sud-est per proteggere i quartieri periferici, tagliando la distanza massima di $0{,}63$ km con un piccolo costo in distanza media.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Risultati del caso: il Weber vincolato a stare entro 2 km dalla cabina sta sul bordo del disco e costa $+0{,}2\%$ di distanza totale. Qual è la lezione manageriale?
Il vincolo andrebbe tolto
La cabina è collocata male
Il modello vincolato è inammissibile
Un vincolo temuto può costare poco
Spiegazione. Il vincolo è attivo (ottimo sul bordo) ma costa pochissimo: scoprirlo è un risultato importante quanto l'ottimo stesso.
Localizzazione continua di una struttura in $(x, y)$ che serve i quartieri $i$ in $(a_i, b_i)$ con pesi $w_i$ (popolazione). Frontiera efficienza–equità del caso: tetto $D = 5{,}680$ km dà media $3{,}391$, $D = 5{,}997$ dà $3{,}351$, $D = 6{,}314$ dà $3{,}344$. Che cosa significa una frontiera così piatta?
L'equità costa pochissimo in efficienza
Efficienza ed equità sono in forte conflitto
La soluzione minimax è inammissibile
La distanza media non dipende dal tetto
Spiegazione. Garantire $0{,}63$ km in meno al quartiere più lontano costa solo $47$ m di distanza media: la soluzione equa è «quasi gratis»; una frontiera ripida segnalerebbe un vero conflitto.
Localizzazione continua con la distanza quadratica pesata $\sum_iw_i[(x - a_i)^2 + (y - b_i)^2]$ ($w_i > 0$ pesi, $(a_i, b_i)$ coordinate dei quartieri). Quale affermazione è corretta?
L'ottimo è la mediana pesata
L'ottimo non ha forma chiusa
Il baricentro pesato
L'ottimo è il centro del cerchio minimo
Spiegazione. L'obiettivo è una quadratica strettamente convessa; annullando il gradiente, $\sum_iw_i(x - a_i) = 0$, si ottiene il baricentro (e analogamente per $y$): l'unico dei tre obiettivi con forma chiusa.
10. Ricarica di veicoli elettrici con profilo regolare (18)
Nella ricarica notturna a costo minimo il prelievo totale sale fino a 103,4 kW e cambia fino a 54,9 kW da un'ora all'altra. Che cosa aggiunge la variante QP?
Un vincolo sul picco massimo di prelievo
Una penalità quadratica sui salti orari del prelievo totale
Variabili binarie di accensione dei caricatori
Un costo fisso per ogni veicolo collegato
Spiegazione. La variante QP aggiunge all'obiettivo $\gamma \sum_t (z_t - z_{t-1})^2$: penalizza ogni variazione del prelievo, non solo il picco.
Ricarica EV con profilo regolare: che cosa la distingue dal peak shaving del modello lineare?
Il peak shaving è un QP, il profilo regolare invece un LP
Il profilo regolare ignora del tutto il carico di base
Il peak shaving penalizza ogni rampa, il QP solo il massimo
Il peak shaving guarda solo il massimo, il QP ogni rampa
Spiegazione. Il peak shaving lineare minimizza il massimo del prelievo; il termine quadratico addolcisce tutte le rampe, comprese quelle lontane dal picco.
Nel modello di ricarica con profilo regolare, quale dato si aggiunge a quelli del modello lineare?
Il peso $\gamma$ dei salti del prelievo totale
Il prezzo orario dell'energia in ogni ora della notte
La potenza massima del caricatore di ogni veicolo
Il rendimento di carica $\eta$ dei veicoli
Spiegazione. Prezzi, potenze, disponibilità, energia, carico di base, contatore e rendimento sono quelli del caso lineare; si aggiunge solo $\gamma$ (€ per kW$^2$).
Il QP di ricarica penalizza i salti del prelievo *totale* $z_t = b_t + \sum_v x_{vt}$, carico di base compreso. Quale conseguenza ha sul profilo di ricarica?
La ricarica ignora le rampe dell'edificio e segue i prezzi
La ricarica può addolcire anche le rampe del carico di base
Il carico di base diventa una variabile di decisione
Il problema diventa non convesso e serve `NonConvex = 2`
Spiegazione. Poiché $b_t$ entra nei salti, spostare la ricarica nelle ore in cui il carico di base cresce o cala riduce la penalità: la ricarica compensa le rampe dell'edificio.
Il QP di ricarica ha obiettivo $\sum_{v,t} \pi_t x_{vt} + \gamma \sum_t (z_t - z_{t-1})^2$ e vincoli lineari. Quale ipotesi serve perché sia un QP convesso?
Che i prezzi $\pi_t$ siano tutti positivi
Che il contatore $k$ sia maggiore del carico di base
Che le finestre di disponibilità siano contigue
Che il peso $\gamma$ sia non negativo
Spiegazione. Con $\gamma \ge 0$ si somma una funzione convessa (somma di quadrati di funzioni lineari) a un obiettivo lineare; prezzi e finestre non influiscono sulla convessità.
Un veicolo, due ore: $e = 10$ kWh, $\eta = 1$, prezzi $0{,}10$ e $0{,}20$ €/kWh, $\bar p = 12$ kW, carico di base nullo, $\gamma = 0{,}01$. Con $x_1 = 5 + d$ l'obiettivo è $1{,}5 - 0{,}1 d + 4\gamma d^2$. Quanto vale $x_1$ all'ottimo?
$6{,}25$
$10{,}00$
$5{,}00$
$7{,}50$
Spiegazione. Il minimo è in $d = 0{,}1/(8\gamma) = 1/(80\gamma) = 1{,}25$, quindi $x_1 = 6{,}25$ e $x_2 = 3{,}75$.
Stesso esempio (prezzi $0{,}10$ e $0{,}20$, vincolo di energia attivo, entrambe le ore usate). La stazionarietà dà $0{,}10 - 2\gamma(x_2 - x_1) = \lambda = 0{,}20 + 2\gamma(x_2 - x_1)$. Quanto vale il moltiplicatore $\lambda$ del fabbisogno?
$0{,}10$, il prezzo dell'ora economica, per ogni $\gamma$
$0{,}20$, il prezzo dell'ora cara, per ogni $\gamma$
$0{,}15$, la media dei prezzi, per ogni $\gamma \ge 1/400$
$2\gamma$, il doppio del peso della penalità
Spiegazione. Sommando le due uguaglianze $2\lambda = 0{,}30$: $\lambda = 0{,}15$, indipendente da $\gamma$ finché entrambe le ore sono usate ($\gamma \ge 1/400$).
Nell'esempio a due ore l'ottimo interno è $x_1 = 5 + 1/(80\gamma)$. Che cosa succede per $\gamma < 1/400$?
L'ottimo resta comunque $x_1 = 5 + 1/(80\gamma)$
Tutto nell'ora economica: $x_1 = 10$, $x_2 = 0$
Si carica tutto nell'ora cara, la seconda
Il problema diventa inammissibile per il vincolo di energia
Spiegazione. Per $\gamma < 1/400$ la formula darebbe $x_1 > 10$ e quindi $x_2 < 0$: il limite $x_2 \ge 0$ diventa attivo e si carica tutto nell'ora 1, come nel modello lineare.
Lo script di ricarica con profilo regolare scrive l'obiettivo `spesa + gamma * salti`. Che tipo di modello risolve Gurobi?
Un LP, perché i vincoli sono lineari
Un QP convesso
Un NLP non convesso con `NonConvex = 2`
Un MIQP con variabili intere
Spiegazione. La spesa è lineare, `salti` è una somma di quadrati di espressioni lineari, i vincoli sono lineari: un QP convesso, risolto senza parametri speciali.
Ricarica della flotta con $\gamma = 0{,}01$: spesa 24,67 € contro 20,36 € del modello lineare, picco 68,0 kW contro 103,4 kW. Che cosa si osserva sul picco?
Raggiunge il minimo possibile, quello del peak shaving
Supera il limite del contatore nelle ore notturne
Resta uguale a quello del modello lineare
Scende sotto il carico di base dell'edificio
Spiegazione. 68 kW è il picco minimo possibile trovato dal peak shaving lineare: il QP lo raggiunge addolcendo tutte le rampe, con 4,31 € a notte in più.
Il compromesso lineare costo $+\,\rho\,$picco di Modellazione PL arriva al picco di 68 kW spendendo meno del QP con $\gamma = 0{,}01$. Perché il QP spende di più?
Perché il QP usa un contatore più piccolo del modello lineare
Perché il QP non può usare le ore notturne più economiche
Perché il QP addolcisce ogni rampa, non solo il massimo
Perché il QP ha un rendimento di carica peggiore
Spiegazione. Il compromesso lineare guarda solo il massimo del prelievo; il QP penalizza ogni salto orario e sposta la ricarica anche dove non serve a ridurre il picco.
Nel modello lineare i moltiplicatori del fabbisogno dei sei veicoli valgono 0,0842 o 0,0947 €/kWh; nel QP con $\gamma = 0{,}01$ valgono tutti 0,0916. Perché nel QP coincidono?
Perché nel QP i veicoli hanno la stessa finestra di disponibilità
Perché il QP ignora il rendimento di carica
Perché nel QP il vincolo di energia non è attivo
Perché la penalità lega i veicoli attraverso il prelievo totale
Spiegazione. Il termine quadratico dipende solo dalla somma delle potenze: un kWh in più di qualunque veicolo si ottiene ridistribuendo la ricarica di tutti, allo stesso costo marginale.
Frontiera spesa-nervosismo della ricarica: con $\gamma = 0{,}0005$ la spesa sale di 1,15 € e la somma dei salti al quadrato scende da 7.268 a 1.563. Che cosa dice questo tratto della frontiera?
Che i primi addolcimenti costano poco
Che la regolarità costa sempre di più a ogni passo uguale
Che il QP non migliora il profilo
Che la spesa scende al crescere di $\gamma$
Spiegazione. La frontiera è ripida all'inizio: con poco più di un euro a notte la somma dei salti al quadrato si riduce di quasi cinque volte.
Ricarica con $\gamma = 0{,}5$: la spesa arriva a 43,80 € a notte, più del doppio del modello lineare. Perché oltre una certa soglia addolcire costa tanto?
Perché il contatore diventa troppo piccolo per la flotta
Perché con $\gamma$ grande il problema diventa non convesso
Perché per seguire le rampe dell'edificio si carica in ore care
Perché i veicoli caricano più energia del necessario
Spiegazione. Le rampe del mattino e della sera vengono dall'edificio; per compensarle la ricarica deve spostarsi in ore con prezzi alti.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Quanto vale l'utilizzo ottimo $\rho = \lambda/\tilde\mu$?
$100\%$, perché la capacità inutilizzata è uno spreco
Meno del $100\%$: la capacità di riserva tiene corta la coda
Esattamente il $50\%$, qualunque siano i dati
Non è definito, perché il costo diverge
Spiegazione. Nell'esempio svolto $\lambda = 8$, $c = 2$, $h = 4$: $\tilde\mu = 12$, $\rho = 66{,}7\%$; con $\mu = 9$ ($\rho = 89\%$) il costo sale da $32$ a $50$ €/h.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. All'ottimo il margine di sicurezza è $\tilde\mu - \lambda = \sqrt{h\lambda/c}$. Come cresce con la domanda $\lambda$?
Come $\sqrt{\lambda}$: i sistemi grandi richiedono una riserva proporzionalmente minore
Linearmente in $\lambda$: la riserva è una quota fissa della domanda
Come $\lambda^2$: le code esplodono con la domanda
Non dipende da $\lambda$
Spiegazione. Capacità = domanda + margine di sicurezza, e il margine cresce meno che proporzionalmente alla domanda: economie di scala nella riserva (pooling).
Coda M/M/1 (arrivi di Poisson con tasso $\lambda$, servizio esponenziale con tasso $\mu > \lambda$, un servente). Quali formule danno il tempo medio nel sistema $w$ e il numero medio di clienti nel sistema $l$?
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Il marketing promette un tempo medio nel sistema $w = 1/(\mu - \lambda)$ al più pari a $w_{\max}$. Quale vincolo sulla capacità ne segue?
$\mu \le \lambda + 1/w_{\max}$
$\mu \ge \lambda\,w_{\max}$
$\mu \ge 1/w_{\max}$
$\mu \ge \lambda + 1/w_{\max}$
Spiegazione. Da $1/(\mu - \lambda) \le w_{\max}$; il vincolo conta solo quando è più stretto dell'ottimo economico $\tilde\mu$.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Nel caso di studio $\lambda$ è incerto in $[36, 48]$ e l'ottimo calcolato per la domanda nominale è $\tilde\mu = 46{,}58$. Perché dimensionare il sistema su questo valore è pericoloso?
Perché $C(\mu)$ non è convessa con $\lambda$ incerto
Perché con $\lambda = 48 > \tilde\mu$ la coda è instabile
Perché $\tilde\mu$ supera ogni domanda probabile
Perché la formula di $\tilde\mu$ vale solo per $\lambda < 36$
Spiegazione. Con $\mu \le \lambda$ la coda cresce senza limite e il costo diverge. Minimizzare il costo del caso peggiore dà $\mu = 52{,}90$: un premio assicurativo di circa il $13\%$.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Quando la promessa $w \le w_{\max}$ è attiva, $\mu = \lambda + 1/w_{\max}$ e il costo è $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda\,w_{\max}$. Con $c = 3$, $h = 1{,}5$, $\lambda = 42$ e $w_{\max} = 0{,}1$ h, quanto vale $dC/dw_{\max}$?
$-237$ €/h per ora di promessa
$+63$ €/h per ora di promessa
$-300$ €/h per ora di promessa
$-30$ €/h per ora di promessa
Spiegazione. $dC/dw_{\max} = -c/w_{\max}^2 + h\lambda = -3/0{,}01 + 63 = -237$: allentare la promessa fa risparmiare, il numero da dare al marketing prima di firmare lo SLA.
Coda M/M/1 con utilizzo $\rho = \lambda/\mu$ e tempo medio nel sistema $w = 1/(\mu - \lambda)$. Il grafico del «muro dell'utilizzo» mostra $w$ al crescere di $\rho$, con $\mu$ fissato. Che cosa mostra?
Il costo totale scende al crescere di $\rho$
Il tempo di attesa non dipende da $\rho$
Da $\rho = 90\%$ a $\rho = 99\%$ il tempo $w$ si moltiplica per dieci
L'utilizzo ottimo è il $99\%$
Spiegazione. $w = 1/(\mu(1 - \rho))$ esplode come un'iperbole per $\rho \to 1$: saturare le risorse e dare un buon servizio sono in conflitto matematico.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Quale affermazione su $C(\mu)$ per $\mu > \lambda$ è corretta?
È concava, quindi il suo punto stazionario è un massimo
È lineare in $\mu$, quindi l'ottimo sta su un estremo
Non ha minimo su $(\lambda, +\infty)$
Lì è convessa, quindi $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ è il minimo globale
Spiegazione. $C''(\mu) = 2h\lambda/(\mu - \lambda)^3 > 0$; il costo tende a $+\infty$ sia per $\mu \to \lambda^+$ sia per $\mu \to +\infty$.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Per affermare che $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ è la capacità ottima, quali fatti si usano?
La dualità forte degli LP
$C'(\tilde\mu) = 0$, la convessità di $C$ su $(\lambda, +\infty)$ e $\tilde\mu > \lambda$
Che il tasso di arrivo $\lambda$ sia intero
Che l'utilizzo all'ottimo sia del $100\%$
Spiegazione. La derivata si annulla in $\tilde\mu$, che rispetta la condizione di stabilità; la convessità rende il punto stazionario il minimo globale.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Caso di studio: $\lambda = 42$ all'ora, $c = 3$, $h = 1{,}5$: $\tilde\mu = 46{,}58$, utilizzo $90{,}2\%$, tempo medio nel sistema $13{,}1$ minuti. Il marketing propone di promettere un tempo medio di al più $15$ minuti. Quanto costa questa promessa?
Nulla: $13{,}1 < 15$, la promessa non è attiva
Impone $\mu \ge \lambda + 15 = 57$ all'ora
Impone $\mu = \lambda + 4 = 46$, risparmiando
È inammissibile con questa domanda
Spiegazione. Il vincolo $\mu \ge \lambda + 1/w_{\max}$ è già soddisfatto dall'ottimo economico: una promessa più larga di $13{,}1$ minuti è gratis.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Nel modello Gurobi del caso di studio il tempo medio $w$ è una variabile legata a $\mu$ dal vincolo $w(\mu - \lambda) = 1$. Quale parametro richiede?
`FuncNonlinear = 1`, per la funzione $1/x$
`QCPDual = 1`, per ottenere i moltiplicatori
Nessun parametro: il vincolo è lineare
`NonConvex = 2`, perché $w\mu$ è un termine bilineare
Spiegazione. Il prodotto $w\mu$ di due variabili è bilineare (non convesso come uguaglianza); Gurobi lo risolve all'ottimo globale con `NonConvex = 2` e ritrova il $\tilde\mu$ analitico.
Modello di capacità M/M/1: tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Nel caso di studio, stringere la promessa sul tempo medio nel sistema da 12 a 9 minuti costa $1{,}85$ €/h, mentre passare da 3 a 2 minuti costa $28{,}95$ €/h. Che cosa mostra?
Che le promesse brevi costano meno da mantenere
Che il costo della promessa è lineare in $w_{\max}$
Che il prezzo della promessa cresce in modo esplosivo al ridursi di $w_{\max}$
Che la promessa non è mai attiva
Spiegazione. Con la promessa attiva, $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda w_{\max}$: il termine $c/w_{\max}$ fa esplodere il costo marginale per le promesse brevi.
Nel capitolo sulle code, che cosa c'è di nuovo rispetto alla teoria classica delle code?
Nuove formule per la coda M/M/1
La simulazione al posto delle formule
Più serventi invece di uno
La capacità $\mu$ diventa una variabile
Spiegazione. Le formule M/M/1 sono standard; il capitolo tratta il tasso di servizio come una decisione e lo sceglie minimizzando il costo della capacità più quello dell'attesa.
Che cosa significa la notazione M/M/1 nel capitolo del corso sulle code?
Arrivi medi, servizio medio, un'ora di lavoro
Arrivi di Poisson, servizio esponenziale, 1 servente
Più code, più serventi, una linea
Una catena di Markov con un solo stato
Spiegazione. Arrivi markoviani (processo di Poisson), tempi di servizio markoviani (esponenziali) e un solo servente: la coda più semplice, con formule chiuse.
Modello di capacità M/M/1 (arrivi di Poisson, servizio esponenziale, un servente): tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, con ottimo $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Sportello con $\lambda = 8$ clienti/h, $c = 2$ €, $h = 4$ €/h. Quanto valgono $\tilde\mu$ e il costo ottimo?
Modello di capacità M/M/1 (arrivi di Poisson, servizio esponenziale, un servente): tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, con ottimo $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Sportello con $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h, ottimo $\tilde\mu = 12$. Quanto vale il tempo medio nel sistema $w = 1/(\mu - \lambda)$?
$7{,}5$ minuti
$4$ minuti
$12$ minuti
$15$ minuti
Spiegazione. $w = 1/(12 - 8) = 0{,}25$ h $= 15$ minuti; con $\mu = 9$ sarebbe un'ora intera.
Modello di capacità M/M/1 (arrivi di Poisson, servizio esponenziale, un servente): tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, con ottimo $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Sportello con $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h: l'ottimo $\tilde\mu = 12$ costa $32$ €/h. Quanto costa il «più efficiente» $\mu = 9$ (utilizzazione $89\%$)?
$50$ €/h: molto peggio
$18$ €/h: meno caro
$32$ €/h: lo stesso
$26$ €/h: un po' meno caro
Spiegazione. $C(9) = 2\cdot 9 + 4\cdot 8/1 = 18 + 32 = 50$ €/h: l'apparente spreco dell'ottimo (un terzo della capacità inutilizzata) è ciò che tiene corta la coda.
Modello di capacità M/M/1 (arrivi di Poisson, servizio esponenziale, un servente): tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, con ottimo $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Sportello con $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h. Quanto vale l'utilizzazione $\rho = \lambda/\tilde\mu$ all'ottimo?
$100\%$
$89\%$
$66{,}7\%$
$50\%$
Spiegazione. $\tilde\mu = 12$, quindi $\rho = 8/12 = 66{,}7\%$: un terzo della capacità resta in media inutilizzato, per scelta.
Modello di capacità M/M/1 (arrivi di Poisson, servizio esponenziale, un servente): tasso di arrivo $\lambda$, capacità (tasso di servizio) $\mu > \lambda$, costo $c$ per unità di capacità, valore $h$ di un'ora di un cliente nel sistema; si minimizza $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, con ottimo $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Caso di studio ($\lambda = 42$/h, $c = 3$, $h = 1{,}5$): il «muro dell'utilizzazione» traccia $w$ in funzione di $\rho$. Fra $\rho = 90\%$ e $\rho = 99\%$ il tempo di attesa si moltiplica circa per:
$1{,}1$
$10$
$2$
$100$
Spiegazione. $w = 1/(\mu - \lambda) = \rho/(\lambda(1 - \rho))$: $1 - \rho$ passa da $0{,}10$ a $0{,}01$, quindi $w$ cresce di circa dieci volte. Saturare le risorse e servire bene sono in conflitto matematico.
Modello di capacità M/M/1 $\min\ c\mu + h\lambda/(\mu - \lambda)$, $\mu > \lambda$, con la promessa $1/(\mu - \lambda) \le w_{\max}$. Nel caso di studio l'ottimo economico ha $w = 13{,}1$ minuti. Per quali promesse l'ottimo è $\tilde\mu = \lambda + 1/w_{\max}$?
Per ogni $w_{\max}$
Solo per $w_{\max} > 13{,}1$ minuti
Solo se la promessa vincola
Solo quando $c = h$ nel modello
Spiegazione. Se $w_{\max} \ge 13{,}1$ min l'ottimo economico mantiene già la promessa e $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ non cambia; la formula $\lambda + 1/w_{\max}$ richiede l'ipotesi che il vincolo sia attivo.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\sum_j w_j^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Perché così si massimizza il margine?
La distanza fra gli iperpiani $\mathbf w'\mathbf x + b = \pm 1$ è $2/\|\mathbf w\|$
La distanza fra gli iperpiani $\mathbf w'\mathbf x + b = \pm 1$ è $\|\mathbf w\|$
Perché l'intercetta $b$ è una variabile libera
Perché le etichette sono $\pm 1$ e si semplificano
Spiegazione. Un $\|\mathbf w\|$ più piccolo vuol dire un margine più largo; i vincoli tengono ogni punto dalla sua parte, ad almeno un'unità nella scala di $\mathbf w$.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Che cosa significa $\tilde\xi_i > 1$ per l'osservazione $i$?
Sta esattamente sul margine
È un support vector con $\alpha_i = 0$
Sta dal lato sbagliato dell'iperpiano
È classificata bene oltre il margine
Spiegazione. $0 < \xi_i \le 1$ è una violazione del margine dal lato giusto; $\xi_i > 1$ mette il punto dal lato sbagliato dell'iperpiano (classificato male).
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Qual è l'effetto di un $C$ piccolo?
Un margine stretto e zero errori di addestramento
Un margine largo, accettando molti punti al suo interno
Un modello inammissibile
Nessun effetto sulla larghezza del margine
Spiegazione. $C$ è il prezzo delle violazioni: un $C$ piccolo compra un margine largo, un $C$ grande insegue ogni punto di addestramento. Va scelto su dati di validazione.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale ha moltiplicatori $0 \le \alpha_i \le C$. Quale caratteristica del duale apre la porta ai kernel $K(\mathbf x_i, \mathbf x_j)$?
Dipende dai dati solo attraverso i prodotti scalari $\mathbf x_i'\mathbf x_j$
Ha i vincoli di limite $\alpha_i \le C$
È un problema di massimo
Ha un solo vincolo di uguaglianza
Spiegazione. Sostituendo $\mathbf x_i'\mathbf x_j$ con $K(\mathbf x_i, \mathbf x_j)$ si classifica in uno spazio trasformato senza costruirlo.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale ha moltiplicatori $0 \le \alpha_i \le C$. Con il kernel RBF $K(\mathbf x_i, \mathbf x_j) = e^{-\gamma\|\mathbf x_i - \mathbf x_j\|^2}$ e $\gamma = 5$, la frontiera si spezza in isole e 61 punti su 90 sono support vector. Che cosa sta succedendo?
Il QP di addestramento è diventato non convesso
Il modello è troppo semplice (underfitting)
Overfitting: il modello memorizza l'insieme di addestramento
Il kernel non è un kernel valido
Spiegazione. L'addestramento resta un QP convesso: convessità e capacità di generalizzare sono proprietà diverse. $C$ e $\gamma$ si scelgono insieme con la validazione incrociata.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Con classi sbilanciate (pochi cattivi pagatori fra i richiedenti di un prestito) gli scarti delle due classi hanno costi diversi $C_-$ e $C_+$. Come vanno scelti?
Proporzionali alle frequenze delle classi
In modo da riflettere i costi delle due decisioni sbagliate
Sempre uguali fra loro
Massimizzando l'accuratezza sull'insieme di test
Spiegazione. I costi devono rispecchiare le decisioni (un prestito a un cattivo pagatore contro un buon cliente rifiutato): con un costo $10\times$ sui cattivi pagatori nessuno sfugge, al prezzo di qualche falso allarme in più.
Spiegazione. Solo i punti con $\tilde\alpha_i > 0$ (support vector) entrano in $\tilde{\mathbf w}$. I punti con $\tilde\alpha_i = 0$ potrebbero sparire senza cambiare nulla: nel caso di studio 7 support vector su 90.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale ha moltiplicatori $0 \le \alpha_i \le C$. Nel duale i prodotti scalari $\mathbf x_i'\mathbf x_j$ si sostituiscono con un kernel $K(\mathbf x_i, \mathbf x_j)$. Sotto quale condizione l'addestramento resta un QP convesso?
$\gamma < 1$ nel kernel RBF
Le due classi sono bilanciate
$C$ è piccolo
La matrice del kernel $(K(\mathbf x_i, \mathbf x_j))$ è semidefinita positiva
Spiegazione. Con matrice del kernel semidefinita positiva l'obiettivo duale è concavo; la frontiera nello spazio originale può essere curva a piacere.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale ha moltiplicatori $0 \le \alpha_i \le C$. Da quale condizione viene il vincolo duale $\sum_i \alpha_i y_i = 0$?
Dal limite $\alpha_i \le C$
Dalla stazionarietà della lagrangiana nell'intercetta libera $b$
Dalla non negatività degli scarti $\xi_i$
Dal fatto che le classi sono bilanciate
Spiegazione. $\partial L/\partial b = -\sum_i\alpha_iy_i = 0$; la stazionarietà in $\mathbf w$ dà $\mathbf w = \sum_i\alpha_iy_i\mathbf x_i$ e quella in $\xi_i$ il limite $\alpha_i \le C$.
SVM: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\|\mathbf w\|^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ per ogni $i$. Che cosa succede quando le due classi si sovrappongono (nessuna retta le separa)?
L'ottimo ha $\mathbf w = \mathbf 0$
Il modello diventa illimitato
Il modello è inammissibile: servono gli scarti (soft margin)
Gurobi restituisce comunque la retta separatrice migliore
Spiegazione. Nessun iperpiano soddisfa tutti i vincoli, quindi il QP non ha soluzioni ammissibili; il soft margin aggiunge scarti $\xi_i \ge 0$ pagati nell'obiettivo.
Support Vector Regression: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ con $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, cioè gli errori dentro un tubo di larghezza $\varepsilon$ sono gratis. Quali osservazioni determinano la retta stimata?
Solo quelle sul bordo o fuori dal tubo
Tutte le osservazioni allo stesso modo
Solo quelle strettamente dentro il tubo
Solo l'osservazione con $y_i$ più grande
Spiegazione. I punti strettamente dentro il tubo hanno moltiplicatori nulli, come i punti oltre il margine nella SVM; nel caso di studio 14 punti su 40 stanno fuori dal tubo.
Nel capitolo del corso sulle Support Vector Machine, le etichette $y_i \in \{-1, +1\}$ delle osservazioni di addestramento (per esempio cliente affidabile / insolvente) sono:
variabili decisionali binarie del QP
variabili continue fra $-1$ e $+1$
dati osservati, non variabili
moltiplicatori dei vincoli di classificazione
Spiegazione. Le etichette sono dati osservati; le variabili (coefficienti $w_j$, intercetta $b$, scarti $\xi_i$, moltiplicatori $\alpha_i$) sono tutte continue, quindi la SVM resta fra i modelli continui del corso.
Il corso addestra le Support Vector Machine senza librerie di machine learning: ogni classificatore è un QP scritto e risolto con Gurobi. Perché?
Per capire che cosa ottimizza davvero un classificatore
Perché le librerie non gestiscono il kernel
Perché Gurobi è più veloce di ogni libreria di ML
Perché le librerie danno solo ottimi locali
Spiegazione. Lo scopo del capitolo è vedere la SVM come problema di ottimizzazione (un QP convesso con il suo duale e i suoi moltiplicatori), non come scatola nera; velocità o limiti delle librerie non c'entrano.
Una Support Vector Machine è un classificatore binario ottenuto risolvendo un QP. Quale domanda gestionale è un problema di classificazione adatto?
Quanti pani si venderanno domani?
Quale prezzo massimizza il profitto di un concerto?
Quanto conviene produrre in ogni mese?
Questo cliente rimborserà il prestito o sarà insolvente?
Spiegazione. Rischio di credito, abbandono dei clienti, manutenzione predittiva, controllo qualità e frodi sono le applicazioni della dispensa: ogni osservazione riceve una di due etichette. Prevedere una quantità è regressione, scegliere prezzi o piani di produzione è ottimizzazione.
Il capitolo del corso sulle Support Vector Machine dice di «chiudere il cerchio» del corso. In che senso?
Introduce per la prima volta le variabili intere
QP convessi e dualità muovono un classificatore
Sostituisce Gurobi con una libreria di machine learning
Mostra che nel machine learning l'ottimizzazione non serve
Spiegazione. QP convessi, dualità e moltiplicatori, usati per produzione, logistica e finanza, sono il motore della SVM: i support vector si leggono con la complementarietà, come i prezzi ombra.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Due osservazioni: $\mathbf x_1 = (0; 0)$ con $y_1 = -1$ e $\mathbf x_2 = (4; 0)$ con $y_2 = +1$. Quanto valgono $\tilde{\mathbf w}$, $\tilde b$ e il margine $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (1; 0)$, $b = -1$, margine $2$
$\mathbf w = (0{,}5; 0)$, $b = -1$, margine $4$
$\mathbf w = (0{,}25; 0)$, $b = -0{,}5$, margine $8$
$\mathbf w = (0{,}5; 0{,}5)$, $b = -1$, margine $2{,}83$
Spiegazione. Vincoli: $-b \ge 1$ e $4w_1 + b \ge 1$; minimizzando $w_1^2 + w_2^2$ si ha $w_2 = 0$ ed entrambi i vincoli attivi: $b = -1$, $w_1 = 0{,}5$. L'iperpiano $x_1 = 2$ è l'asse del segmento, e il margine $2/0{,}5 = 4$ è proprio la distanza fra i due punti.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Hard margin con $n$ osservazioni e $p$ caratteristiche: $\min\ \tfrac12\sum_j w_j^2$ soggetto a $y_i(\sum_j w_jx_{ij} + b) \ge 1$. Quante variabili e quanti vincoli ha il QP?
$n$ variabili e $p + 1$ vincoli
$p$ variabili e $n + 1$ vincoli
$n + p$ variabili e $n$ vincoli
$p + 1$ variabili e $n$ vincoli
Spiegazione. Le variabili sono i $p$ coefficienti $w_j$ e l'intercetta $b$, tutte libere; c'è un vincolo di classificazione per osservazione. Gli scarti $\xi_i$ (altre $n$ variabili) compaiono solo nel soft margin.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ per ogni $i$. Sotto quale ipotesi sui dati questo QP ha una soluzione ottima?
Le due classi sono linearmente separabili
Le due classi hanno lo stesso numero di punti
Le caratteristiche sono standardizzate
Ci sono più osservazioni che caratteristiche
Spiegazione. Se un iperpiano separa le classi, riscalandolo si ottiene una $(\mathbf w, b)$ ammissibile; l'obiettivo è convesso e limitato inferiormente da $0$, quindi l'ottimo esiste. Senza separabilità l'insieme ammissibile è vuoto: per questo serve il soft margin.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. All'ottimo un'osservazione ha $0 < \tilde\xi_i < 1$. Dove si trova?
Esattamente sulla sua retta di margine
Dal lato sbagliato dell'iperpiano
Dal lato giusto, ma dentro il margine
Ben oltre la sua retta di margine
Spiegazione. $y_i(\mathbf w'\mathbf x_i + b) = 1 - \tilde\xi_i$ sta strettamente fra $0$ e $1$: il punto è classificato bene ma viola il margine. Con $\tilde\xi_i > 1$ sarebbe classificato male, con $\tilde\xi_i = 0$ sul margine o oltre.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Per $(\mathbf w, b)$ fissati, qual è il valore ottimo di ogni scarto $\xi_i$?
$\xi_i = 1 - y_i(\mathbf w'\mathbf x_i + b)$, qualunque sia il segno
$\xi_i = \max\{0,\ y_i(\mathbf w'\mathbf x_i + b) - 1\}$
Spiegazione. $\xi_i$ deve soddisfare $\xi_i \ge 1 - y_i(\mathbf w'\mathbf x_i + b)$ e $\xi_i \ge 0$, e costa $C > 0$: prende il più piccolo valore ammesso, la hinge loss. Il soft margin minimizza quindi $\tfrac12\|\mathbf w\|^2$ più $C$ volte la hinge loss totale.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Caso del rischio di credito (90 clienti, 2 indicatori): $C = 0{,}05$ dà margine $2{,}42$ con 2 errori e 22 punti nel margine; $C = 20$ dà margine $0{,}36$, 0 errori, 3 punti nel margine. $C = 20$ è la scelta migliore?
Sì: non fa errori sull'insieme di addestramento
Sì: un $C$ più grande generalizza sempre meglio
No: il $C$ più piccolo è sempre il migliore
Non necessariamente: $C$ si sceglie su dati di validazione
Spiegazione. Un $C$ grande insegue ogni punto di addestramento (zero errori, margine strettissimo); uno piccolo compra un margine ampio. È il compromesso regolarizzazione–aderenza: $C$ si sceglie su dati di validazione, mai sugli errori di addestramento o sul test set.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Quando il soft margin, per $C$ abbastanza grande, restituisce la soluzione dell'hard margin ($\min\ \tfrac12\|\mathbf w\|^2$ con $y_i(\mathbf w'\mathbf x_i + b) \ge 1$)?
Sempre, qualunque siano i dati
Mai: i due modelli differiscono per ogni $C$
Quando le classi sono linearmente separabili
Solo quando c'è una sola caratteristica, $p = 1$
Spiegazione. Se le classi sono separabili l'hard margin è ammissibile, e per $C$ abbastanza grande pagare uno scarto costa più che restringere il margine: tutti gli $\xi_i = 0$. Con classi sovrapposte l'hard margin è inammissibile e gli scarti restano positivi per ogni $C$.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ soggetto a $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. All'ottimo un'osservazione ha $\tilde\alpha_i = C$. Che cosa dice la complementarietà?
$\tilde\xi_i > 0$: dentro il margine o classificata male
Sta esattamente sulla retta di margine
Sta oltre il margine e non influisce sulla soluzione
Va tolta dall'insieme di addestramento
Spiegazione. Le condizioni KKT organizzano i punti: $\alpha_i = 0$ oltre il margine, $0 < \alpha_i < C$ esattamente sul margine, $\alpha_i = C$ quando il vincolo paga uno scarto $\xi_i > 0$ (dentro il margine, o dal lato sbagliato se $\xi_i > 1$).
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ soggetto a $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. Caso del rischio di credito con $C = 1$: 83 dei 90 clienti hanno $\tilde\alpha_i = 0$. Che cosa succede al classificatore se si tolgono quei 83 punti e si risolve di nuovo?
Cambia completamente, sia $\mathbf w$ sia $b$
Diventa inammissibile per i punti rimasti
Resta lo stesso
Cambia soltanto l'intercetta $b$
Spiegazione. $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$ usa solo i 7 punti con $\tilde\alpha_i > 0$, i support vector; gli altri 83 stanno oltre il margine e potrebbero sparire senza cambiare la soluzione.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ soggetto a $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. Nel caso del rischio di credito il solver riporta valore duale $4{,}7868$ = valore primale $4{,}7868$. Quale risultato garantisce questa uguaglianza?
La dualità debole, che vale per ogni QP
Il trucco del kernel
L'unicità dei support vector
La dualità forte dei QP convessi
Spiegazione. Il soft margin è un QP convesso con vincoli lineari: le KKT sono necessarie e sufficienti e l'ottimo duale ha lo stesso valore del primale. La dualità debole darebbe solo una disuguaglianza.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Il suo duale: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ soggetto a $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. Con un kernel $K(\mathbf x_i, \mathbf x_j)$ al posto di $\mathbf x_i'\mathbf x_j$ (per esempio RBF, $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$), come si classifica un punto nuovo $\mathbf x$?
$\mathrm{sign}(\mathbf w'\mathbf x + b)$ con $\mathbf w$ calcolato nello spazio originale
Spiegazione. Lo spazio trasformato non si costruisce mai: il classificatore usa solo i valori del kernel fra il punto nuovo e i support vector ($\tilde\alpha_i > 0$), pesati con $\tilde\alpha_iy_i$, più l'intercetta.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Con il kernel RBF $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ la SVM ha due iperparametri, $C$ e $\gamma$. Come li sceglie la dispensa?
Prima $\gamma$ sugli errori di addestramento, poi $C$
I valori più grandi che danno zero errori di addestramento
$C$ con la dualità, $\gamma$ con una regola empirica
Insieme, per cross-validation
Spiegazione. $C$ e $\gamma$ interagiscono (entrambi controllano quanto la frontiera segue i punti di addestramento), quindi si scelgono insieme per cross-validation; zero errori di addestramento è il segnale dell'overfitting, non un obiettivo.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Caso «a corona» con kernel RBF: con $\gamma = 5$ la frontiera si spezza in isole e 61 punti su 90 sono support vector, eppure l'addestramento resta un QP convesso. Che cosa mostra?
Convessità e generalizzazione sono cose diverse
Il QP non è più convesso per $\gamma$ grande
Il solver si è fermato in un ottimo locale
Il kernel RBF non è valido per $\gamma > 1$
Spiegazione. Il QP è convesso per ogni kernel valido e il suo ottimo è globale, ma un ottimo globale del problema di addestramento può comunque memorizzare i dati: la generalizzazione si giudica su dati di validazione.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. La classe rara (per esempio i clienti insolventi, $y_i = +1$) costa di più quando è classificata male. Come cambia l'obiettivo nella dispensa?
Spiegazione. Basta pesare in modo diverso gli scarti delle due classi, con $C_+ > C_-$ per la classe i cui errori costano di più; il modello resta un QP convesso.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Caso del rischio di credito: a costi uguali precision $1{,}00$ e recall degli insolventi $0{,}94$; con un costo 10 volte più alto sugli scarti degli insolventi precision $0{,}97$ e recall $1{,}00$. Come si legge il cambiamento?
La frontiera arretra verso la classe dei sani
Il classificatore è peggiorato su ogni misura
La frontiera avanza verso gli insolventi: meno falsi allarmi
Nulla è cambiato: le differenze sono rumore numerico
Spiegazione. Alzare il costo di un insolvente non individuato spinge la frontiera nella zona dei sani: la recall arriva al 100% e la precision scende di poco perché alcuni buoni clienti vengono segnalati.
SVM per la classificazione binaria: osservazioni $\mathbf x_i \in \mathbb R^p$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ liberi). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Nel caso del rischio di credito la recall degli insolventi vale $1{,}00$. Che cosa significa?
Ogni cliente segnalato come insolvente lo è davvero
L'errore di addestramento è nullo
Tutti gli scarti $\xi_i$ sono nulli
Nessun insolvente vero è classificato come affidabile
Spiegazione. Recall = quota degli insolventi veri che il classificatore individua; precision = quota dei clienti segnalati che sono davvero insolventi. Recall 1 vuol dire che nessun insolvente sfugge, eventualmente al prezzo di falsi allarmi.
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ con $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, dove $\xi_i, \xi_i^* \ge 0$. Qual è il ruolo di $\varepsilon$?
Il peso degli errori nella funzione obiettivo
La semiampiezza del tubo degli errori gratis
La pendenza massima ammessa per la retta
La quota di punti ammessi fuori dal tubo
Spiegazione. Gli errori entro $\pm\varepsilon$ dalla stima sono ignorati; pagano solo i punti fuori dal tubo, con $\xi_i$ (sopra) o $\xi_i^*$ (sotto), con peso $C$.
Support Vector Regression su dati prezzo–domanda (40 osservazioni): con tubo $\varepsilon = 8$, 14 punti cadono fuori dal tubo. Che cosa succede al numero di punti fuori se $\varepsilon$ si allarga?
Cresce, perché il tubo è più severo
Resta 14, perché non dipende da $\varepsilon$
Diminuisce: pagano meno punti
Diventa zero per ogni $\varepsilon > 0$
Spiegazione. Un tubo più largo contiene più punti, che vengono ignorati; la stima poggia sui pochi punti rimasti fuori (con $\varepsilon = 8$ la retta era $-10{,}86p + 220{,}32$, contro la vera $-11p + 220$).
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ soggetto a $y_i - (\mathbf w'\mathbf x_i + b) \le \varepsilon + \xi_i$, $(\mathbf w'\mathbf x_i + b) - y_i \le \varepsilon + \xi_i^*$, $\xi_i, \xi_i^* \ge 0$. Di che classe è il problema, e che cosa ne segue?
Un QP convesso: ogni ottimo locale è globale
Un LP: l'ottimo sta in un vertice
Un QP non convesso: serve `NonConvex = 2`
Un NLP con vincoli funzionali
Spiegazione. Obiettivo quadratico convesso ($\tfrac12\|\mathbf w\|^2$ più un termine lineare) e vincoli lineari: un QP convesso, come la SVM soft margin, con un ottimo globale certificabile.
Il duale della SVM soft margin ha obiettivo $\sum_i \alpha_i - \tfrac12 \sum_i\sum_j \alpha_i\alpha_j y_i y_j\, \mathbf x_i'\mathbf x_j$. In che modo dipende dai dati $\mathbf x_i$?
Da ogni coordinata $x_{ij}$ presa separatamente
Solo dalla media di tutte le osservazioni
Solo dalle osservazioni con etichetta $y_i = +1$
Solo tramite i prodotti scalari $\mathbf x_i'\mathbf x_j$
Spiegazione. Il duale dipende dai dati solo tramite i prodotti scalari: sostituendoli con un kernel si ottengono frontiere non lineari con lo stesso QP.
SVM soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$. Su dati separabili, che cosa succede al crescere di $C$?
Il margine si allarga e crescono i punti nel margine
Ci si avvicina all'hard margin, con margine più stretto
La soluzione ottima resta la stessa per ogni valore
Il problema diventa non convesso e servono altri solver
Spiegazione. Con $C$ grande le violazioni costano molto: il modello insegue ogni punto del training set (nel caso di studio zero errori, margine 0,359).
Una panetteria stima le vendite in funzione della temperatura in due modi: minimi scostamenti assoluti (un LP) e minimi quadrati (un QP). Lo storico contiene cinque giorni di sciopero con vendite bassissime. Quale retta stimata si sposta di più a causa loro?
La retta degli scostamenti assoluti (LP)
La retta dei minimi quadrati (QP), che paga gli scostamenti al quadrato
Nessuna delle due si sposta in modo visibile
Entrambe si spostano della stessa quantità
Spiegazione. Uno scostamento di $100$ pesa, al quadrato, quanto diecimila scostamenti di uno: i minimi quadrati vengono trascinati giù, l'LP resta con i dati normali.
Storico della panetteria con cinque giorni di sciopero. Sui 55 giorni normali la retta dei minimi scostamenti assoluti (LP) ha errore medio $13{,}08$ pezzi, quella dei minimi quadrati (QP) $14{,}81$; il QP ristimato *senza* gli scioperi ha intercetta $213{,}58$, da cui l'intercetta LP dista $3{,}81$ e quella QP $11{,}24$. Qual è la lezione?
Il QP è migliore perché usa tutti i dati
Entrambi i metodi richiedono di togliere a mano gli scioperi
Gli scioperi non influenzano nessuna delle due stime
L'LP trova da solo la retta che il QP trova solo dopo la pulizia
Spiegazione. Pagare ogni scostamento una volta sola rende l'LP robusto agli outlier: nessuno deve prima riconoscere e togliere i giorni di sciopero.
Storico della panetteria (60 giorni, 5 giorni di sciopero con una ventina di pezzi venduti): la retta dei minimi quadrati è tirata in basso dagli scioperi, quella dei minimi scostamenti assoluti no. Perché un solo dato anomalo su dieci sposta tanto i minimi quadrati?
Perché i minimi quadrati hanno più variabili
Perché l'LP toglie gli anomali prima di stimare
Perché il QP si risolve con una tolleranza più larga
Perché paga ogni scarto al quadrato
Spiegazione. L'obiettivo quadratico lascia dominare uno scarto grande; l'LP paga ogni scarto una volta sola, quindi la retta resta dove sono i dati normali, senza che nessuno ripulisca lo storico a mano.
$\min\sum_i|r_i|$ con $r_i \ge 0$ e le stesse uguaglianze
$\max\sum_ir_i^2$ con $r_i$ libera e nessun vincolo
Spiegazione. Un residuo libero per osservazione, definito dalla stessa uguaglianza dell'LP, e un obiettivo quadratico: un QP convesso risolto con lo stesso solver.
La regressione robusta di Modellazione PL minimizza la somma degli scarti assoluti (un LP). Che cosa minimizzano i minimi quadrati?
Il massimo degli scarti assoluti
La somma degli scarti al quadrato
La somma pesata degli scarti con pesi $\tau$ e $1-\tau$
Il numero di osservazioni mal previste
Spiegazione. I minimi quadrati minimizzano $\sum_i r_i^2$: un QP convesso; il massimo degli scarti sarebbe un LP minimax, la somma pesata la regressione quantile.
Quale vantaggio dei minimi quadrati rispetto agli scarti assoluti mette in evidenza il capitolo?
Equazioni normali in forma chiusa e la stima della media
La robustezza ai dati anomali dello storico
La possibilità di stimare un quantile qualunque
La selezione automatica delle caratteristiche utili
Spiegazione. Sui dati puliti i minimi quadrati hanno le equazioni normali e stimano la media; robustezza, quantili e selezione sono punti forti dei modelli lineari.
Nel QP dei minimi quadrati $\min \sum_i r_i^2$ con $\sum_j w_j x_{ij} + b + r_i = y_i$, come si dichiarano i residui $r_i$?
Non negativi, come gli scostamenti del modello lineare
Binari, per contare gli errori
Come due variabili non negative $u_i$ e $v_i$ per residuo
Liberi: il quadrato non distingue il segno
Spiegazione. Il quadrato di un residuo non dipende dal suo segno: basta una variabile libera per residuo, senza le due parti positive del modello lineare.
Nelle stesse sette vendite l'ultimo valore passa da 148 a 248. Come cambiano la stima dei minimi quadrati (media) e quella degli scarti assoluti (mediana)?
Restano entrambe invariate, perché i dati sono pochi
La media sale di 14,29, la mediana resta 112
La mediana sale di 100, la media resta uguale
Salgono entrambe di 100/7, cioè di circa 14,29
Spiegazione. La media dipende da ogni valore: sale di $100/7 = 14{,}29$. La mediana dipende solo dall'ordine dei valori e resta 112.
QP dei minimi quadrati con intercetta $b$ e coefficienti $w_j$ liberi. Che cosa dicono le KKT sui residui ottimi $\tilde r_i$?
Che sono tutti nulli tranne al più $p + 1$ di essi
Che sono tutti uguali in valore assoluto
Che sommano a zero e sono ortogonali ai dati
Che sono tutti non negativi all'ottimo
Spiegazione. Stazionarietà rispetto a $b$: $\sum_i \pi_i = 0$; rispetto a $w_j$: $\sum_i \pi_i x_{ij} = 0$; con $\pi_i = 2 r_i$ sono le equazioni normali.
Nel QP dei minimi quadrati il moltiplicatore del vincolo dell'osservazione $i$ vale $\tilde\pi_i = 2\tilde r_i$. Che cosa misura?
Quanto cresce la somma dei quadrati se $y_i$ sale di uno
La probabilità che l'osservazione $i$ sia un dato anomalo
Il numero di osservazioni che stanno sopra la retta
Il peso della caratteristica $i$ nella previsione
Spiegazione. Il moltiplicatore è la derivata del valore ottimo rispetto al termine noto $y_i$: il doppio del residuo. Un dato lontano pesa quanto è lontano.
Nella regressione degli scarti assoluti (LP) i duali valgono $\pm 1/2$ o un valore interno; nei minimi quadrati valgono $2 r_i$. Che conseguenza ha sui dati anomali?
Nessuna: i due modelli pesano gli anomali allo stesso modo
I minimi quadrati ignorano del tutto gli anomali
L'LP dà agli anomali un peso proporzionale allo scarto
Nei minimi quadrati un anomalo pesa in proporzione allo scarto
Spiegazione. Nell'LP conta solo il segno del residuo (peso limitato); nei minimi quadrati il peso cresce con il residuo, e un anomalo lontano tira la retta.
Per il newsvendor serve il quantile $9/13$ della domanda. Partendo dai minimi quadrati (media prevista $128{,}7$, deviazione standard dei residui $9{,}40$, $z = 0{,}5024$), quale quantità si ottiene supponendo residui normali?
$128{,}7$ pezzi
$138{,}1$ pezzi
$133{,}5$ pezzi
$124{,}0$ pezzi
Spiegazione. $128{,}7 + 0{,}5024 \cdot 9{,}40 = 133{,}5$ pezzi; la regressione quantile, senza ipotesi sulla forma degli errori, dà $132{,}1$.
Per arrivare al quantile del newsvendor si somma alla media dei minimi quadrati una scorta $z\sigma$. Quale ipotesi richiede questa strada, e la regressione quantile no?
Che le caratteristiche siano standardizzate
Che i giorni di sciopero siano inclusi
Che il quantile sia la mediana
Che i residui siano normali
Spiegazione. La formula media $+\,z\sigma$ usa il quantile della normale standard: vale se i residui sono normali. La regressione quantile stima il quantile direttamente.
Sul giorno tipo della panetteria (28 gradi, prezzo 3,00, weekend) la media prevista dai minimi quadrati è 128,7 pezzi. Perché non basta produrre 128,7 pezzi?
Perché con $c_u = 9$ e $c_o = 4$ serve il quantile $9/13$, sopra la media
Perché la media dei minimi quadrati è sottostimata di dieci pezzi
Perché il weekend va escluso dalla stima della domanda
Perché la media va sempre arrotondata per difetto
Spiegazione. Con costo di mancanza 9 e di eccesso 4 il frattile critico è $9/13 > 1/2$: conviene produrre più della media, cioè un quantile alto della domanda.
Si sposta verso il basso la domanda del giorno normale più caldo (33,7 gradi). Come reagiscono la retta dei minimi quadrati e quella degli scarti assoluti?
Restano entrambe ferme, qualunque sia lo spostamento
Si spostano entrambe in proporzione allo spostamento
La retta LP si sposta in proporzione, la QP una volta sola
La retta QP si sposta in proporzione, la LP una volta sola
Spiegazione. Nei minimi quadrati la pendenza cambia di circa 0,004 per ogni pezzo; nell'LP conta solo il segno del residuo e la stima resta 211,63 $-$ 3,689 temperatura.
Regressione ridge: all'obiettivo dei minimi quadrati si aggiunge $\lambda \sum_j w_j^2$. Al crescere di $\lambda$ i coefficienti si restringono ma nessuno si annulla esattamente. Perché?
Perché Gurobi arrotonda i coefficienti piccoli
Perché $2\lambda w_j$ si annulla in $w_j = 0$: nessuna spinta fissa
Perché le caratteristiche sono state standardizzate
Perché il problema diventa non convesso per $\lambda$ grande
Spiegazione. Vicino a zero la penalità quadratica non spinge più: il coefficiente si avvicina a zero senza raggiungerlo. Il budget sui valori assoluti ha invece una spinta costante e azzera.
QP dei minimi quadrati senza caratteristiche: $\min \sum_i r_i^2$ con $b + r_i = y_i$. Che cosa dà la stazionarietà rispetto a $b$?
$\sum_i |r_i| = 0$: la stima è la mediana
$r_i = 0$ per ogni osservazione $i$
$\sum_i r_i = 0$: la stima è la media
$b = \max_i y_i$, il valore più alto
Spiegazione. Con $\pi_i = 2r_i$ la stazionarietà rispetto a $b$ dà $\sum_i r_i = 0$: la stima $\tilde b$ è la media dei dati (114,29 nelle sette vendite).
Nel QP dei minimi quadrati i residui $r_i$ sono variabili libere. Che cosa succede se si lasciano con il limite inferiore predefinito di gurobipy ($r_i \ge 0$)?
La retta deve stare sotto tutti i dati: stima distorta
Nulla cambia, perché il quadrato non distingue il segno
Il modello diventa non convesso e serve `NonConvex = 2`
Gurobi si ferma e segnala un errore di sintassi
Spiegazione. Con $r_i \ge 0$ ogni previsione deve essere al più il dato osservato: il modello cambia e la stima non è più quella dei minimi quadrati.
Domande generate (29)
Ogni generatore crea a ogni avvio un'istanza nuova, con numeri diversi: qui alcuni esempi.
2. Richiami: convessità, QP e KKT (2)
Esempio 1 · nlpm-g-qp-kkt · livello facile · dispensa
QP convesso: $\min\ 6x_1^2 + x_2^2$ soggetto a $x_1 + x_2 \ge 20$, $x_1, x_2 \ge 0$. All'ottimo il vincolo è attivo, i limiti no, e vale la stazionarietà della Lagrangiana $L = f + \lambda(20 - x_1 - x_2)$. Quanto valgono $\tilde x_1$ e il moltiplicatore $\lambda$?
$\tilde x_1 = 2{,}86$, $\lambda = 34{,}29$
$\tilde x_1 = 10$, $\lambda = 120$
$\tilde x_1 = 17{,}14$, $\lambda = 34{,}29$
$\tilde x_1 = 2{,}86$, $\lambda = 17{,}14$
Spiegazione. Stazionarietà: $12x_1 = \lambda$ e $2x_2 = \lambda$, quindi $x_1 = \lambda/12$, $x_2 = \lambda/2$; il vincolo attivo dà $\lambda = 34{,}29$, da cui $\tilde x_1 = 2{,}86$, $\tilde x_2 = 17{,}14$. La variabile col coefficiente quadratico minore prende la quota maggiore; $\lambda$ è il costo marginale di un'unità in più di $d$.
Esempio 2 · nlpm-g-qp-kkt · livello facile · dispensa
QP convesso: $\min\ 3x_1^2 + 6x_2^2$ soggetto a $x_1 + x_2 \ge 9$, $x_1, x_2 \ge 0$. All'ottimo il vincolo è attivo, i limiti no, e vale la stazionarietà della Lagrangiana $L = f + \lambda(9 - x_1 - x_2)$. Quanto valgono $\tilde x_1$ e il moltiplicatore $\lambda$?
$\tilde x_1 = 4{,}5$, $\lambda = 27$
$\tilde x_1 = 6$, $\lambda = 18$
$\tilde x_1 = 3$, $\lambda = 36$
$\tilde x_1 = 6$, $\lambda = 36$
Spiegazione. Stazionarietà: $6x_1 = \lambda$ e $12x_2 = \lambda$, quindi $x_1 = \lambda/6$, $x_2 = \lambda/12$; il vincolo attivo dà $\lambda = 36$, da cui $\tilde x_1 = 6$, $\tilde x_2 = 3$. La variabile col coefficiente quadratico minore prende la quota maggiore; $\lambda$ è il costo marginale di un'unità in più di $d$.
Esempio 1 · nlpm-g-kkt-proiezione · livello media · dispensa
QP convesso: $\min\ (x - 4)^2 + (y - 4)^2$ soggetto a $x + y \le 7$, $x, y \ge 0$; $\lambda \ge 0$ è il moltiplicatore KKT di $x + y \le 7$ (Lagrangiana $L = f + \lambda(x + y - 7)$). Quanto valgono l'ottimo e $\lambda$?
$(4; 4)$, $\lambda = 0$
$(3{,}5; 3{,}5)$, $\lambda = 0{,}5$
$(3{,}5; 3{,}5)$, $\lambda = 1$
$(3{,}5; 3{,}5)$, $\lambda = 2$
Spiegazione. Il minimo libero $(4, 4)$ viola $x + y \le 7$, quindi il vincolo è attivo. Stazionarietà: $2(x - 4) + \lambda = 0$, $2(y - 4) + \lambda = 0$, quindi $x = 4 - \lambda/2$, $y = 4 - \lambda/2$; con $x + y = 7$: $\lambda = 1$, ottimo $(3{,}5; 3{,}5)$, entrambe positive (limiti inattivi). Problema convesso: il punto KKT è l'ottimo globale.
Esempio 2 · nlpm-g-kkt-proiezione · livello media · dispensa
QP convesso: $\min\ (x - 3)^2 + (y - 6)^2$ soggetto a $x + y \le 4$, $x, y \ge 0$; $\lambda \ge 0$ è il moltiplicatore KKT di $x + y \le 4$ (Lagrangiana $L = f + \lambda(x + y - 4)$). Quanto valgono l'ottimo e $\lambda$?
$(3{,}5; 0{,}5)$, $\lambda = 5$
$(3; 6)$, $\lambda = 0$
$(0{,}5; 3{,}5)$, $\lambda = 2{,}5$
$(0{,}5; 3{,}5)$, $\lambda = 5$
Spiegazione. Il minimo libero $(3, 6)$ viola $x + y \le 4$, quindi il vincolo è attivo. Stazionarietà: $2(x - 3) + \lambda = 0$, $2(y - 6) + \lambda = 0$, quindi $x = 3 - \lambda/2$, $y = 6 - \lambda/2$; con $x + y = 4$: $\lambda = 5$, ottimo $(0{,}5; 3{,}5)$, entrambe positive (limiti inattivi). Problema convesso: il punto KKT è l'ottimo globale.
3. Il solver per i modelli non lineari (1)
Esempio 1 · nlpm-g-sv-perturbazione-nl · livello facile · dispensa
Un modello gurobipy massimizza $20\log(1 + 1x)$ soggetto a $0 \le x \le b$, con il logaritmo scritto tramite `addGenConstrLog`, quindi il solver non restituisce il duale del limite $x \le b$. Risolvendo con $b = 5$ si ottiene $35{,}8352$; con $b = 5{,}1$ si ottiene $36{,}1658$. Qual è la stima per perturbazione del moltiplicatore di $x \le b$?
$\approx 33{,}06$
$\approx 7{,}17$
$\approx 3{,}31$
$\approx 0{,}33$
Spiegazione. Rapporto incrementale: $(36{,}1658 - 35{,}8352)/0{,}1 = 3{,}31$, vicino alla derivata esatta $20\cdot 1/(1 + 1\cdot 5) = 3{,}33$ (la differenza è la curvatura). Dimenticare di dividere per $0{,}1$ è la svista tipica.
Esempio 2 · nlpm-g-sv-perturbazione-nl · livello facile · dispensa
Un modello gurobipy massimizza $50\log(1 + 1x)$ soggetto a $0 \le x \le b$, con il logaritmo scritto tramite `addGenConstrLog`, quindi il solver non restituisce il duale del limite $x \le b$. Risolvendo con $b = 7$ si ottiene $103{,}9721$; con $b = 7{,}1$ si ottiene $104{,}5932$. Qual è la stima per perturbazione del moltiplicatore di $x \le b$?
$\approx 62{,}11$
$\approx 14{,}85$
$\approx 0{,}62$
$\approx 6{,}21$
Spiegazione. Rapporto incrementale: $(104{,}5932 - 103{,}9721)/0{,}1 = 6{,}21$, vicino alla derivata esatta $50\cdot 1/(1 + 1\cdot 7) = 6{,}25$ (la differenza è la curvatura). Dimenticare di dividere per $0{,}1$ è la svista tipica.
4. Produzione con smoothing quadratico (1)
Esempio 1 · nlpm-g-prodq-scorta · livello facile · dispensa
Produzione con smoothing quadratico, un prodotto e due mesi: domanda $d_1 = 60$ e $d_2 = 100$, costo di giacenza $h = 2$ per unità, capacità abbondante, scorta iniziale nulla e peso $\gamma = 1$ sul salto al quadrato $(x_2 - x_1)^2$. Con $x_1 = d_1 + s_1$ e $x_2 = d_2 - s_1$, quanto vale la scorta ottima $\tilde s_1$?
$\tilde s_1 = 19$
$\tilde s_1 = 20$
$\tilde s_1 = 19{,}5$
$\tilde s_1 = 19{,}75$
Spiegazione. Il salto è $40 - 2s_1$ e l'obiettivo (a meno di costanti) è $h s_1 + \gamma(40 - 2s_1)^2$. Stazionarietà: $h - 4\gamma(40 - 2s_1) = 0$, quindi $\tilde s_1 = 40/2 - h/(8\gamma) = 19{,}75$: si accumula scorta finché il risparmio marginale sulla penalità uguaglia la giacenza.
Esempio 2 · nlpm-g-prodq-scorta · livello facile · dispensa
Produzione con smoothing quadratico, un prodotto e due mesi: domanda $d_1 = 50$ e $d_2 = 110$, costo di giacenza $h = 1$ per unità, capacità abbondante, scorta iniziale nulla e peso $\gamma = 0{,}05$ sul salto al quadrato $(x_2 - x_1)^2$. Con $x_1 = d_1 + s_1$ e $x_2 = d_2 - s_1$, quanto vale la scorta ottima $\tilde s_1$?
$\tilde s_1 = 27{,}5$
$\tilde s_1 = 20$
$\tilde s_1 = 25$
$\tilde s_1 = 30$
Spiegazione. Il salto è $60 - 2s_1$ e l'obiettivo (a meno di costanti) è $h s_1 + \gamma(60 - 2s_1)^2$. Stazionarietà: $h - 4\gamma(60 - 2s_1) = 0$, quindi $\tilde s_1 = 60/2 - h/(8\gamma) = 27{,}5$: si accumula scorta finché il risparmio marginale sulla penalità uguaglia la giacenza.
5. Supply chain con congestione e sostenibilità (2)
Esempio 1 · nlpm-g-sc-due-rotte · livello facile · dispensa
LP di flusso a costo minimo di una supply chain: un mercato chiede $D = 140$ unità, inviate su due rotte con flussi $x_1, x_2 \ge 0$ e vincolo di domanda $x_1 + x_2 \ge D$. La rotta 1 costa $c_1 = 4$ €/unità con capacità $x_1 \le 110$; la rotta 2 costa $c_2 = 10$ €/unità con capacità illimitata. Quanto valgono il costo ottimo e il prezzo ombra del vincolo di domanda (costo di servire un'unità in più)?
costo 740 €, costo marginale 6 €/unità
costo 740 €, costo marginale 4 €/unità
costo 560 €, costo marginale 4 €/unità
costo 740 €, costo marginale 10 €/unità
Spiegazione. La rotta economica è satura ($x_1 = 110$) e il resto va sulla rotta 2: $4\cdot 110 + 10\cdot 30 = 740$ €. L'unità successiva può viaggiare solo sulla rotta 2: il prezzo ombra della domanda è $10$.
Esempio 2 · nlpm-g-sc-due-rotte · livello facile · dispensa
LP di flusso a costo minimo di una supply chain: un mercato chiede $D = 110$ unità, inviate su due rotte con flussi $x_1, x_2 \ge 0$ e vincolo di domanda $x_1 + x_2 \ge D$. La rotta 1 costa $c_1 = 2$ €/unità con capacità $x_1 \le 60$; la rotta 2 costa $c_2 = 3$ €/unità con capacità illimitata. Quanto valgono il costo ottimo e il prezzo ombra del vincolo di domanda (costo di servire un'unità in più)?
costo 270 €, costo marginale 3 €/unità
costo 270 €, costo marginale 1 €/unità
costo 220 €, costo marginale 2 €/unità
costo 270 €, costo marginale 2 €/unità
Spiegazione. La rotta economica è satura ($x_1 = 60$) e il resto va sulla rotta 2: $2\cdot 60 + 3\cdot 50 = 270$ €. L'unità successiva può viaggiare solo sulla rotta 2: il prezzo ombra della domanda è $3$.
Esempio 1 · nlpm-g-sc-congestione · livello media · dispensa
Supply chain con congestione: $D = 235$ unità si ripartiscono su due rotte, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. La rotta 1 (costo unitario $c_1 = 1$, capacità nominale $u_1 = 140$, parametro di congestione $\alpha = 2$) costa $c_1x_1 + \alpha c_1x_1^2/u_1$ €; la rotta 2 costa $c_2 = 6$ €/unità con capacità ampia. Minimizzando il costo totale, qual è la ripartizione ottima $(\tilde x_1; \tilde x_2)$?
$(\tilde x_1; \tilde x_2) = (140; 95)$
$(\tilde x_1; \tilde x_2) = (117{,}5; 117{,}5)$
$(\tilde x_1; \tilde x_2) = (235; 0)$
$(\tilde x_1; \tilde x_2) = (175; 60)$
Spiegazione. All'ottimo i costi marginali sono uguali: $1 + 2\alpha\,1\,x_1/140 = 6$, quindi $x_1 = 175$ e $x_2 = 60$. L'LP puro saturerebbe la rotta 1; dimenticare il fattore 2 della derivata raddoppia $x_1$.
Esempio 2 · nlpm-g-sc-congestione · livello media · dispensa
Supply chain con congestione: $D = 370$ unità si ripartiscono su due rotte, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. La rotta 1 (costo unitario $c_1 = 5$, capacità nominale $u_1 = 200$, parametro di congestione $\alpha = 0{,}5$) costa $c_1x_1 + \alpha c_1x_1^2/u_1$ €; la rotta 2 costa $c_2 = 13$ €/unità con capacità ampia. Minimizzando il costo totale, qual è la ripartizione ottima $(\tilde x_1; \tilde x_2)$?
$(\tilde x_1; \tilde x_2) = (185; 185)$
$(\tilde x_1; \tilde x_2) = (200; 170)$
$(\tilde x_1; \tilde x_2) = (320; 50)$
$(\tilde x_1; \tilde x_2) = (370; 0)$
Spiegazione. All'ottimo i costi marginali sono uguali: $5 + 2\alpha\,5\,x_1/200 = 13$, quindi $x_1 = 320$ e $x_2 = 50$. L'LP puro saturerebbe la rotta 1; dimenticare il fattore 2 della derivata raddoppia $x_1$.
6. Portafoglio di Markowitz (4)
Esempio 1 · nlpm-g-mk-minvar · livello facile · dispensa
Modello di Markowitz con due titoli non correlati di volatilità (deviazione standard del rendimento) $\sigma_1 = 30\%$ e $\sigma_2 = 40\%$. Le quote $x_1, x_2$ del capitale, con $x_1 + x_2 = 1$, minimizzano la varianza del portafoglio (senza vincolo di rendimento). Quanto valgono la quota ottima $\tilde x_1$ e la volatilità $\sigma_p$ del portafoglio (radice della varianza)?
$\tilde x_1 = 50\%$, $\sigma_p = 25\%$
$\tilde x_1 = 57{,}1\%$, $\sigma_p = 24{,}2\%$
$\tilde x_1 = 36\%$, $\sigma_p = 27{,}8\%$
$\tilde x_1 = 64\%$, $\sigma_p = 24\%$
Spiegazione. Annullando la derivata di $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ si ottiene $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: i pesi sono inversamente proporzionali alle varianze (non alle volatilità). La volatilità è minore di quella di entrambi i titoli.
Esempio 2 · nlpm-g-mk-minvar · livello facile · dispensa
Modello di Markowitz con due titoli non correlati di volatilità (deviazione standard del rendimento) $\sigma_1 = 20\%$ e $\sigma_2 = 40\%$. Le quote $x_1, x_2$ del capitale, con $x_1 + x_2 = 1$, minimizzano la varianza del portafoglio (senza vincolo di rendimento). Quanto valgono la quota ottima $\tilde x_1$ e la volatilità $\sigma_p$ del portafoglio (radice della varianza)?
$\tilde x_1 = 50\%$, $\sigma_p = 22{,}4\%$
$\tilde x_1 = 20\%$, $\sigma_p = 32{,}2\%$
$\tilde x_1 = 80\%$, $\sigma_p = 17{,}9\%$
$\tilde x_1 = 66{,}7\%$, $\sigma_p = 18{,}9\%$
Spiegazione. Annullando la derivata di $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ si ottiene $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: i pesi sono inversamente proporzionali alle varianze (non alle volatilità). La volatilità è minore di quella di entrambi i titoli.
Esempio 1 · nlpm-g-mk-portafoglio · livello facile · dispensa
Modello di Markowitz, portafoglio di due titoli con quote del capitale $x_1 = 0{,}5$, $x_2 = 0{,}5$; rendimenti attesi $\mu_1 = 5\%$, $\mu_2 = 12\%$; volatilità $\sigma_1 = 0{,}2$, $\sigma_2 = 0{,}25$; correlazione $\rho = 0{,}75$, quindi $q_{ii} = \sigma_i^2$ e $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. Quanto valgono il rendimento atteso e la varianza $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
rendimento atteso 8,5%, varianza 0,0444
rendimento atteso 8,5%, varianza 0,0513
rendimento atteso 8,5%, varianza 0,0256
rendimento atteso 8,5%, varianza 0,035
Spiegazione. Il rendimento è lineare, $\mu_1 x_1 + \mu_2 x_2$. La varianza ha tre termini: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; la covarianza compare due volte ($q_{12}$ e $q_{21}$).
Esempio 2 · nlpm-g-mk-portafoglio · livello facile · dispensa
Modello di Markowitz, portafoglio di due titoli con quote del capitale $x_1 = 0{,}4$, $x_2 = 0{,}6$; rendimenti attesi $\mu_1 = 8\%$, $\mu_2 = 13\%$; volatilità $\sigma_1 = 0{,}3$, $\sigma_2 = 0{,}15$; correlazione $\rho = -0{,}5$, quindi $q_{ii} = \sigma_i^2$ e $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. Quanto valgono il rendimento atteso e la varianza $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
rendimento atteso 11%, varianza 0,0117
rendimento atteso 11%, varianza 0,0171
rendimento atteso 11%, varianza 0,0225
rendimento atteso 11%, varianza 0,0495
Spiegazione. Il rendimento è lineare, $\mu_1 x_1 + \mu_2 x_2$. La varianza ha tre termini: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; la covarianza compare due volte ($q_{12}$ e $q_{21}$).
Esempio 1 · nlpm-g-mk-correlati · livello media · dispensa
Modello di Markowitz con due titoli di volatilità (deviazione standard del rendimento) $\sigma_1 = 0{,}3$, $\sigma_2 = 0{,}4$ e correlazione $\rho = -0{,}5$. Le quote $x_1 + x_2 = 1$ minimizzano la varianza del portafoglio $\sum_i\sum_j q_{ij}x_ix_j$, con covarianza $q_{12} = \rho\sigma_1\sigma_2$ (senza vincolo di rendimento; all'ottimo $x_1, x_2 > 0$). Quanto valgono $\tilde x_1$ e la varianza minima $\sigma_p^2$?
$\tilde x_1 = 59{,}5\%$, $\sigma_p^2 = 0{,}0292$
$\tilde x_1 = 76{,}9\%$, $\sigma_p^2 = 0{,}0405$
$\tilde x_1 = 64\%$, $\sigma_p^2 = 0{,}03$
$\tilde x_1 = 40{,}5\%$, $\sigma_p^2 = 0{,}0424$
Spiegazione. Con la correlazione $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0{,}5946$; la varianza è $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ in quel peso. Ignorare $\rho$ o sbagliarne il segno dà il peso sbagliato.
Esempio 2 · nlpm-g-mk-correlati · livello media · dispensa
Modello di Markowitz con due titoli di volatilità (deviazione standard del rendimento) $\sigma_1 = 0{,}2$, $\sigma_2 = 0{,}4$ e correlazione $\rho = -0{,}25$. Le quote $x_1 + x_2 = 1$ minimizzano la varianza del portafoglio $\sum_i\sum_j q_{ij}x_ix_j$, con covarianza $q_{12} = \rho\sigma_1\sigma_2$ (senza vincolo di rendimento; all'ottimo $x_1, x_2 > 0$). Quanto valgono $\tilde x_1$ e la varianza minima $\sigma_p^2$?
$\tilde x_1 = 25\%$, $\sigma_p^2 = 0{,}085$
$\tilde x_1 = 87{,}5\%$, $\sigma_p^2 = 0{,}0288$
$\tilde x_1 = 80\%$, $\sigma_p^2 = 0{,}0256$
$\tilde x_1 = 75\%$, $\sigma_p^2 = 0{,}025$
Spiegazione. Con la correlazione $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0{,}75$; la varianza è $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ in quel peso. Ignorare $\rho$ o sbagliarne il segno dà il peso sbagliato.
Esempio 1 · nlpm-g-mk-due-titoli-r · livello complessa · dispensa
Markowitz con due titoli: rendimenti attesi $\mu_1 = 16\%$, $\mu_2 = 6\%$; volatilità $\sigma_1 = 27\%$, $\sigma_2 = 14\%$; correlazione $\rho = -0{,}2$. Si minimizza la varianza del portafoglio $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ con $x_1 + x_2 = 1$, $x \ge 0$ e rendimento atteso almeno $\bar r = 12\%$. Quanto valgono la quota ottima $x_1$ e la volatilità del portafoglio?
$x_1 = 60\%$, volatilità $16{,}05\%$
$x_1 = 60\%$, volatilità $21{,}8\%$
$x_1 = 25{,}2\%$, volatilità $11{,}29\%$
$x_1 = 60\%$, volatilità $17{,}14\%$
Spiegazione. Quota di minima varianza senza il vincolo di rendimento: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 25{,}2\%$, con rendimento $8{,}52\%$. È sotto $\bar r$, quindi il vincolo morde: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ dà $x_1 = 60\%$. Volatilità $16{,}05\%$.
Esempio 2 · nlpm-g-mk-due-titoli-r · livello complessa · dispensa
Markowitz con due titoli: rendimenti attesi $\mu_1 = 14\%$, $\mu_2 = 8\%$; volatilità $\sigma_1 = 19\%$, $\sigma_2 = 8\%$; correlazione $\rho = 0$. Si minimizza la varianza del portafoglio $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ con $x_1 + x_2 = 1$, $x \ge 0$ e rendimento atteso almeno $\bar r = 12\%$. Quanto valgono la quota ottima $x_1$ e la volatilità del portafoglio?
$x_1 = 66{,}7\%$, volatilità $12{,}94\%$
$x_1 = 66{,}7\%$, volatilità $15{,}33\%$
$x_1 = 15{,}1\%$, volatilità $7{,}37\%$
$x_1 = 33{,}3\%$, volatilità $8{,}28\%$
Spiegazione. Quota di minima varianza senza il vincolo di rendimento: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 15{,}1\%$, con rendimento $8{,}9\%$. È sotto $\bar r$, quindi il vincolo morde: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ dà $x_1 = 66{,}7\%$. Volatilità $12{,}94\%$.
7. Pricing e revenue management (2)
Esempio 1 · nlpm-g-pricing-ottimo · livello facile · dispensa
Modello di pricing: si scelgono il prezzo $p$ e la quantità venduta $q$ per massimizzare il profitto $(p - c)\,q$ soggetto a $q \le d(p) = 1100 - 5p$ (domanda) e $q \le k$ (capacità), con costo marginale $c = 66$ € e $k = 405$. Quanto valgono il prezzo ottimo $p^*$ e il profitto ottimo?
$p^* = 143$ €, profitto 29645 €
$p^* = 110$ €, profitto 17820 €
$p^* = 139$ €, profitto 29565 €
$p^* = 187$ €, profitto 19965 €
Spiegazione. Senza capacità $p^\circ = (a/b + c)/2 = 143$ con $q^\circ = 385 \le k$: il vincolo di capacità non è attivo e $p^* = p^\circ$.
Esempio 2 · nlpm-g-pricing-ottimo · livello facile · dispensa
Modello di pricing: si scelgono il prezzo $p$ e la quantità venduta $q$ per massimizzare il profitto $(p - c)\,q$ soggetto a $q \le d(p) = 1080 - 4p$ (domanda) e $q \le k$ (capacità), con costo marginale $c = 32$ € e $k = 416$. Quanto valgono il prezzo ottimo $p^*$ e il profitto ottimo?
$p^* = 166$ €, profitto 55744 €
$p^* = 151$ €, profitto 49504 €
$p^* = 135$ €, profitto 42848 €
$p^* = 150$ €, profitto 49088 €
Spiegazione. Senza capacità $p^\circ = (a/b + c)/2 = 151$ con $q^\circ = 476 > k$: la capacità morde, e il prezzo che vende esattamente $k$ è $p^* = (a - k)/b = 166$.
Esempio 1 · nlpm-g-pricing-posto · livello media · dispensa
Modello di pricing: si scelgono il prezzo $p$ e la quantità venduta $q$ per massimizzare $(p - c)\,q$ soggetto a $q \le d(p) = 1100 - 5p$ e $q \le k$, con $c = 66$ € e $k = 235$; all'ottimo il vincolo di capacità è attivo. Sia $\Pi(k)$ il profitto ottimo in funzione della capacità. Quanto vale $d\Pi/dk$, il valore di un'unità di capacità in più?
126 €
107 €
13 €
60 €
Spiegazione. Con $p^* = (a - k)/b = 173$ il profitto è $(p^* - c)\,k$, e $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 60$. Il margine pieno $p^* - c$ dimentica che, per riempire il posto in più, il prezzo scende per tutti.
Esempio 2 · nlpm-g-pricing-posto · livello media · dispensa
Modello di pricing: si scelgono il prezzo $p$ e la quantità venduta $q$ per massimizzare $(p - c)\,q$ soggetto a $q \le d(p) = 1080 - 4p$ e $q \le k$, con $c = 32$ € e $k = 456$; all'ottimo il vincolo di capacità è attivo. Sia $\Pi(k)$ il profitto ottimo in funzione della capacità. Quanto vale $d\Pi/dk$, il valore di un'unità di capacità in più?
10 €
42 €
-104 €
124 €
Spiegazione. Con $p^* = (a - k)/b = 156$ il profitto è $(p^* - c)\,k$, e $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 10$. Il margine pieno $p^* - c$ dimentica che, per riempire il posto in più, il prezzo scende per tutti.
8. Allocazione del budget pubblicitario (2)
Esempio 1 · nlpm-g-budget-due-canali · livello media · dispensa
Budget pubblicitario: le spese $x_1, x_2 \ge 0$ (migliaia di €) su due canali massimizzano $r_1(x_1) + r_2(x_2)$ con $r_1(x) = 160\log(1 + 0{,}25x)$, $r_2(x) = 180\log(1 + 0{,}25x)$ (logaritmo naturale), soggetto a $x_1 + x_2 \le b = 20$, senza tetti. Quanto valgono l'allocazione ottima e il moltiplicatore $\lambda$ del vincolo di budget (risposta in più per mille € in più)?
Spiegazione. All'ottimo i rendimenti marginali sono uguali: $40/(1 + 0{,}25x_1) = 45/(1 + 0{,}25x_2)$ con $x_1 + x_2 = 20$, quindi $x_1 = 9{,}2$; $\lambda$ è il rendimento marginale comune, $12{,}14$. Ripartire in proporzione ad $a_i k_i$ ignora la saturazione.
Esempio 2 · nlpm-g-budget-due-canali · livello media · dispensa
Budget pubblicitario: le spese $x_1, x_2 \ge 0$ (migliaia di €) su due canali massimizzano $r_1(x_1) + r_2(x_2)$ con $r_1(x) = 70\log(1 + 0{,}2x)$, $r_2(x) = 30\log(1 + 0{,}5x)$ (logaritmo naturale), soggetto a $x_1 + x_2 \le b = 50$, senza tetti. Quanto valgono l'allocazione ottima e il moltiplicatore $\lambda$ del vincolo di budget (risposta in più per mille € in più)?
Spiegazione. All'ottimo i rendimenti marginali sono uguali: $14/(1 + 0{,}2x_1) = 15/(1 + 0{,}5x_2)$ con $x_1 + x_2 = 50$, quindi $x_1 = 34{,}9$; $\lambda$ è il rendimento marginale comune, $1{,}75$. Ripartire in proporzione ad $a_i k_i$ ignora la saturazione.
Esempio 1 · nlpm-g-budget-tetto · livello complessa · dispensa
Budget pubblicitario: le spese $x_1, x_2 \ge 0$ (migliaia di €) massimizzano $r_1(x_1) + r_2(x_2)$, con $r_1(x) = 160\log(1 + 0{,}25x)$ e $r_2(x) = 180\log(1 + 0{,}25x)$ (logaritmo naturale), soggetto a $x_1 + x_2 \le b = 30$ (moltiplicatore $\lambda$) e al tetto $x_1 \le u_1 = 10$ (moltiplicatore $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, con $\mu_2 = 0$. Quanto valgono l'allocazione ottima, $\lambda$ e $\mu_1$?
Spiegazione. Senza tetto i rendimenti marginali sarebbero uguali in $x_1 = 13{,}88 > u_1$: il tetto è attivo, $\tilde x_1 = 10$ e $\tilde x_2 = 20$. Il canale 2 è interno, quindi $\lambda = r_2'(20) = 45/(1 + 0{,}25\cdot 20) = 7{,}5$; il canale 1 dà $\mu_1 = r_1'(10) - \lambda = 11{,}43 - 7{,}5 = 3{,}93$, il valore di mille € di tetto in più.
Esempio 2 · nlpm-g-budget-tetto · livello complessa · dispensa
Budget pubblicitario: le spese $x_1, x_2 \ge 0$ (migliaia di €) massimizzano $r_1(x_1) + r_2(x_2)$, con $r_1(x) = 70\log(1 + 0{,}2x)$ e $r_2(x) = 30\log(1 + 0{,}5x)$ (logaritmo naturale), soggetto a $x_1 + x_2 \le b = 60$ (moltiplicatore $\lambda$) e al tetto $x_1 \le u_1 = 34$ (moltiplicatore $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, con $\mu_2 = 0$. Quanto valgono l'allocazione ottima, $\lambda$ e $\mu_1$?
Spiegazione. Senza tetto i rendimenti marginali sarebbero uguali in $x_1 = 41{,}9 > u_1$: il tetto è attivo, $\tilde x_1 = 34$ e $\tilde x_2 = 26$. Il canale 2 è interno, quindi $\lambda = r_2'(26) = 15/(1 + 0{,}5\cdot 26) = 1{,}07$; il canale 1 dà $\mu_1 = r_1'(34) - \lambda = 1{,}79 - 1{,}07 = 0{,}72$, il valore di mille € di tetto in più.
9. Localizzazione continua di un servizio (2)
Esempio 1 · nlpm-g-loc-weber-1d · livello facile · dispensa
Localizzazione su una strada rettilinea: clienti nelle posizioni $a_i$ con pesi $w_i$: km 2 (peso 4), km 12 (peso 5), km 13 (peso 1), km 16 (peso 5), km 18 (peso 1). Una struttura nella posizione $x$ (km) minimizza la distanza totale pesata $\sum_i w_i |x - a_i|$ (modello di Weber su una retta). Dov'è la posizione ottima $x^*$?
$x^* = 13$ km
$x^* = 10$ km
$x^* = 12$ km
$x^* = 11{,}2$ km
Spiegazione. In una dimensione Weber è la mediana pesata: il punto che lascia almeno metà del peso totale ($16/2$) da ciascun lato, qui il km $12$. Il baricentro ($11{,}2$) è l'ottimo delle distanze al quadrato, il punto medio degli estremi ($10$) quello del minimax.
Esempio 2 · nlpm-g-loc-weber-1d · livello facile · dispensa
Localizzazione su una strada rettilinea: clienti nelle posizioni $a_i$ con pesi $w_i$: km 4 (peso 1), km 9 (peso 3), km 12 (peso 5). Una struttura nella posizione $x$ (km) minimizza la distanza totale pesata $\sum_i w_i |x - a_i|$ (modello di Weber su una retta). Dov'è la posizione ottima $x^*$?
$x^* = 10{,}1$ km
$x^* = 9$ km
$x^* = 12$ km
$x^* = 8$ km
Spiegazione. In una dimensione Weber è la mediana pesata: il punto che lascia almeno metà del peso totale ($9/2$) da ciascun lato, qui il km $12$. Il baricentro ($10{,}1$) è l'ottimo delle distanze al quadrato, il punto medio degli estremi ($8$) quello del minimax.
Esempio 1 · nlpm-g-loc-minimax-2d · livello media · dispensa
Localizzazione minimax nel piano: tre quartieri in $(6; 6)$, $(8; 9)$, $(1; 8)$ (km). La struttura in $(x, y)$ minimizza $z$, la massima distanza euclidea da essa a un quartiere (senza pesi). Quanto valgono il punto ottimo $(x^*; y^*)$ e il valore ottimo $z^*$?
$(x^*; y^*) = (4{,}5; 8{,}5)$, $z^* = 3{,}54$
$(x^*; y^*) = (4{,}5; 7{,}5)$, $z^* = 3{,}81$
$(x^*; y^*) = (5; 7{,}67)$, $z^* = 4{,}01$
$(x^*; y^*) = (4{,}39; 9{,}24)$, $z^* = 3{,}61$
Spiegazione. L'ottimo è il centro del più piccolo cerchio che contiene i tre punti. Il triangolo è ottusangolo: il cerchio che ha per diametro il lato più lungo contiene già il terzo punto, quindi il centro è il punto medio di quel lato e $z^*$ è metà della sua lunghezza, $3{,}54$. Il cerchio per i tre punti sarebbe più grande.
Esempio 2 · nlpm-g-loc-minimax-2d · livello media · dispensa
Localizzazione minimax nel piano: tre quartieri in $(4; 9)$, $(3; 1)$, $(8; 7)$ (km). La struttura in $(x, y)$ minimizza $z$, la massima distanza euclidea da essa a un quartiere (senza pesi). Quanto valgono il punto ottimo $(x^*; y^*)$ e il valore ottimo $z^*$?
$(x^*; y^*) = (4{,}44; 4{,}88)$, $z^* = 4{,}14$
$(x^*; y^*) = (5; 5{,}67)$, $z^* = 5{,}08$
$(x^*; y^*) = (3{,}5; 5)$, $z^* = 4{,}03$
$(x^*; y^*) = (5{,}5; 5)$, $z^* = 4{,}72$
Spiegazione. L'ottimo è il centro del più piccolo cerchio che contiene i tre punti. Il triangolo è acutangolo: nessun cerchio costruito su un lato contiene il terzo punto, quindi l'ottimo è il circocentro, equidistante dai tre quartieri, con $z^* = 4{,}14$. Il baricentro ignora i quartieri estremi.
10. Ricarica di veicoli elettrici con profilo regolare (1)
Esempio 1 · nlpm-g-evq-due-ore · livello media · dispensa
Ricarica EV con profilo regolare, un veicolo e due ore: servono $e = 20$ kWh ($\eta = 1$), prezzi $0{,}1$ e $0{,}2$ €/kWh, limite di potenza abbastanza grande, carico di base nullo, obiettivo $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ con $\gamma = 0{,}05$ e vincolo $x_1 + x_2 \ge 20$. All'ottimo si usano entrambe le ore. Quanto valgono $\tilde x_1$ e il moltiplicatore $\lambda$ del vincolo di energia?
$\tilde x_1 = 10{,}5$, $\lambda = 0{,}15$
$\tilde x_1 = 10{,}25$, $\lambda = 0{,}1$
$\tilde x_1 = 20$, $\lambda = 0{,}1$
$\tilde x_1 = 10{,}25$, $\lambda = 0{,}15$
Spiegazione. Con $x_1 = 10 + d$ l'obiettivo è lineare in $d$ con pendenza $-0{,}1$ più $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, quindi $\tilde x_1 = 10{,}25$. La stazionarietà dà $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, da cui $\lambda = (\pi_1 + \pi_2)/2 = 0{,}15$: il kWh marginale costa la media dei prezzi.
Esempio 2 · nlpm-g-evq-due-ore · livello media · dispensa
Ricarica EV con profilo regolare, un veicolo e due ore: servono $e = 16$ kWh ($\eta = 1$), prezzi $0{,}12$ e $0{,}18$ €/kWh, limite di potenza abbastanza grande, carico di base nullo, obiettivo $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ con $\gamma = 0{,}005$ e vincolo $x_1 + x_2 \ge 16$. All'ottimo si usano entrambe le ore. Quanto valgono $\tilde x_1$ e il moltiplicatore $\lambda$ del vincolo di energia?
$\tilde x_1 = 9{,}5$, $\lambda = 0{,}15$
$\tilde x_1 = 11$, $\lambda = 0{,}15$
$\tilde x_1 = 16$, $\lambda = 0{,}12$
$\tilde x_1 = 9{,}5$, $\lambda = 0{,}12$
Spiegazione. Con $x_1 = 8 + d$ l'obiettivo è lineare in $d$ con pendenza $-0{,}06$ più $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, quindi $\tilde x_1 = 9{,}5$. La stazionarietà dà $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, da cui $\lambda = (\pi_1 + \pi_2)/2 = 0{,}15$: il kWh marginale costa la media dei prezzi.
11. Capacità di servizio e tempi di attesa (4)
Esempio 1 · nlpm-g-code-ottimo · livello facile · dispensa
Capacità di una coda M/M/1: tasso di arrivo $\lambda = 25$ clienti/ora; il tasso di servizio $\mu > \lambda$ (capacità) minimizza $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, dove $c = 4$ €/h per unità di $\mu$, $h = 4$ € per ora passata da un cliente nel sistema e $\lambda/(\mu - \lambda)$ è il numero medio di clienti nel sistema. Quanto valgono $\mu^*$ e $C(\mu^*)$?
Esempio 2 · nlpm-g-code-ottimo · livello facile · dispensa
Capacità di una coda M/M/1: tasso di arrivo $\lambda = 27$ clienti/ora; il tasso di servizio $\mu > \lambda$ (capacità) minimizza $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, dove $c = 3$ €/h per unità di $\mu$, $h = 1$ € per ora passata da un cliente nel sistema e $\lambda/(\mu - \lambda)$ è il numero medio di clienti nel sistema. Quanto valgono $\mu^*$ e $C(\mu^*)$?
Esempio 1 · nlpm-g-code-misure · livello facile · dispensa
Coda M/M/1 (arrivi di Poisson, servizio esponenziale, un servente) con tasso di arrivo $\lambda = 18$ all'ora e tasso di servizio $\mu = 24$ all'ora. Quanto valgono l'utilizzo $\rho$, il tempo medio nel sistema $w$ e il numero medio di clienti nel sistema $l$?
$\rho = 75\%$, $w = 2{,}5$ min, $l = 0{,}75$
$\rho = 75\%$, $w = 10$ min, $l = 3$
$\rho = 75\%$, $w = 180$ min, $l = 0{,}17$
$\rho = 75\%$, $w = 10$ min, $l = 4$
Spiegazione. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ ore $= 10$ minuti e, per la legge di Little, $l = \lambda\, w = \lambda/(\mu - \lambda) = 3$. $1/\mu$ è solo il tempo medio di servizio.
Esempio 2 · nlpm-g-code-misure · livello facile · dispensa
Coda M/M/1 (arrivi di Poisson, servizio esponenziale, un servente) con tasso di arrivo $\lambda = 13$ all'ora e tasso di servizio $\mu = 22$ all'ora. Quanto valgono l'utilizzo $\rho$, il tempo medio nel sistema $w$ e il numero medio di clienti nel sistema $l$?
$\rho = 59{,}1\%$, $w = 6{,}7$ min, $l = 2{,}44$
$\rho = 59{,}1\%$, $w = 86{,}7$ min, $l = 0{,}11$
$\rho = 59{,}1\%$, $w = 6{,}7$ min, $l = 1{,}44$
$\rho = 59{,}1\%$, $w = 2{,}7$ min, $l = 0{,}59$
Spiegazione. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ ore $= 6{,}7$ minuti e, per la legge di Little, $l = \lambda\, w = \lambda/(\mu - \lambda) = 1{,}44$. $1/\mu$ è solo il tempo medio di servizio.
Esempio 1 · nlpm-g-code-promessa · livello media · dispensa
Capacità di una coda M/M/1: tasso di arrivo $\lambda = 16$ clienti/ora; il tasso di servizio $\mu > \lambda$ minimizza $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, con $c = 2$ e $h = 8$; il tempo medio nel sistema è $w = 1/(\mu - \lambda)$ ore. Il marketing promette $w \le w_{\max} = 6$ minuti. Quanto valgono la capacità ottima con la promessa e il suo costo $C$?
$\mu = 26$, $C = 64{,}8$ €/h
$\mu = 26$, $C = 52{,}8$ €/h
$\mu = 24$, $C = 64$ €/h
$\mu = 22$, $C = 65{,}33$ €/h
Spiegazione. Senza promessa $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 24$. La promessa richiede $\mu \ge \lambda + 1/w_{\max} = 16 + 60/6 = 26$ (con $w_{\max}$ in ore), più stretto di $\tilde\mu$: essendo $C$ convessa, l'ottimo sta sul vincolo, con $C = 2\cdot 26 + 8\cdot 16\cdot 6/60 = 64{,}8$ €/h.
Esempio 2 · nlpm-g-code-promessa · livello media · dispensa
Capacità di una coda M/M/1: tasso di arrivo $\lambda = 27$ clienti/ora; il tasso di servizio $\mu > \lambda$ minimizza $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, con $c = 3$ e $h = 1$; il tempo medio nel sistema è $w = 1/(\mu - \lambda)$ ore. Il marketing promette $w \le w_{\max} = 2$ minuti. Quanto valgono la capacità ottima con la promessa e il suo costo $C$?
$\mu = 30$, $C = 99$ €/h
$\mu = 29$, $C = 100{,}5$ €/h
$\mu = 57$, $C = 171{,}03$ €/h
$\mu = 57$, $C = 171{,}9$ €/h
Spiegazione. Senza promessa $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 30$. La promessa richiede $\mu \ge \lambda + 1/w_{\max} = 27 + 60/2 = 57$ (con $w_{\max}$ in ore), più stretto di $\tilde\mu$: essendo $C$ convessa, l'ottimo sta sul vincolo, con $C = 3\cdot 57 + 1\cdot 27\cdot 2/60 = 171{,}9$ €/h.
Esempio 1 · nlpm-g-code-robusto · livello complessa · dispensa
Modello di capacità M/M/1: si sceglie la capacità $\mu$ per minimizzare $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, con $c = 4$ € per unità di capacità e $h = 3$ €/h per cliente nel sistema. Il tasso di arrivo è incerto, $\lambda \in [31, 42]$ all'ora, valore nominale $36{,}5$. Si dimensiona $\mu$ minimizzando il costo nel caso peggiore sull'intervallo. Quanto valgono il $\mu$ robusto, il suo costo nel caso peggiore e il premio rispetto al costo ottimo nominale $C(\tilde\mu(36{,}5), 36{,}5)$?
$\mu = 73{,}5$, costo nel caso peggiore $298$, premio $58{,}6\%$
$\mu = 41{,}73$, costo nel caso peggiore $187{,}86$, premio $0\%$
$\mu = 47{,}61$, costo nel caso peggiore $200{,}3$, premio $6{,}6\%$
$\mu = 47{,}61$, costo nel caso peggiore $212{,}9$, premio $13{,}3\%$
Spiegazione. A $\mu$ fissato il costo cresce con $\lambda$, quindi il caso peggiore è $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 47{,}61$, costo nel caso peggiore $212{,}9$. L'ottimo nominale costa $187{,}86$: il premio assicurativo è del $13{,}3\%$. Dimensionare sul $\tilde\mu = 41{,}73 < 42$ nominale renderebbe instabile la coda in cima all'intervallo.
Esempio 2 · nlpm-g-code-robusto · livello complessa · dispensa
Modello di capacità M/M/1: si sceglie la capacità $\mu$ per minimizzare $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, con $c = 2$ € per unità di capacità e $h = 1$ €/h per cliente nel sistema. Il tasso di arrivo è incerto, $\lambda \in [28, 42]$ all'ora, valore nominale $35$. Si dimensiona $\mu$ minimizzando il costo nel caso peggiore sull'intervallo. Quanto valgono il $\mu$ robusto, il suo costo nel caso peggiore e il premio rispetto al costo ottimo nominale $C(\tilde\mu(35), 35)$?
$\mu = 46{,}58$, costo nel caso peggiore $102{,}33$, premio $18\%$
$\mu = 63$, costo nel caso peggiore $128$, premio $47{,}6\%$
$\mu = 46{,}58$, costo nel caso peggiore $96{,}19$, premio $10{,}9\%$
$\mu = 39{,}18$, costo nel caso peggiore $86{,}73$, premio $0\%$
Spiegazione. A $\mu$ fissato il costo cresce con $\lambda$, quindi il caso peggiore è $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 46{,}58$, costo nel caso peggiore $102{,}33$. L'ottimo nominale costa $86{,}73$: il premio assicurativo è del $18\%$. Dimensionare sul $\tilde\mu = 39{,}18 < 42$ nominale renderebbe instabile la coda in cima all'intervallo.
12. Support Vector Machine (7)
Esempio 1 · nlpm-g-svm-due-punti · livello facile · dispensa
SVM hard margin: $\min \tfrac12\|\mathbf w\|^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, con $\mathbf w \in \mathbb R^2$ e $b$ libero. Due osservazioni: $\mathbf x_1 = (0; 0)$ con etichetta $y_1 = -1$ e $\mathbf x_2 = (2; 2)$ con etichetta $y_2 = +1$. Quanto valgono il $\tilde{\mathbf w}$ ottimo e il margine $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (0{,}25; 0{,}25)$, margine $5{,}657$
$\mathbf w = (0{,}5; 0{,}5)$, margine $2{,}828$
$\mathbf w = (2; 2)$, margine $0{,}707$
$\mathbf w = (0{,}5; 0{,}5)$, margine $1{,}414$
Spiegazione. Entrambi i vincoli sono attivi: $b = -1$ e $\mathbf w'\mathbf x_2 + b = 1$; il $\mathbf w$ di norma minima è parallelo a $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. Il margine $2/\|\mathbf w\| = \|\mathbf x_2\| = 2{,}828$ è la distanza fra i due punti.
Esempio 2 · nlpm-g-svm-due-punti · livello facile · dispensa
SVM hard margin: $\min \tfrac12\|\mathbf w\|^2$ soggetto a $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, con $\mathbf w \in \mathbb R^2$ e $b$ libero. Due osservazioni: $\mathbf x_1 = (0; 0)$ con etichetta $y_1 = -1$ e $\mathbf x_2 = (1; 4)$ con etichetta $y_2 = +1$. Quanto valgono il $\tilde{\mathbf w}$ ottimo e il margine $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (0{,}118; 0{,}471)$, margine $2{,}062$
$\mathbf w = (1; 4)$, margine $0{,}485$
$\mathbf w = (0{,}118; 0{,}471)$, margine $4{,}123$
$\mathbf w = (0{,}059; 0{,}235)$, margine $8{,}246$
Spiegazione. Entrambi i vincoli sono attivi: $b = -1$ e $\mathbf w'\mathbf x_2 + b = 1$; il $\mathbf w$ di norma minima è parallelo a $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. Il margine $2/\|\mathbf w\| = \|\mathbf x_2\| = 4{,}123$ è la distanza fra i due punti.
Esempio 1 · nlpm-g-svm-soft · livello media · dispensa
SVM soft margin: obiettivo $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, dove per $\mathbf w, b$ dati gli slack ottimi sono $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Classificatore candidato $\mathbf w = (0; -2)$, $b = 0$, con $C = 1$; osservazioni $\mathbf x_1 = (1; -2)$, $y_1 = +1$; $\mathbf x_2 = (-1; 2)$, $y_2 = -1$; $\mathbf x_3 = (-1; -2)$, $y_3 = -1$; $\mathbf x_4 = (0; 1)$, $y_4 = +1$. Quanto valgono $\sum_i \xi_i$ e il valore dell'obiettivo?
$\sum_i \xi_i = 6$, obiettivo $8$
$\sum_i \xi_i = 8$, obiettivo $12$
$\sum_i \xi_i = 8$, obiettivo $10$
$\sum_i \xi_i = 2$, obiettivo $4$
Spiegazione. Si calcola $y_i(\mathbf w'\mathbf x_i + b)$ per ogni osservazione: i punti con valore $\ge 1$ sono oltre il margine e non pagano, gli altri pagano $1 - y_i(\mathbf w'\mathbf x_i + b)$. Gli slack sommano $8$ e l'obiettivo è $\tfrac12\cdot 4 + 1\cdot 8 = 10$. Togliere il $\max$ fa sottrarre i punti ben classificati.
Esempio 2 · nlpm-g-svm-soft · livello media · dispensa
SVM soft margin: obiettivo $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, dove per $\mathbf w, b$ dati gli slack ottimi sono $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Classificatore candidato $\mathbf w = (-1; 0)$, $b = 2$, con $C = 2$; osservazioni $\mathbf x_1 = (-2; 1)$, $y_1 = -1$; $\mathbf x_2 = (-2; -2)$, $y_2 = +1$; $\mathbf x_3 = (2; 1)$, $y_3 = -1$; $\mathbf x_4 = (2; -1)$, $y_4 = -1$. Quanto valgono $\sum_i \xi_i$ e il valore dell'obiettivo?
$\sum_i \xi_i = 7$, obiettivo $14{,}5$
$\sum_i \xi_i = 4$, obiettivo $8{,}5$
$\sum_i \xi_i = 7$, obiettivo $15$
$\sum_i \xi_i = 5$, obiettivo $10{,}5$
Spiegazione. Si calcola $y_i(\mathbf w'\mathbf x_i + b)$ per ogni osservazione: i punti con valore $\ge 1$ sono oltre il margine e non pagano, gli altri pagano $1 - y_i(\mathbf w'\mathbf x_i + b)$. Gli slack sommano $7$ e l'obiettivo è $\tfrac12\cdot 1 + 2\cdot 7 = 14{,}5$. Togliere il $\max$ fa sottrarre i punti ben classificati.
Esempio 1 · nlpm-g-svm-margine · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Una SVM addestrata ha $\mathbf w = (1; 1)$ e $b = 5$; le sue rette di margine sono $\mathbf w'\mathbf x + b = \pm 1$. Quanto valgono il margine (la distanza fra le due rette di margine) e la distanza del punto $\mathbf x_0 = (3; -4)$ dall'iperpiano?
margine $1{,}414$, distanza $2{,}828$
margine $1{,}414$, distanza $4$
margine $0{,}707$, distanza $2{,}828$
margine $1$, distanza $2{,}828$
Spiegazione. $\|\mathbf w\| = \sqrt{2} = 1{,}414$: il margine è $2/\|\mathbf w\| = 1{,}414$; la distanza di $\mathbf x_0$ è $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 4/1{,}414 = 2{,}828$. Dimenticare di dividere per $\|\mathbf w\|$ è l'errore tipico.
Esempio 2 · nlpm-g-svm-margine · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Una SVM addestrata ha $\mathbf w = (-2; 4)$ e $b = -3$; le sue rette di margine sono $\mathbf w'\mathbf x + b = \pm 1$. Quanto valgono il margine (la distanza fra le due rette di margine) e la distanza del punto $\mathbf x_0 = (-4; -1)$ dall'iperpiano?
margine $0{,}447$, distanza $0{,}224$
margine $0{,}224$, distanza $0{,}224$
margine $0{,}447$, distanza $1$
margine $0{,}1$, distanza $0{,}224$
Spiegazione. $\|\mathbf w\| = \sqrt{20} = 4{,}472$: il margine è $2/\|\mathbf w\| = 0{,}447$; la distanza di $\mathbf x_0$ è $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 1/4{,}472 = 0{,}224$. Dimenticare di dividere per $\|\mathbf w\|$ è l'errore tipico.
Esempio 1 · nlpm-g-svm-duale-w · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Nel duale del soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) solo tre punti hanno $\tilde\alpha_i > 0$: $\mathbf x_1 = (1; 1)$, $y_1 = +1$, $\tilde\alpha_1 = 1{,}5$; $\mathbf x_2 = (3; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 1{,}5$; $\mathbf x_3 = (-3; 3)$, $y_3 = -1$, $\tilde\alpha_3 = 3$. Quanto vale il $\tilde{\mathbf w}$ ottimo del primale?
$\tilde{\mathbf w} = (-15; 3)$
$\tilde{\mathbf w} = (-3; 15)$
$\tilde{\mathbf w} = (15; -3)$
$\tilde{\mathbf w} = (6; 6)$
Spiegazione. Relazione primale-duale: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, una somma sui soli support vector, col segno delle etichette: $1{,}5\,\mathbf x_1 + 1{,}5\,\mathbf x_2 - 3\,\mathbf x_3 = (15; -3)$. Dimenticare le etichette $y_i$ è l'errore tipico.
Esempio 2 · nlpm-g-svm-duale-w · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Nel duale del soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) solo tre punti hanno $\tilde\alpha_i > 0$: $\mathbf x_1 = (4; 3)$, $y_1 = +1$, $\tilde\alpha_1 = 2$; $\mathbf x_2 = (2; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 2$; $\mathbf x_3 = (3; -2)$, $y_3 = -1$, $\tilde\alpha_3 = 4$. Quanto vale il $\tilde{\mathbf w}$ ottimo del primale?
$\tilde{\mathbf w} = (24; 4)$
$\tilde{\mathbf w} = (0; 20)$
$\tilde{\mathbf w} = (12; 12)$
$\tilde{\mathbf w} = (0; -20)$
Spiegazione. Relazione primale-duale: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, una somma sui soli support vector, col segno delle etichette: $2\,\mathbf x_1 + 2\,\mathbf x_2 - 4\,\mathbf x_3 = (0; 20)$. Dimenticare le etichette $y_i$ è l'errore tipico.
Esempio 1 · nlpm-g-svm-rbf-valore · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Con il kernel RBF (gaussiano) $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ e $\gamma = 0{,}5$, quanto vale $K(\mathbf x, \mathbf z)$ per $\mathbf x = (4; 2)$ e $\mathbf z = (3; 1)$?
$K = 0{,}018$
$K = 0{,}607$
$K = 0{,}368$
$K = 0{,}493$
Spiegazione. $\|\mathbf x - \mathbf z\|^2 = 2$ (la distanza al quadrato, non la distanza), quindi $K = e^{-0{,}5\cdot 2} = 0{,}368$. Punti lontani danno $K$ vicino a 0, punti coincidenti $K = 1$; un $\gamma$ più grande rende il kernel più locale.
Esempio 2 · nlpm-g-svm-rbf-valore · livello facile · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Con il kernel RBF (gaussiano) $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ e $\gamma = 0{,}5$, quanto vale $K(\mathbf x, \mathbf z)$ per $\mathbf x = (4; 3)$ e $\mathbf z = (3; 4)$?
$K = 0{,}368$
$K = 0{,}493$
$K = 0{,}607$
$K = 0{,}018$
Spiegazione. $\|\mathbf x - \mathbf z\|^2 = 2$ (la distanza al quadrato, non la distanza), quindi $K = e^{-0{,}5\cdot 2} = 0{,}368$. Punti lontani danno $K$ vicino a 0, punti coincidenti $K = 1$; un $\gamma$ più grande rende il kernel più locale.
Esempio 1 · nlpm-g-svr-tubo · livello facile · dispensa
Support Vector Regression: gli errori dentro un tubo $|y_i - \hat y_i| \le \varepsilon$ non costano, quelli fuori pagano $|y_i - \hat y_i| - \varepsilon$ (gli scarti $\xi_i$, $\xi_i^*$). La retta stimata è $\hat y = -8x + 210$, con $\varepsilon = 7$; le osservazioni $(x_i; y_i)$ sono (2; 205), (9; 124), (10; 141), (11; 113), (13; 99). Quanti punti cadono fuori dal tubo, e qual è la loro penalità totale $\sum_i(\xi_i + \xi_i^*)$?
$4$ punti fuori, penalità $45$
$1$ punti fuori, penalità $17$
$1$ punti fuori, penalità $45$
$4$ punti fuori, penalità $17$
Spiegazione. Residui $y_i - \hat y_i$: $11$, $-14$, $11$, $-9$, $-7$. Quelli con $|r_i| > 7$ sono 4; ciascuno paga solo la parte oltre il tubo, $|r_i| - 7$, per un totale di $17$. Pagare l'intero residuo dà $45$.
Esempio 2 · nlpm-g-svr-tubo · livello facile · dispensa
Support Vector Regression: gli errori dentro un tubo $|y_i - \hat y_i| \le \varepsilon$ non costano, quelli fuori pagano $|y_i - \hat y_i| - \varepsilon$ (gli scarti $\xi_i$, $\xi_i^*$). La retta stimata è $\hat y = -6x + 240$, con $\varepsilon = 4$; le osservazioni $(x_i; y_i)$ sono (1; 241), (7; 202), (10; 183), (13; 168), (14; 161). Quanti punti cadono fuori dal tubo, e qual è la loro penalità totale $\sum_i(\xi_i + \xi_i^*)$?
$2$ punti fuori, penalità $18$
$3$ punti fuori, penalità $18$
$2$ punti fuori, penalità $6$
$3$ punti fuori, penalità $6$
Spiegazione. Residui $y_i - \hat y_i$: $7$, $4$, $3$, $6$, $5$. Quelli con $|r_i| > 4$ sono 3; ciascuno paga solo la parte oltre il tubo, $|r_i| - 4$, per un totale di $6$. Pagare l'intero residuo dà $18$.
Esempio 1 · nlpm-g-svm-duale-b · livello media · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Una SVM soft margin (moltiplicatori duali $0 \le \alpha_i \le C$) dà $\tilde{\mathbf w} = (0; 1)$. Il punto $\mathbf x_k = (2; 3)$ con etichetta $y_k = -1$ ha $0 < \tilde\alpha_k < C$. Quanto valgono l'intercetta $\tilde b$ e il punteggio $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ di $\mathbf x_0 = (2; 1)$?
$\tilde b = -3$, $f(\mathbf x_0) = -2$
$\tilde b = -4$, $f(\mathbf x_0) = -3$
$\tilde b = 4$, $f(\mathbf x_0) = 5$
$\tilde b = -2$, $f(\mathbf x_0) = -1$
Spiegazione. $0 < \tilde\alpha_k < C$ vuol dire che $\mathbf x_k$ sta esattamente sulla sua retta di margine: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, quindi $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = -4$ (perché $1/y_k = y_k$). Allora $f(\mathbf x_0) = -3$: $\mathbf x_0$ va nella classe $-1$.
Esempio 2 · nlpm-g-svm-duale-b · livello media · dispensa
SVM per la classificazione binaria: osservazioni $\mathbf x_i$ con etichette $y_i \in \{-1, +1\}$, iperpiano $\mathbf w'\mathbf x + b = 0$. Una SVM soft margin (moltiplicatori duali $0 \le \alpha_i \le C$) dà $\tilde{\mathbf w} = (-1; 2)$. Il punto $\mathbf x_k = (-1; -3)$ con etichetta $y_k = -1$ ha $0 < \tilde\alpha_k < C$. Quanto valgono l'intercetta $\tilde b$ e il punteggio $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ di $\mathbf x_0 = (3; 2)$?
$\tilde b = 4$, $f(\mathbf x_0) = 5$
$\tilde b = 5$, $f(\mathbf x_0) = 6$
$\tilde b = -4$, $f(\mathbf x_0) = -3$
$\tilde b = 6$, $f(\mathbf x_0) = 7$
Spiegazione. $0 < \tilde\alpha_k < C$ vuol dire che $\mathbf x_k$ sta esattamente sulla sua retta di margine: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, quindi $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = 4$ (perché $1/y_k = y_k$). Allora $f(\mathbf x_0) = 5$: $\mathbf x_0$ va nella classe $+1$.
13. Regressione ai minimi quadrati (1)
Esempio 1 · nlpm-g-ls-media · livello facile · dispensa
Minimi quadrati senza caratteristiche: $\min \sum_i r_i^2$ soggetto a $b + r_i = y_i$, con $b$ e $r_i$ liberi, sulle cinque osservazioni $y = (145; 130; 130; 151; 81)$. Quanto valgono l'intercetta ottima $\tilde b$ e il moltiplicatore $\tilde\pi$ del vincolo dell'osservazione più grande ($y = 151$)?
$\tilde b = 130$, $\tilde\pi = 42$
$\tilde b = 127{,}4$, $\tilde\pi = 23{,}6$
$\tilde b = 127{,}4$, $\tilde\pi = 47{,}2$
$\tilde b = 130$, $\tilde\pi = 47{,}2$
Spiegazione. La stazionarietà rispetto a $b$ dà $\sum_i r_i = 0$: $\tilde b$ è la media, $127{,}4$. Quella rispetto a $r_i$ dà $\pi_i = 2 r_i$: per $y = 151$ il residuo è $23{,}6$ e $\tilde\pi = 47{,}2$. La mediana $130$ sarebbe l'ottimo degli scarti assoluti.
Esempio 2 · nlpm-g-ls-media · livello facile · dispensa
Minimi quadrati senza caratteristiche: $\min \sum_i r_i^2$ soggetto a $b + r_i = y_i$, con $b$ e $r_i$ liberi, sulle cinque osservazioni $y = (110; 148; 105; 87; 112)$. Quanto valgono l'intercetta ottima $\tilde b$ e il moltiplicatore $\tilde\pi$ del vincolo dell'osservazione più grande ($y = 148$)?
$\tilde b = 112{,}4$, $\tilde\pi = 71{,}2$
$\tilde b = 110$, $\tilde\pi = 76$
$\tilde b = 112{,}4$, $\tilde\pi = 35{,}6$
$\tilde b = 110$, $\tilde\pi = 71{,}2$
Spiegazione. La stazionarietà rispetto a $b$ dà $\sum_i r_i = 0$: $\tilde b$ è la media, $112{,}4$. Quella rispetto a $r_i$ dà $\pi_i = 2 r_i$: per $y = 148$ il residuo è $35{,}6$ e $\tilde\pi = 71{,}2$. La mediana $110$ sarebbe l'ottimo degli scarti assoluti.