26 - Ottimizzazione vincolata: moltiplicatori di Lagrange, dualità e condizioni KKT

Corso Machine Learning Engineer · Modulo 02 · Matematica e statistica · Lezione 11

Obiettivo. Risolvere un problema di minimo quando non sei libero di muoverti dove vuoi. Alla fine sai impostare e risolvere un problema con vincoli di uguaglianza con il lagrangiano, sai enunciare e applicare le quattro condizioni KKT, sai dimostrare la dualità debole e riconoscere quando vale quella forte, e sai ricavare il duale della support vector machine dal suo primale leggendo i vettori di supporto direttamente dai moltiplicatori.

Falso mito da sfatare. «Il moltiplicatore di Lagrange è un numero di servizio: serve a fare i conti e poi si butta.» No: λ è la derivata del valore ottimo rispetto al termine noto del vincolo, cioè il prezzo marginale di quel vincolo. È spesso il numero più interessante del problema, e in una SVM è letteralmente l'elenco dei punti che decidono il confine.

Introduzione

Nella lezione sul gradiente e sulla discesa del gradiente abbiamo imparato a scendere: calcoli ∇f, fai un passo nella direzione opposta, ripeti. Quel metodo presuppone però una cosa che quasi nessun problema di machine learning concede: la libertà di muoverti ovunque.

Guarda i problemi che hai già incontrato o che incontrerai. La PCA della lezione su autovalori, SVD e PCA cerca una direzione di norma 1: senza quel vincolo la varianza proiettata non ha massimo, basta allungare il vettore. La support vector machine cerca il margine più largo a parità di classificazione corretta: il margine da solo è illimitato, sono i vincoli di corretta classificazione a renderlo un problema sensato. La regolarizzazione L2 e L1 limita quanto grandi possono essere i pesi. Una distribuzione di probabilità deve sommare a 1. Un budget non si può sforare.

In tutti questi casi il punto di minimo non è dove il gradiente si annulla. È dove il gradiente non riesce più a farti migliorare restando dentro le regole. Questa lezione costruisce l'apparato che descrive quella situazione, e lo fa fino in fondo: niente «si dimostra che».

Risultato finale di questa lezione. Saprai da dove escono gli α dei vettori di supporto di una SVM, ricavandoli tu dal problema primale e verificandoli su sei punti che puoi disegnare a mano su un foglio a quadretti.

Roadmap della lezione.

1. Vincoli di uguaglianza: perché nel punto ottimo il gradiente dev'essere parallelo a quello del vincolo.
2. Il lagrangiano, e due problemi risolti fino in fondo, uno dei quali è la PCA.
3. Vincoli di disuguaglianza: vincolo attivo o inattivo, e le quattro condizioni KKT che ne derivano.
4. Il duale: la funzione che sta sempre sotto, la dualità debole dimostrata, Slater enunciato.
5. La SVM: il duale ricavato dal primale, con i vettori di supporto come conseguenza.
6. La regolarizzazione come vincolo travestito, e perché il rombo L1 produce zeri esatti.
7. Come si risolvono in pratica: penalizzazione, gradiente proiettato, SLSQP, con i tre risultati confrontati.
8. L'esperimento sulla SVM su sei punti, gli errori tipici e quando i vincoli duri non convengono.

Le otto tappe vanno lette come una catena in cui ogni anello usa il precedente: la tangenza dà il moltiplicatore, il moltiplicatore diventa prezzo, il prezzo diventa disuguaglianza con le KKT, le KKT producono il duale, il duale produce la SVM. Saltare un passaggio significa ritrovarsi con formule che sembrano cadute dal cielo.

Vincoli di uguaglianza: il sentiero sul fianco della collina

L'analogia: il sentiero sul fianco della collina

Immagina una collina e, sul suo fianco, un sentiero tracciato. Non puoi camminare dove vuoi: puoi solo seguire il sentiero. La domanda è: qual è il punto più alto che il sentiero raggiunge?

Non è la cima della collina, a meno di una coincidenza fortunata: la cima quasi certamente sta fuori dal sentiero. E non è nemmeno un punto in cui il terreno è pianeggiante. Nel punto più alto del sentiero il terreno continua a salire — solo che sale perpendicolarmente al sentiero, in una direzione che non puoi prendere.

Prova a disegnare le curve di livello della collina, le linee che uniscono i punti alla stessa quota, come su una carta topografica. Cammina lungo il sentiero. Finché il sentiero attraversa una curva di livello, stai cambiando quota: in una delle due direzioni stai salendo. Il punto più alto è quello in cui il sentiero smette di attraversare le curve di livello e le sfiora: è tangente a una di esse.

Dalla tangenza alla formula

Traduciamo. La quota è una funzione f(x) con x ∈ ℝⁿ; il sentiero è l'insieme dei punti che soddisfano g(x) = 0. Il problema è

max f(x) soggetto a g(x) = 0.

Due fatti di analisi, entrambi già visti: il gradiente ∇f punta nella direzione di massima salita di f, e il gradiente ∇g è perpendicolare alla superficie g(x) = 0 (lungo quella superficie g non cambia, quindi la sua derivata direzionale è nulla, quindi ∇g è ortogonale a ogni direzione che resta sulla superficie).

Ora il ragionamento, che è una dimostrazione per assurdo di due righe. Sia x* il punto ottimo. Supponiamo che ∇f(x*) abbia una componente non nulla lungo il vincolo, cioè che esista una direzione d tangente alla superficie con ∇f(x*)·d > 0. Allora muovendosi di un passo piccolo ε lungo d si resta (al primo ordine) sulla superficie e si guadagna f(x* + εd) ≈ f(x*) + ε·∇f(x*)·d > f(x*). Ma allora x* non era il massimo: contraddizione.

Quindi ∇f(x*) non ha nessuna componente tangente alla superficie: è tutto perpendicolare ad essa. E l'altra direzione perpendicolare alla superficie che conosciamo è ∇g(x*). Due vettori perpendicolari alla stessa superficie (regolare, di dimensione n − 1) sono paralleli. Esiste dunque un numero λ tale che

∇f(x*) = λ ∇g(x*) ∎

Questo numero è il moltiplicatore di Lagrange. Nota bene: non l'abbiamo postulato, l'abbiamo derivato. La condizione di parallelismo dei gradienti non è una regola da memorizzare, è la riscrittura di «non esiste più nessuna direzione ammissibile che migliori il valore».

Il lagrangiano, e due problemi risolti fino in fondo

Il lagrangiano: un trucco per tornare a un problema libero

La condizione ∇f = λ∇g più il vincolo g(x) = 0 formano un sistema di n + 1 equazioni in n + 1 incognite (le n componenti di x più λ). C'è un modo elegante di scriverlo tutto insieme. Definiamo il lagrangiano

L(x, λ) = f(x) − λ·g(x).

Annullando il gradiente di L rispetto a tutte le sue variabili si ottengono esattamente le condizioni che cerchiamo: ∇_x L = ∇f − λ∇g = 0 è il parallelismo, e ∂L/∂λ = −g(x) = 0 è il vincolo. Il trucco è questo: un problema vincolato in n variabili diventa un problema libero in n + 1 variabili, e sui problemi liberi sappiamo già lavorare.

Attenzione a una tentazione: L non va minimizzato rispetto a λ. Rispetto a λ il lagrangiano è lineare, quindi non ha né massimo né minimo; il punto che cerchiamo è un punto di sella. È il motivo per cui una discesa del gradiente ingenua su L in tutte le variabili non converge, e lo vedremo nella sezione sui metodi pratici.

Esempio (a): il rettangolo di perimetro fissato, e il prezzo del vincolo

Massimizzare l'area f(x, y) = x·y con il vincolo g(x, y) = x + y − 10 = 0. In parole: fra tutti i rettangoli di semiperimetro 10, qual è quello di area massima?

Il lagrangiano è L = x·y − λ(x + y − 10). Annulliamo le tre derivate parziali:

∂L/∂x = y − λ = 0, ∂L/∂y = x − λ = 0, ∂L/∂λ = −(x + y − 10) = 0.

Le prime due danno x = y = λ; la terza dà 2λ = 10, cioè λ = 5. L'ottimo è il quadrato x = y = 5, di area f* = 25. Fin qui nulla di sorprendente. La parte interessante è λ = 5.

Che cos'è quel 5? Scriviamo il valore ottimo come funzione del termine noto c del vincolo x + y = c. Rifacendo il conto si trova x = y = c/2 e f*(c) = c²/4. Allora df*/dc = c/2, che per c = 10 vale 5: esattamente il moltiplicatore. Il moltiplicatore è la derivata del valore ottimo rispetto al termine noto: dice quanto vale, al margine, una unità in più di vincolo. In economia si chiama prezzo ombra; in un problema di allocazione dice quale vincolo conviene comprare per primo.

def ottimo_lagrange(c):
    """Massimo di x*y sul vincolo x + y = c: dal lagrangiano, x = y = lambda = c/2."""
    lam = c / 2.0
    return lam, lam, lam

x, y, lam = ottimo_lagrange(10.0)
print(f"ottimo: x = {x:.4f}  y = {y:.4f}  f* = {x * y:.4f}  lambda = {lam:.4f}")

# il moltiplicatore come prezzo marginale: perturbiamo il vincolo di 0.01
passo = 0.01
xd, yd, _ = ottimo_lagrange(10.0 + passo)
salto = xd * yd - x * y
print(f"f*(10.01) - f*(10.00) = {salto:.8f}")
print(f"lambda * 0.01         = {lam * passo:.8f}")
print(f"scarto                = {abs(salto - lam * passo):.2e}")

Output ottenuto (Python 3.14.4, nessun numero casuale):

ottimo: x = 5.0000  y = 5.0000  f* = 25.0000  lambda = 5.0000
f*(10.01) - f*(10.00) = 0.05002500
lambda * 0.01         = 0.05000000
scarto                = 2.50e-05

Cosa fa il codice. Calcola l'ottimo in forma chiusa per un generico c, poi confronta il guadagno vero ottenuto rilassando il vincolo di 0.01 con la previsione λ·0.01. Lo scarto non è errore numerico: è il termine di secondo ordine. Poiché f*(c) = c²/4, lo sviluppo esatto è f*(c + h) − f*(c) = (c/2)·h + h²/4, e con h = 0.01 il secondo addendo vale 0.0001/4, cioè esattamente il numero stampato. Il moltiplicatore è una derivata, quindi una approssimazione lineare: affidabile per perturbazioni piccole del vincolo, non per riscriverlo da capo.

Esempio (b): la PCA è un problema vincolato (e λ è la varianza)

Secondo esempio, meno giocattolo. Data una matrice di covarianza Σ (simmetrica, semidefinita positiva), massimizzare la varianza proiettata f(w) = wᵀΣw con il vincolo g(w) = wᵀw − 1 = 0. È, parola per parola, la prima componente principale della lezione su autovalori, SVD e PCA.

Senza il vincolo il problema non ha soluzione: raddoppiando w la varianza proiettata quadruplica, e si può salire all'infinito. È il vincolo di norma unitaria a rendere la domanda sensata, ed è per questo che la PCA è un problema di ottimizzazione vincolata, non una ricetta di algebra lineare.

Il lagrangiano è L(w, λ) = wᵀΣw − λ(wᵀw − 1). I due gradienti sono ∇_w(wᵀΣw) = 2Σw (vale perché Σ è simmetrica) e ∇_w(wᵀw) = 2w. Annullando: 2Σw − 2λw = 0, cioè

Σ w = λ w.

In parole: il w ottimo è un autovettore di Σ, e il moltiplicatore è il corrispondente autovalore. E poiché sul vincolo wᵀw = 1 il valore obiettivo è wᵀΣw = λ·wᵀw = λ, il moltiplicatore è la varianza spiegata. Per massimizzare si prende l'autovalore più grande. L'equazione agli autovalori della PCA non è un'intuizione geometrica caduta dal cielo: è la condizione del primo ordine di un problema vincolato.

import numpy as np

Sigma = np.array([[4.0, 1.0],
                  [1.0, 2.0]])                     # covarianza inventata, simmetrica

lam, V = np.linalg.eigh(Sigma)                     # eigh: autovalori in ordine crescente
w = V[:, -1] * np.sign(V[0, -1])                   # autovettore dominante, segno fissato
print(f"autovalori: {lam[0]:.6f}  {lam[1]:.6f}")
print(f"w (norma 1): ({w[0]:.6f}, {w[1]:.6f})   w^T w = {w @ w:.6f}")
print(f"w^T Sigma w = {w @ Sigma @ w:.6f}   (deve valere lambda_max)")
print("Sigma w == lambda w ?", np.allclose(Sigma @ w, lam[-1] * w))

# controprova indipendente: forza bruta su tutte le direzioni, un decimo di grado
angoli = np.linspace(0.0, np.pi, 1801)
W = np.column_stack([np.cos(angoli), np.sin(angoli)])
valori = np.einsum("ij,jk,ik->i", W, Sigma, W)
print(f"forza bruta: angolo {np.degrees(angoli[valori.argmax()]):.1f} gradi "
      f"-> w^T Sigma w = {valori.max():.6f}")

Output ottenuto (NumPy 2.3.5, nessun numero casuale):

autovalori: 1.585786  4.414214
w (norma 1): (0.923880, 0.382683)   w^T w = 1.000000
w^T Sigma w = 4.414214   (deve valere lambda_max)
Sigma w == lambda w ? True
forza bruta: angolo 22.5 gradi -> w^T Sigma w = 4.414214

Cosa fa il codice. La prima metà applica il risultato della derivazione: eigh dà gli autovalori di Σ in ordine crescente e gli autovettori in colonna; si prende l'ultimo, gli si fissa il segno (un autovettore e il suo opposto sono entrambi validi) e si verifica che valga davvero Σw = λw. La seconda metà non usa nessun risultato teorico: scorre 1801 direzioni unitarie con np.einsum e tiene la migliore. I due metodi concordano, e la verifica incrociata è il punto: la derivazione con i moltiplicatori non va creduta, va controllata con un metodo che non la usa. Gli autovalori sono 3 ± √2: puoi ricavarli a mano dal polinomio caratteristico λ² − 6λ + 7 = 0 e confrontarli con la stampa.

Vincoli di disuguaglianza e condizioni KKT

Attivo o inattivo: i casi sono due, non uno

Passiamo dai sentieri ai recinti. Un vincolo di disuguaglianza non ti obbliga a stare su una linea: ti chiude dentro una regione. Scriviamo tutti i vincoli nella forma standard

min f(x) soggetto a gᵢ(x) ≤ 0, i = 1, …, m

(una disuguaglianza h(x) ≥ c si riscrive come c − h(x) ≤ 0; è la convenzione di Boyd e Vandenberghe, e conviene adottarla sempre perché fissa il segno dei moltiplicatori).

Nel punto ottimo x* ogni vincolo si trova in uno di due stati, e solo due.

• Inattivo (gᵢ(x*) < 0): il punto ottimo sta dentro al recinto, lontano da quel muro. Se togli il vincolo, non cambia niente. Il muro non spinge: il suo moltiplicatore è zero.
• Attivo (gᵢ(x*) = 0): il punto ottimo è appoggiato al muro. Se non ci fosse il muro, scenderesti oltre. Il muro spinge, e quanto spinge è il valore del moltiplicatore.

Da questa dicotomia segue tutto. Se tutti i vincoli sono inattivi, siamo al minimo libero e ∇f(x*) = 0. Se alcuni sono attivi, quei vincoli si comportano come vincoli di uguaglianza e torniamo al caso precedente — con una differenza fondamentale sul segno.

Le quattro condizioni, una alla volta

Definiamo il lagrangiano con i moltiplicatori μᵢ dei vincoli di disuguaglianza:

L(x, μ) = f(x) + Σᵢ μᵢ gᵢ(x).

Le condizioni di Karush-Kuhn-Tucker sono quattro. Le enunciamo con la frase che le rende memorabili.

1. Stazionarietà: ∇f(x*) + Σᵢ μᵢ ∇gᵢ(x*) = 0. Il gradiente dell'obiettivo è bilanciato dalla spinta dei muri che toccano. È lo stesso parallelismo di prima, scritto per più vincoli insieme.
2. Ammissibilità primale: gᵢ(x*) ≤ 0 per ogni i. La soluzione deve stare dentro il recinto. Banale a dirsi, dimenticata di continuo: un punto che viola i vincoli non è una soluzione, per quanto piccolo sia il valore di f.
3. Ammissibilità duale: μᵢ ≥ 0. Il muro può solo spingere verso dentro, mai tirare verso fuori.
4. Scarto complementare: μᵢ·gᵢ(x*) = 0 per ogni i. O il vincolo tocca, o il suo prezzo è zero. È l'esatta formalizzazione della dicotomia attivo/inattivo: il prodotto di due numeri è nullo se almeno uno dei due lo è.

Perché μ ≥ 0, geometricamente. Prendiamo un solo vincolo attivo. La stazionarietà dice ∇f(x*) = −μ ∇g(x*). Il gradiente ∇g punta nella direzione in cui g cresce, cioè verso l'esterno della regione ammissibile (dove g diventa positiva). Se μ > 0, allora ∇f punta verso l'interno: il modo di far scendere f sarebbe uscire, e il muro lo impedisce. Se invece fosse μ < 0, ∇f punterebbe verso l'esterno: potresti far scendere f rientrando nella regione, restando ammissibile. Ma allora x* non sarebbe il minimo. Il segno non è una convenzione: è l'affermazione che il vincolo stia davvero bloccando la discesa.

Le KKT sono necessarie sotto una condizione di regolarità dei vincoli, e diventano anche sufficienti quando f e i gᵢ sono convessi. Nel caso convesso, quindi, trovare un punto che soddisfa le quattro condizioni significa aver finito: è l'ottimo globale, non uno dei tanti candidati. È il motivo per cui l'ottimizzazione convessa è una disciplina a sé.

Un problema risolto a mano. Minimizzare f(x, y) = x² + y² con x + 2y ≥ 4. In forma standard: g(x, y) = 4 − x − 2y ≤ 0, e L = x² + y² + μ(4 − x − 2y). I casi da esaminare sono due. Caso μ = 0: la stazionarietà dà 2x = 0 e 2y = 0, cioè l'origine; ma g(0, 0) = 4 > 0, l'origine viola il vincolo, caso scartato. Caso g = 0: la stazionarietà dà 2x − μ = 0 e 2y − 2μ = 0, cioè x = μ/2 e y = μ; sostituendo nel vincolo attivo μ/2 + 2μ = 4 si ottiene μ = 8/5 = 1.6 ≥ 0, quindi x* = 0.8, y* = 1.6, f* = 3.2. Entrambe le verifiche passano: è la soluzione.

import numpy as np

def risolvi_kkt(a, c):
    """Minimo di ||v||^2 sotto a . v >= c, cioè g(v) = c - a . v <= 0.

    Esamina i due casi e restituisce (v, mu) del caso che sopravvive."""
    a = np.asarray(a, dtype=float)
    if c <= 0.0:                       # caso mu = 0: il minimo libero è ammissibile
        return np.zeros_like(a), 0.0
    mu = 2.0 * c / (a @ a)             # caso g = 0: stazionarietà 2v = mu*a
    return mu * a / 2.0, mu

a = np.array([1.0, 2.0])
for c in (4.0, -1.0):
    v, mu = risolvi_kkt(a, c)
    g = c - a @ v
    print(f"c = {c:5.1f} -> v* = ({v[0]:.4f}, {v[1]:.4f})  f* = {v @ v:.4f}  "
          f"mu = {mu:.4f}  g(v*) = {g:+.4f}  |mu*g| = {abs(mu * g):.2e}")

Output ottenuto:

c =   4.0 -> v* = (0.8000, 1.6000)  f* = 3.2000  mu = 1.6000  g(v*) = +0.0000  |mu*g| = 0.00e+00
c =  -1.0 -> v* = (0.0000, 0.0000)  f* = 0.0000  mu = 0.0000  g(v*) = -1.0000  |mu*g| = 0.00e+00

Cosa fa il codice. Implementa la discussione dei due casi, non una ricerca numerica: il primo if è il vincolo inattivo, le due righe successive il caso attivo risolto in forma chiusa, e la scelta fra i due è una condizione di ammissibilità, non un parametro. Lo scarto complementare vale zero in entrambi i casi, ma per ragioni diverse: con c = 4 perché g = 0, con c = −1 perché μ = 0. È il senso della condizione: non dice che i due fattori siano piccoli, dice che almeno uno dei due è esattamente nullo. Il confine fra i due regimi è c = 0.

Il duale: la funzione che sta sempre sotto

La funzione duale

Fin qui abbiamo usato il lagrangiano come un sistema di equazioni. Ora ne facciamo una cosa diversa, e più potente. Fissiamo i moltiplicatori μ ≥ 0 e minimizziamo il lagrangiano su tutto x, senza nessun vincolo. Il risultato è un numero, che dipende da μ:

d(μ) = infₓ L(x, μ) = infₓ [ f(x) + Σᵢ μᵢ gᵢ(x) ].

Questa è la funzione duale (dual function). Il problema di massimizzare d(μ) per μ ≥ 0 si chiama problema duale; il problema originale si chiama primale, e il suo valore ottimo si indica con p*.

Un fatto notevole, e gratuito: d è concava comunque siano fatti f e i gᵢ, anche se il primale è orribile. Il motivo è che d è l'estremo inferiore di una famiglia di funzioni affini in μ (per ogni x fissato, L(x, μ) è una retta in μ), e l'inf di funzioni affini è concavo. Quindi il problema duale è sempre un problema di massimizzazione concava, cioè convesso: massimo globale, nessun minimo locale in cui restare incastrati.

Dualità debole, dimostrata in tre righe

Sia x̃ un punto qualsiasi ammissibile per il primale, cioè con gᵢ(x̃) ≤ 0 per ogni i, e sia μ ≥ 0. Allora:

Σᵢ μᵢ gᵢ(x̃) ≤ 0, perché è una somma di prodotti fra numeri non negativi (μᵢ) e numeri non positivi (gᵢ(x̃)).

L(x̃, μ) = f(x̃) + Σᵢ μᵢ gᵢ(x̃) ≤ f(x̃), per il punto precedente.

d(μ) = infₓ L(x, μ) ≤ L(x̃, μ) ≤ f(x̃), perché l'estremo inferiore su tutti gli x è minore o uguale al valore in uno specifico x̃.

La catena vale per ogni x̃ ammissibile, quindi vale anche per il migliore di essi: d(μ) ≤ p*, per ogni μ ≥ 0. ∎

Questa è la dualità debole. In parole: qualunque valore del duale è un limite inferiore garantito del primale. È un risultato pratico, non solo estetico: se stai risolvendo un problema difficile con un metodo che produce soluzioni ammissibili, ogni μ ≥ 0 che ti capita in mano ti dà un certificato del tipo «non potrò mai scendere sotto d(μ)». La differenza p* − d* fra l'ottimo primale e l'ottimo duale si chiama duality gap, ed è sempre ≥ 0.

def duale(mu):
    """d(mu) per min x^2 + y^2 con 4 - x - 2y <= 0.

    Il lagrangiano L = x^2 + y^2 + mu*(4 - x - 2y) è una parabola in (x, y):
    il suo minimo libero è in x = mu/2, y = mu."""
    x, y = mu / 2.0, mu
    return x * x + y * y + mu * (4.0 - x - 2.0 * y)

p_stella = 3.2                                   # ricavato a mano con le KKT
for mu in (0.0, 0.5, 1.0, 1.6, 2.0, 3.0, 4.0):
    d = duale(mu)
    print(f"mu = {mu:4.1f}   d(mu) = {d:7.4f}   d(mu) <= p* ? {d <= p_stella + 1e-12}")

Output ottenuto:

mu =  0.0   d(mu) =  0.0000   d(mu) <= p* ? True
mu =  0.5   d(mu) =  1.6875   d(mu) <= p* ? True
mu =  1.0   d(mu) =  2.7500   d(mu) <= p* ? True
mu =  1.6   d(mu) =  3.2000   d(mu) <= p* ? True
mu =  2.0   d(mu) =  3.0000   d(mu) <= p* ? True
mu =  3.0   d(mu) =  0.7500   d(mu) <= p* ? True
mu =  4.0   d(mu) = -4.0000   d(mu) <= p* ? True

Cosa fa il codice. Il minimo libero del lagrangiano si trova una volta per tutte a mano (x = μ/2, y = μ) e si sostituisce: la funzione duale, scritta per esteso, è d(μ) = −1.25μ² + 4μ, una parabola concava con il vertice in μ = 1.6. Nessun valore supera 3.2, come garantisce la dualità debole, e il massimo lo tocca: il duality gap è zero, e il moltiplicatore che massimizza il duale è lo stesso trovato con le KKT. Nota il comportamento per μ grandi: il duale crolla, fino a diventare negativo. Un limite inferiore resta valido anche quando è inutile.

Dualità forte e condizione di Slater: che cosa enunciamo e dove si dimostra

Quando il duality gap è zero si dice che vale la dualità forte: d* = p*, e risolvere il duale equivale a risolvere il primale. Non vale sempre. La condizione sufficiente più usata è la condizione di Slater.

Enunciato. Se il problema primale è convesso (f convessa, i gᵢ convessi, gli eventuali vincoli di uguaglianza affini) ed esiste un punto strettamente ammissibile, cioè un x̄ nell'interno relativo del dominio con gᵢ(x̄) < 0 per tutti i vincoli di disuguaglianza non affini, allora la dualità forte vale e l'ottimo duale è raggiunto. In più, se p* è finito, esiste un μ* ottimo e la coppia (x*, μ*) soddisfa le KKT.

Non la dimostriamo qui, e lo dichiaro invece di scrivere «si dimostra che»: la dimostrazione passa per il teorema dell'iperpiano separatore applicato all'insieme dei valori raggiungibili {(g(x), f(x))}, e si trova per esteso in Boyd e Vandenberghe, Convex Optimization, §5.3.2, con la lettura geometrica in §5.3.1. La condizione prende il nome da Morton Slater, che la introdusse nel 1950. Quello che faremo qui è verificarla numericamente sui problemi della lezione: abbiamo già visto il gap chiudersi a zero nell'output qui sopra, e lo rivedremo sulla SVM.

Perché risolvere il duale può costare meno. Tre motivi concreti, tutti e tre validi per la SVM. Primo, il numero di variabili cambia: il primale della SVM ha d + 1 incognite (i pesi più l'intercetta), il duale ne ha n, una per esempio — e quando d ≫ n, cioè con poche osservazioni e moltissime caratteristiche, il duale è drasticamente più piccolo. Secondo, i vincoli diventano più semplici: n vincoli di disuguaglianza complicati diventano n semplici positività più una sola uguaglianza, e su quelli esistono algoritmi specializzati. Terzo, e decisivo, nel duale i dati compaiono solo attraverso i prodotti scalari, e questo apre la porta al trucco del kernel. Il rovescio della medaglia: quando n ≫ d, cioè con molti esempi e poche caratteristiche, il duale ha più variabili del primale e conviene il primale — è esattamente la scelta che fa LinearSVC di scikit-learn con il parametro dual="auto".

La SVM: il duale ricavato dal primale

Il primale a margine rigido

Dati n esempi (xᵢ, yᵢ) con yᵢ ∈ {−1, +1} e linearmente separabili, la support vector machine cerca l'iperpiano wᵀx + b = 0 che li separa con il margine più largo. Normalizzando la scala in modo che i punti più vicini soddisfino |wᵀx + b| = 1, il margine vale 1/‖w‖ e massimizzarlo equivale a minimizzare ‖w‖². Il problema primale è

min_(w, b) ½‖w‖² soggetto a yᵢ(wᵀxᵢ + b) ≥ 1, i = 1, …, n.

In forma standard i vincoli sono gᵢ(w, b) = 1 − yᵢ(wᵀxᵢ + b) ≤ 0. Il lagrangiano, con un moltiplicatore αᵢ ≥ 0 per ogni esempio, è

L(w, b, α) = ½‖w‖² + Σᵢ αᵢ [1 − yᵢ(wᵀxᵢ + b)] = ½‖w‖² − Σᵢ αᵢ yᵢ(wᵀxᵢ + b) + Σᵢ αᵢ.

Annullare rispetto a w e a b

Per costruire la funzione duale dobbiamo minimizzare L rispetto alle variabili primali. L è una parabola convessa in w e lineare in b, quindi basta annullare le derivate.

∇_w L = w − Σᵢ αᵢ yᵢ xᵢ = 0, da cui la prima relazione:

w = Σᵢ αᵢ yᵢ xᵢ.

∂L/∂b = −Σᵢ αᵢ yᵢ = 0, da cui la seconda:

Σᵢ αᵢ yᵢ = 0.

Leggi la prima: il vettore dei pesi è una combinazione lineare degli esempi, pesati dai loro moltiplicatori e dal segno della classe. Non è un vettore qualunque dello spazio: vive nello spazio generato dai dati. La seconda dice che i pesi delle due classi si bilanciano.

Ora sostituiamo. Il termine −Σᵢ αᵢ yᵢ b si annulla per la seconda relazione. Resta ½‖w‖² − wᵀ(Σᵢ αᵢ yᵢ xᵢ) + Σᵢ αᵢ, e poiché la somma fra parentesi è w, diventa ½‖w‖² − ‖w‖² + Σᵢ αᵢ = Σᵢ αᵢ − ½‖w‖². Espandendo ‖w‖² con la prima relazione si ottiene il problema duale:

max_α Σᵢ αᵢ − ½ Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ (xᵢᵀxⱼ) soggetto a αᵢ ≥ 0, Σᵢ αᵢ yᵢ = 0.

Guarda che cosa è rimasto. Non ci sono più né w né b. Ci sono n variabili, una per esempio, due vincoli semplicissimi, e i dati compaiono solo dentro la matrice dei prodotti scalari Kᵢⱼ = xᵢᵀxⱼ. Questa non è una riscrittura cosmetica: è il risultato strutturale della lezione.

Due conseguenze che si leggono direttamente dal risultato

Prima conseguenza: i vettori di supporto. Lo scarto complementare dice αᵢ·[1 − yᵢ(wᵀxᵢ + b)] = 0 per ogni i. Quindi, per ogni esempio, o αᵢ = 0, oppure yᵢ(wᵀxᵢ + b) = 1, cioè il punto sta esattamente sul margine. Girando la frase: i punti che stanno oltre il margine hanno moltiplicatore nullo e, per la relazione w = Σ αᵢ yᵢ xᵢ, non contribuiscono al confine. Potresti cancellarli dal dataset e riaddestrare, ottenendo lo stesso identico iperpiano. Gli altri — quelli con αᵢ > 0 — sono i vettori di supporto. Non sono una scelta di progetto né un'euristica: sono una conseguenza aritmetica dello scarto complementare.

Seconda conseguenza: il trucco del kernel è legittimo. Nel duale i dati appaiono solo come xᵢᵀxⱼ. Se sostituisci quel prodotto scalare con una funzione k(xᵢ, xⱼ) che sia il prodotto scalare in qualche spazio di dimensione maggiore (lo garantisce il teorema di Mercer), tutto il resto del problema non cambia nemmeno di una riga: stessi vincoli, stessa struttura, stesso solutore. Ottieni un classificatore non lineare senza mai calcolare le coordinate nello spazio nuovo, che potrebbe avere dimensione infinita. Il trucco del kernel della lezione sulla SVM funziona perché esiste questa forma duale: nel primale non avresti dove infilarlo.

Margine morbido, in due righe. Con dati non separabili si ammettono violazioni ξᵢ ≥ 0 pagandole nell'obiettivo: min ½‖w‖² + C·Σᵢ ξᵢ con yᵢ(wᵀxᵢ + b) ≥ 1 − ξᵢ. Rifacendo lo stesso conto (ora ci sono due famiglie di moltiplicatori, quelli dei vincoli di margine e quelli di ξᵢ ≥ 0, e la loro somma è vincolata a C) il duale resta identico salvo un dettaglio: 0 ≤ αᵢ ≤ C. Il parametro di regolarizzazione C diventa un tetto sul moltiplicatore. Interpretazione diretta: nessun singolo punto può spingere il confine più di tanto, e un C piccolo significa «non lasciare che un esempio anomalo decida da solo».

La regolarizzazione è un vincolo travestito

Torniamo alla lezione su overfitting e regolarizzazione, dove L2 e L1 compaiono come termini aggiunti alla funzione di costo. Da dove vengono? Da un vincolo.

Il problema «adatta i dati ma non lasciare che i pesi diventino grandi» si scrive naturalmente come problema vincolato: min_β L(β) soggetto a ‖β‖² ≤ t. In forma standard, g(β) = ‖β‖² − t ≤ 0, e il lagrangiano è L(β) + λ(‖β‖² − t). Per λ fissato, il termine −λt è una costante e non sposta l'argmin: minimizzare il lagrangiano equivale quindi a minimizzare

L(β) + λ‖β‖²,

cioè esattamente la forma penalizzata che conosci. La corrispondenza fra t e λ è lo scarto complementare. Se il vincolo è attivo (‖β*‖² = t) allora λ > 0 e i due problemi hanno lo stesso argmin; se il vincolo è inattivo, cioè se la soluzione non regolarizzata è già abbastanza piccola, allora λ = 0 e la penalizzazione non serve. Non sono due tecniche diverse: sono lo stesso problema visto dai due lati della dualità. Il valore di λ non si «sceglie» in astratto — corrisponde a un budget t sulla dimensione dei pesi.

import numpy as np
from scipy.optimize import minimize

Xd = np.array([[2.0, 0.0],
               [0.0, 1.0]])                      # matrice di progetto inventata
yd = np.array([4.0, 1.0])
lam = 1.0

beta_ridge = np.linalg.solve(Xd.T @ Xd + lam * np.eye(2), Xd.T @ yd)
t = float(beta_ridge @ beta_ridge)               # il budget che corrisponde a questo lambda
print(f"penalizzata, lambda = {lam}: beta = ({beta_ridge[0]:.6f}, {beta_ridge[1]:.6f})")
print(f"                             ||beta||^2 = {t:.6f}")

perdita = lambda b: float(((Xd @ b - yd) ** 2).sum())
ris = minimize(perdita, np.zeros(2), method="SLSQP",
               constraints=[{"type": "ineq", "fun": lambda b: t - b @ b}],
               options={"ftol": 1e-12})
print(f"vincolata,   t = {t:.6f}:  beta = ({ris.x[0]:.6f}, {ris.x[1]:.6f})")
print(f"stesso argmin a meno di 1e-6 ? {np.abs(ris.x - beta_ridge).max() < 1e-6}")

Output ottenuto (NumPy 2.3.5, SciPy 1.16.3):

penalizzata, lambda = 1.0: beta = (1.600000, 0.500000)
                             ||beta||^2 = 2.810000
vincolata,   t = 2.810000:  beta = (1.600000, 0.500000)
stesso argmin a meno di 1e-6 ? True

Cosa fa il codice. Risolve la ridge in forma chiusa con λ = 1, misura la norma al quadrato della soluzione ottenuta e la usa come budget t del problema vincolato, che poi risolve numericamente con SLSQP. I due argmin coincidono. La direzione inversa è altrettanto vera ma meno comoda: dato t, il λ corrispondente è il moltiplicatore del vincolo.

Palla contro rombo: perché L1 produce zeri esatti. La stessa lettura spiega la differenza geometrica fra L2 e L1, che la lezione sulla regolarizzazione mostra ma non deriva. Il vincolo L2 ‖β‖₂² ≤ t disegna una palla, liscia dappertutto. Il vincolo L1 ‖β‖₁ ≤ t disegna un rombo (un ottaedro in tre dimensioni, un politopo in d), con 2d vertici che stanno sugli assi coordinati. La soluzione vincolata è il punto in cui le curve di livello della perdita, che sono ellissi concentriche attorno alla soluzione non regolarizzata, toccano per la prima volta la regione ammissibile. Su una palla il punto di tocco è generico: la tangente è definita ovunque e il contatto avviene quasi sempre in un punto con tutte le coordinate diverse da zero. Su un rombo, invece, i vertici sporgono, e un vertice ha un intero cono di direzioni normali: un'ellisse che si espande ha una probabilità non trascurabile di toccare lì per prima. E un vertice del rombo L1 ha, per costruzione, tutte le coordinate nulle tranne una. Ecco perché L1 azzera coefficienti e L2 li rimpicciolisce soltanto: non è una proprietà magica della norma, è la forma degli spigoli.

Risolverli in pratica

Penalizzazione: semplice, e il coefficiente non è un moltiplicatore

Il metodo più immediato è trasformare il vincolo in un costo: invece di min f(x) con g(x) ≤ 0, si minimizza f(x) + ρ·max(0, g(x))² con ρ grande. Funziona, ed è una riga di codice. Ma ha due difetti che vanno conosciuti.

Il primo: la soluzione è sempre leggermente infeasible. Il minimo del problema penalizzato viola il vincolo di una quantità che va a zero come 1/ρ, mai esattamente a zero per ρ finito. Il secondo: ρ non è il moltiplicatore, ed è un errore concettuale molto diffuso. Il moltiplicatore implicito è μ̂ = 2ρ·s, dove s è la violazione residua; poiché s scende come 1/ρ, il prodotto converge a μ* mentre ρ cresce senza limite. Verifichiamolo.

def penalizzazione(rho):
    """Minimo di x^2 + y^2 + rho*max(0, 4 - x - 2y)^2, in forma chiusa.

    Annullando il gradiente: x = rho*s, y = 2*rho*s, con s = 4/(1 + 5*rho)
    la violazione residua del vincolo."""
    s = 4.0 / (1.0 + 5.0 * rho)
    x, y = rho * s, 2.0 * rho * s
    return x, y, x * x + y * y, 2.0 * rho * s        # l'ultimo valore è mu stimato

for rho in (1e1, 1e2, 1e3, 1e4, 1e5):
    x, y, f, mu = penalizzazione(rho)
    print(f"rho={rho:>7.0f} | x={x:.6f} | y={y:.6f} | f={f:.6f} | "
          f"mu={mu:.6f} | err={abs(f - 3.2):.2e}")

Output ottenuto:

rho=     10 | x=0.784314 | y=1.568627 | f=3.075740 | mu=1.568627 | err=1.24e-01
rho=    100 | x=0.798403 | y=1.596806 | f=3.187238 | mu=1.596806 | err=1.28e-02
rho=   1000 | x=0.799840 | y=1.599680 | f=3.198720 | mu=1.599680 | err=1.28e-03
rho=  10000 | x=0.799984 | y=1.599968 | f=3.199872 | mu=1.599968 | err=1.28e-04
rho= 100000 | x=0.799998 | y=1.599997 | f=3.199987 | mu=1.599997 | err=1.28e-05

Cosa fa il codice. Risolve il problema penalizzato in forma chiusa, per cinque valori di ρ distanziati di una decade; l'ultima colonna misura la distanza dal valore esatto 3.2 ottenuto con le KKT. Tre letture. L'errore si divide per dieci a ogni decade: la convergenza è di ordine 1/ρ, lenta. Il moltiplicatore stimato 2ρs converge a 1.6, cioè al μ* esatto, mentre ρ arriva a 100000: se qualcuno ti dice che il coefficiente di penalizzazione «è» il moltiplicatore, i due numeri in questa tabella differiscono di cinque ordini di grandezza. E c'è un costo nascosto: l'hessiana del problema penalizzato ha numero di condizionamento che cresce come ρ, quindi un solutore generico rallenta e perde cifre proprio quando ρ diventa abbastanza grande da servire. Trade-off. La penalizzazione conviene quando il vincolo è morbido e una violazione di 1e-4 è irrilevante; non conviene quando il vincolo è duro o quando ti serve il moltiplicatore.

Gradiente proiettato

Se la regione ammissibile ha una proiezione facile da calcolare — un semispazio, una palla, una scatola, il simplesso delle probabilità — si può fare un passo di discesa normale e poi rimettere il punto dentro: x ← Proj_C(x − η∇f(x)). La soluzione resta ammissibile a ogni iterazione, cosa che la penalizzazione non garantisce mai.

def gradiente_proiettato(v0, passi=200, eta=0.1):
    """Discesa proiettata per min ||v||^2 con a . v >= c."""
    a, c = np.array([1.0, 2.0]), 4.0
    v = np.array(v0, dtype=float)
    for _ in range(passi):
        v = v - eta * 2.0 * v                     # passo di discesa sul gradiente di f
        violazione = c - a @ v
        if violazione > 0.0:                      # proiezione sul semispazio
            v = v + (violazione / (a @ a)) * a
    return v

v = gradiente_proiettato([3.0, 3.0])
print(f"gradiente proiettato: v* = ({v[0]:.9f}, {v[1]:.9f})  f* = {v @ v:.9f}")
print(f"distanza dall'ottimo KKT (0.8, 1.6) minore di 1e-12 ? "
      f"{np.hypot(v[0] - 0.8, v[1] - 1.6) < 1e-12}")

Output ottenuto:

gradiente proiettato: v* = (0.800000000, 1.600000000)  f* = 3.200000000
distanza dall'ottimo KKT (0.8, 1.6) minore di 1e-12 ? True

Cosa fa il codice. Parte da un punto ammissibile lontano, (3, 3), e alterna un passo di discesa e una proiezione. La proiezione su un semispazio aᵀv ≥ c è esplicita: se il punto viola, gli si somma ((c − aᵀv)/‖a‖²)·a, il tratto minimo che lo riporta sul bordo. Per i primi passi il punto resta ammissibile e la proiezione non fa nulla; dopo, a ogni iterazione scivola lungo il bordo verso l'ottimo con un fattore di contrazione costante. Trade-off. Il metodo è semplice, mantiene l'ammissibilità e si adatta bene a grandi dimensioni, ma richiede che la proiezione sia calcolabile: su un insieme definito da vincoli non lineari generici la proiezione è a sua volta un problema vincolato, e si entra in un circolo. In più, come la penalizzazione, non restituisce i moltiplicatori.

SLSQP, e dove sono i moltiplicatori

Per i problemi di taglia piccola e media, la scelta pratica è scipy.optimize.minimize con method="SLSQP" (sequential least squares programming): approssima il problema con una successione di sottoproblemi quadratici vincolati e li risolve. Si passano i vincoli come lista di dizionari con "type" uguale a "eq" o "ineq", ricordando che SciPy usa la convenzione fun(x) ≥ 0 per le disuguaglianze: è l'opposto della forma standard g(x) ≤ 0 di questa lezione, e sbagliare quel segno è l'errore numero uno con questa API.

from scipy.optimize import minimize

obiettivo = lambda v: float(v[0] ** 2 + v[1] ** 2)
vincoli = [{"type": "ineq", "fun": lambda v: v[0] + 2.0 * v[1] - 4.0}]   # SciPy: fun >= 0

ris = minimize(obiettivo, x0=[0.0, 0.0], method="SLSQP",
               constraints=vincoli, options={"ftol": 1e-12})
print("successo:", ris.success, "| valutazioni di f:", ris.nfev > 0)
print(f"SLSQP:  v* = ({ris.x[0]:.6f}, {ris.x[1]:.6f})   f* = {ris.fun:.6f}")
print(f"coincide con le KKT a meno di 1e-9 ? {abs(ris.fun - 3.2) < 1e-9}")
print(f"mu ricavato dalla stazionarietà 2x - mu = 0: {2.0 * ris.x[0]:.6f}")

Output ottenuto (SciPy 1.16.3):

successo: True | valutazioni di f: True
SLSQP:  v* = (0.800000, 1.600000)   f* = 3.200000
coincide con le KKT a meno di 1e-9 ? True
mu ricavato dalla stazionarietà 2x - mu = 0: 1.600000

Cosa fa il codice. Imposta il problema con la convenzione di SciPy e lo risolve. L'ultima riga merita attenzione: minimize con SLSQP non restituisce i moltiplicatori nel suo OptimizeResult. Se ti servono esplicitamente, l'opzione è method="trust-constr", che li espone nel campo v. In alternativa — ed è quello che facciamo qui — li si ricava dalla condizione di stazionarietà, che vale sempre all'ottimo e non dipende dal solutore: da 2x* − μ = 0 segue μ = 1.6, lo stesso numero trovato a mano.

Che cosa ci dice. I tre metodi della sezione — KKT a mano, gradiente proiettato, SLSQP — concordano sullo stesso punto (0.8, 1.6) e sullo stesso valore 3.2 entro 1e-9. La penalizzazione no: all'ultima riga della sua tabella è ancora lontana, e per scendere sotto 1e-9 servirebbe ρ dell'ordine di 10⁹, con il condizionamento che ne consegue. È la conclusione pratica della sezione: se il vincolo è duro, usa un metodo che lo tratta come tale.

L'esperimento: sei punti su un foglio

Chiudiamo il cerchio sulla SVM. I dati sono sei punti bidimensionali a coordinate intere, scelti a mano: tre della classe −1 e tre della classe +1, linearmente separabili, con due vettori di supporto che si vedono a occhio. Puoi disegnarli su un foglio a quadretti in dieci secondi, e questo è il punto: nessun generatore di dati, nessun seed, nessuna sorpresa.

Risolviamo il duale così com'è stato ricavato: massimizzare Σᵢ αᵢ − ½ αᵀGα con G la matrice Gᵢⱼ = yᵢyⱼ xᵢᵀxⱼ, sotto αᵢ ≥ 0 e Σᵢ αᵢyᵢ = 0. Poiché i solutori minimizzano, passiamo l'opposto.

import numpy as np
from scipy.optimize import minimize

X = np.array([[1.0, 1.0], [0.0, 1.0], [1.0, 0.0],        # classe -1
              [3.0, 3.0], [4.0, 4.0], [5.0, 3.0]])       # classe +1
y = np.array([-1.0, -1.0, -1.0, 1.0, 1.0, 1.0])

Z = y[:, None] * X                                       # righe y_i x_i
G = Z @ Z.T                                              # G_ij = y_i y_j (x_i . x_j)

duale_negato = lambda al: float(0.5 * al @ G @ al - al.sum())

ris = minimize(duale_negato, np.zeros(6), method="SLSQP",
               bounds=[(0.0, None)] * 6,                 # margine rigido: alpha_i >= 0
               constraints=[{"type": "eq", "fun": lambda al: float(al @ y)}],
               options={"ftol": 1e-12, "maxiter": 500})

alpha = np.where(ris.x > 1e-8, ris.x, 0.0)               # sotto la soglia è zero
print("alpha:", " ".join(f"{a:.4f}" for a in alpha))
print(f"valore del duale d(alpha*) = {-ris.fun:.6f}")
print(f"vincolo somma alpha_i y_i rispettato ? {abs(alpha @ y) < 1e-9}")

Output ottenuto (SciPy 1.16.3, nessun numero casuale):

alpha: 0.2500 0.0000 0.0000 0.2500 0.0000 0.0000
valore del duale d(alpha*) = 0.250000
vincolo somma alpha_i y_i rispettato ? True

Cosa fa il codice. Costruisce la matrice G in una riga sfruttando il fatto che Gᵢⱼ = (yᵢxᵢ)·(yⱼxⱼ), poi minimizza l'opposto del duale con i due vincoli ricavati a mano. La soglia 1e-8 serve perché un solutore numerico non restituisce zeri esatti: nel vettore grezzo ris.x di questa esecuzione c'è un 2.2e-16 accanto a due zeri veri, e i due moltiplicatori non nulli valgono 0.249999982, non 0.25. La distinzione fra «moltiplicatore nullo» e «moltiplicatore piccolo» va imposta da noi, ed è una scelta da dichiarare. Due moltiplicatori su sei risultano diversi da zero, e sono uguali fra loro perché il vincolo Σαᵢyᵢ = 0 lo impone quando i supporti sono uno per classe. Ora ricostruiamo i parametri del classificatore e li confrontiamo con scikit-learn.

from sklearn.svm import SVC

w = (alpha * y) @ X                                      # w = somma alpha_i y_i x_i
supporti = np.flatnonzero(alpha > 1e-8)
b = float(np.mean(y[supporti] - X[supporti] @ w))        # da y_k (w.x_k + b) = 1
print(f"w = ({w[0]:.6f}, {w[1]:.6f})   b = {b:.6f}")
print(f"margine 1/||w|| = {1.0 / np.linalg.norm(w):.6f}   (radice di 2 = {np.sqrt(2):.6f})")
print("margini y_i (w.x_i + b):", " ".join(f"{m:.4f}" for m in y * (X @ w + b)))
print("indici dei vettori di supporto:", supporti.tolist())

mdl = SVC(kernel="linear", C=1e6).fit(X, y)              # C enorme = margine rigido
print(f"w coincide con SVC a meno di 1e-6 ? {np.abs(w - mdl.coef_[0]).max() < 1e-6}")
print(f"b coincide con SVC a meno di 1e-6 ? {abs(b - mdl.intercept_[0]) < 1e-6}")
print("support_ di scikit-learn:", mdl.support_.tolist())

Output ottenuto (scikit-learn 1.8.0):

w = (0.500000, 0.500000)   b = -2.000000
margine 1/||w|| = 1.414214   (radice di 2 = 1.414214)
margini y_i (w.x_i + b): 1.0000 1.5000 1.5000 1.0000 2.0000 2.0000
indici dei vettori di supporto: [0, 3]
w coincide con SVC a meno di 1e-6 ? True
b coincide con SVC a meno di 1e-6 ? True
support_ di scikit-learn: [0, 3]

Cosa fa il codice. Applica le due relazioni ricavate annullando il lagrangiano: w come combinazione pesata degli esempi, e b dalla condizione di margine sui soli vettori di supporto (si media su tutti per robustezza numerica). Poi addestra una SVC lineare con C = 10⁶, che è il modo standard di approssimare il margine rigido con un'implementazione a margine morbido.

Che cosa ci dice. Tutto torna, a 1e-6. Il confine è x₁ + x₂ = 4, il margine è √2, cioè metà della distanza fra (1, 1) e (3, 3), che vale 2√2. La colonna dei margini è la verifica più istruttiva: vale esattamente 1 sui due punti con α > 0 e più di 1 sugli altri quattro — lo scarto complementare, misurato. E gli indici che scikit-learn chiama support_ sono gli stessi che abbiamo trovato noi risolvendo il duale: l'attributo di una libreria e una condizione KKT sono la stessa cosa. Un'ultima nota di onestà sulla tolleranza: è 1e-6 e non 1e-9 perché lo scarto reale è dell'ordine di 1e-7, e quello scarto viene dal nostro duale risolto numericamente, non da scikit-learn, che su questi sei punti restituisce 0.5 e −2 esatti.

Un esperimento di controllo che vale la pena fare. Cancella dal dataset le righe 1, 2, 4 e 5 — i quattro punti con α = 0 — e riaddestra sui due soli vettori di supporto. Ottieni lo stesso w e lo stesso b. Sposta invece (3, 3) in (3.5, 3.5) e tutto cambia: il margine si allarga e i moltiplicatori calano. Il modello dipende da due punti su sei, e i due punti sono quelli più difficili.

Quando i vincoli duri non convengono

Tutto questo apparato ha un costo, e non va pagato sempre. La domanda da farsi è: il vincolo è duro davvero, o è l'approssimazione di un desiderio?

• È l'approssimazione di un desiderio — «i pesi non devono diventare troppo grandi», «le previsioni dovrebbero essere lisce», «preferirei che il modello non usasse troppe caratteristiche». Qui non esiste nessuna soglia naturale: il valore di t lo sceglieresti con la validazione incrociata esattamente come sceglieresti λ. In questi casi la penalizzazione è più semplice: un termine in più nella funzione di costo, nessun solutore vincolato, nessun moltiplicatore da interpretare, e il gradiente resta quello di sempre.
• È duro davvero — un budget che non si può sforare, una probabilità che deve sommare esattamente a 1, una norma unitaria che se violata rende l'oggetto privo di senso, un limite di capacità fisica, un vincolo di legge. Qui la penalizzazione produce una risposta che quasi rispetta la regola, ed è inutile: una distribuzione che somma a 1.0003 non è una distribuzione. Servono i vincoli espliciti.

C'è poi un costo di diagnosi. Un problema vincolato può essere infeasible — nessun punto soddisfa tutti i vincoli insieme — e in quel caso il solutore fallisce senza dirti quale vincolo è di troppo. Con la penalizzazione questo non succede: ottieni sempre una risposta, che però può violare tutto allegramente. Nessuno dei due comportamenti è migliore in assoluto: il primo è rumoroso e onesto, il secondo è silenzioso e pericoloso.

La regola da portare via. Usa i vincoli duri quando la violazione rende la risposta priva di significato, non quando la rende semplicemente meno elegante.

Errori tipici (sintomo, causa, rimedio)

1. Segno di λ invertito. Sintomo: il moltiplicatore esce negativo in un problema dove dovrebbe essere positivo, oppure l'interpretazione come prezzo dà il verso sbagliato («rilassare il vincolo peggiora il valore»). Causa: aver scritto L = f − λg con i vincoli in forma g ≤ 0, o L = f + μg con i vincoli in forma g ≥ 0. Rimedio: porta sempre tutto in forma standard gᵢ(x) ≤ 0 prima di scrivere il lagrangiano, e usa L = f + Σ μᵢgᵢ. Per i vincoli di uguaglianza il segno è libero, per le disuguaglianze no.
2. Slater non verificata, e il duale si ferma sotto il primale. Sintomo: risolvi il duale, ottieni un valore, lo usi come se fosse la soluzione, e il punto primale ricostruito non è ottimo (o non è nemmeno ammissibile). Causa: dualità forte assunta invece che verificata — regione ammissibile senza punti strettamente interni, o problema non convesso. Rimedio: controlla la convessità e l'esistenza di un punto strettamente ammissibile prima; se non puoi, calcola il gap p* − d* esplicitamente e dichiaralo.
3. Penalizzazione troppo debole. Sintomo: la soluzione viola il vincolo di una quantità visibile e nessuno se ne accorge, perché il solutore riporta successo. Causa: ρ scelto una volta sola e troppo piccolo; la violazione scende come 1/ρ. Rimedio: aumenta ρ a scaletta (10, 100, 1000…) riusando la soluzione precedente come punto di partenza, e stampa sempre la violazione residua accanto al valore dell'obiettivo.
4. Moltiplicatore letto come zero quando vale 1e-9. Sintomo: il numero dei vettori di supporto cambia da un'esecuzione all'altra, o è assurdamente alto. Causa: il confronto alpha != 0 su numeri in virgola mobile. Rimedio: una soglia esplicita e dichiarata (alpha > 1e-8), scelta guardando l'istogramma dei valori, non a caso. È lo stesso problema del rango numerico di una matrice.
5. Vincolo scritto g(x) ≥ 0 in un solutore che aspetta g(x) ≤ 0. Sintomo: il solutore converge rapidamente a una soluzione che viola palesemente il vincolo, oppure dichiara il problema infeasible su un problema che ha ovvie soluzioni. Causa: convenzioni diverse fra librerie — SciPy vuole fun(x) ≥ 0 per i vincoli "ineq", la letteratura usa g(x) ≤ 0. Rimedio: dopo aver risolto, valuta i vincoli nel punto trovato e stampali. Tre righe che smascherano il segno sbagliato in un secondo.
6. Discesa del gradiente sul lagrangiano in tutte le variabili. Sintomo: i valori oscillano e non convergono mai, con λ che diverge. Causa: il punto cercato è una sella, un minimo in x e un massimo in λ; scendere in entrambe le direzioni non ha senso. Rimedio: discesa in x e salita in λ (metodo di Uzawa, o lagrangiano aumentato), oppure un solutore che tratti i vincoli esplicitamente.
7. Dimenticare di controllare l'ammissibilità primale. Sintomo: la soluzione ha un valore dell'obiettivo sorprendentemente buono. Causa: si sono risolte solo stazionarietà e scarto complementare, dimenticando che il punto deve anche stare dentro il recinto. Rimedio: le condizioni KKT sono quattro, e si verificano tutte e quattro, nell'ordine.

I sette errori si raggruppano in tre famiglie. Quattro sono di segno o di convenzione (segno del moltiplicatore, vincolo scritto al contrario nel solutore, ammissibilità primale dimenticata, soglia sullo zero), due riguardano ipotesi non verificate (Slater, penalizzazione troppo debole) e uno è un metodo applicato dove non converge. Per le prime quattro basta stampare i vincoli e le quattro condizioni KKT sul punto trovato.

Best practice

• Porta tutto in forma standard prima di scrivere una riga. Vincoli come gᵢ(x) ≤ 0, uguaglianze come hⱼ(x) = 0: metà degli errori di segno sparisce qui.
• Verifica le quattro condizioni KKT sulla soluzione, sempre. Quattro righe di codice che stampano stazionarietà, ammissibilità primale, ammissibilità duale e scarto complementare valgono più di qualunque messaggio di successo del solutore.
• Dichiara la soglia con cui distingui un moltiplicatore nullo da uno piccolo, e scegli quel numero guardando la distribuzione dei valori.
• Usa il duale come certificato. Anche quando risolvi il primale, un qualsiasi μ ≥ 0 ti dà un limite inferiore gratuito: stamparlo accanto al valore corrente dice quanto può ancora migliorare.
• Controlla il problema su un caso con soluzione nota a mano prima di lanciarlo su quello vero: sei punti a coordinate intere valgono più di diecimila punti generati a caso.
• Dichiara le versioni delle librerie quando riporti numeri: il codice di questa lezione è stato eseguito con Python 3.14.4, NumPy 2.3.5, SciPy 1.16.3 e scikit-learn 1.8.0, senza numeri casuali.

Le sei regole costano pochissimo e si controllano tutte con poche righe di codice: la forma standard e le quattro verifiche KKT eliminano la maggior parte degli errori della sezione precedente, la soglia dichiarata e le versioni dichiarate rendono il risultato riproducibile da chi lo rilegge. Se ne applichi una sola, applica la verifica delle quattro condizioni sulla soluzione.

Glossario minimo

• Vincolo attivo (active constraint): vincolo di disuguaglianza che nel punto ottimo vale con l'uguale, gᵢ(x*) = 0. Se non è attivo è inattivo, e rimuoverlo non cambia la soluzione.
• Lagrangiano (Lagrangian): la funzione L(x, μ) = f(x) + Σ μᵢgᵢ(x) che incorpora i vincoli nell'obiettivo, trasformando un problema vincolato in uno libero con più variabili.
• Moltiplicatore (multiplier): la variabile associata a un vincolo; vale la derivata del valore ottimo rispetto al termine noto di quel vincolo, cioè il suo prezzo marginale.
• Problema duale (dual problem): max_μ d(μ) con μ ≥ 0, dove d(μ) = infₓ L(x, μ). È sempre un problema concavo, anche quando il primale non lo è.
• Duality gap: la differenza p* − d* fra ottimo primale e ottimo duale. È sempre ≥ 0 (dualità debole); quando è zero vale la dualità forte.
• Scarto complementare (complementary slackness): la condizione μᵢ·gᵢ(x*) = 0. O il vincolo tocca, o il suo prezzo è zero.
• Condizione di Slater: ipotesi sufficiente per la dualità forte in un problema convesso — esiste un punto che soddisfa strettamente tutti i vincoli di disuguaglianza non affini.
• Vettore di supporto (support vector): esempio con moltiplicatore αᵢ > 0 nel duale della SVM; sta esattamente sul margine ed è uno dei pochi punti che determinano il confine.

Il glossario ha un ordine nascosto: partendo dal vincolo attivo si arriva al lagrangiano, al moltiplicatore, al duale, al gap e allo scarto complementare, cioè lo stesso ragionamento della lezione compresso in otto definizioni. Se una voce ti suona opaca, risali a quella che la precede e rileggi la sezione corrispondente.

Mini-progetto

Costruisci uno script che tratti lo stesso problema con i due linguaggi, vincolato e penalizzato, e li metta a confronto onestamente.

1. Scrivi una funzione che risolva min ‖v − z‖² con v vincolato al simplesso delle probabilità (vᵢ ≥ 0, Σ vᵢ = 1), usando SLSQP. Provala con z = (0.6, 0.1, −0.2, 0.9) e verifica le quattro condizioni KKT sulla soluzione, stampandole una per una;
2. risolvi lo stesso problema con la penalizzazione quadratica sul vincolo di somma più un troncamento a zero delle componenti negative, per ρ ∈ {10, 10³, 10⁵}, e tabula per ciascun ρ la violazione residua di Σ vᵢ = 1 e la distanza dalla soluzione vincolata;
3. documenta il caso limite: che cosa succede quando z ha tutte le componenti negative? Quale vincolo diventa attivo, quanto valgono i moltiplicatori, e la penalizzazione se ne accorge?

Le tre richieste vanno eseguite nell'ordine: prima la soluzione vincolata con le sue quattro verifiche, poi il confronto con la penalizzazione al crescere di ρ, infine il caso limite, che è dove si vede se hai capito quali vincoli diventano attivi. Il confronto fra i due metodi deve restare onesto, con la violazione residua stampata accanto a ogni riga.

Consegna: uno script che stampa la soluzione vincolata, le quattro verifiche KKT, la tabella delle penalizzazioni e una riga di commento sul caso limite.

Challenge

• Easy. Carta e penna: risolvi min x² + y² con x + y = 2. Trova x, y e λ, poi scrivi il valore ottimo come funzione del termine noto c e verifica che λ sia esattamente la sua derivata in c = 2.
• Medium. Carta e penna: scrivi le quattro condizioni KKT per min x² con x ≥ 1 e discuti entrambi i casi (vincolo attivo e inattivo), dicendo per ciascuno quale condizione lo scarta o lo conferma. Poi ripeti con il vincolo x ≥ −1 e confronta i due moltiplicatori.
• Hard. Simula 300 lanci di un dado truccato (scegli tu le sei probabilità vere, dichiarale) e stima le probabilità con il gradiente proiettato sul simplesso, massimizzando la log-verosimiglianza. La proiezione sul simplesso non è ovvia: implementa l'algoritmo di ordinamento e soglia. Confronta la stima con le frequenze empiriche, che sono la soluzione in forma chiusa, e misura di quanto differiscono.
• Expert. Ricava a mano il duale a margine morbido partendo dal primale con la perdita hinge e le variabili di scarto, mostrando da dove esce il vincolo 0 ≤ αᵢ ≤ C. Poi aggiungi ai sei punti della lezione un settimo punto mal classificato e verifica numericamente che al crescere di C da 0.01 a 100 il numero di vettori di supporto diminuisce. Spiega perché, in termini di scarto complementare sui due gruppi di moltiplicatori.
• Enterprise. Prendi l'allocazione reale del tuo tempo di lavoro su quattro o cinque attività. Scrivi il problema in forma standard: una funzione obiettivo (il valore che produci, anche stimato grossolanamente, purché dichiarato), il vincolo di ore totali, i minimi contrattuali su alcune attività, i massimi di sostenibilità su altre. Risolvilo con SLSQP e produci un report che elenca quali vincoli sono attivi all'ottimo e con quale moltiplicatore: quelli sono i vincoli che ti stanno costando qualcosa, in quell'ordine.

I cinque livelli salgono da un conto a mano a un problema con i tuoi dati: i primi due si risolvono con carta e penna e consolidano moltiplicatori e KKT, il terzo e il quarto richiedono codice e un confronto con la soluzione in forma chiusa, l'ultimo porta il metodo sul tuo lavoro. Conviene farli in ordine, perché ciascuno fornisce l'oracolo del successivo.

Gli esercizi di codice di questa lezione sono in un solo file, esercizi.py (circa 13 KB): il moltiplicatore come prezzo marginale, la discussione dei due casi KKT e il duale della SVM risolto sui sei punti. Richiede soltanto Python 3.12 o successivo e NumPy 2.3, senza SciPy e senza numeri casuali. Eseguilo con python3 esercizi.py: gira anche con le parti da completare lasciate vuote e ti dice quali mancano.

Recap

Mappa mentale. Vincolo di uguaglianza: nel punto ottimo ∇f = λ∇g, perché altrimenti resterebbe una direzione ammissibile che migliora. Lagrangiano L = f − λg (uguaglianze) o L = f + Σμᵢgᵢ (disuguaglianze in forma gᵢ ≤ 0). Quattro condizioni KKT: stazionarietà, ammissibilità primale, μ ≥ 0, μᵢgᵢ = 0. Duale d(μ) = infₓ L, sempre concavo, sempre ≤ p*; gap zero sotto Slater. SVM: w = Σαᵢyᵢxᵢ, Σαᵢyᵢ = 0, duale nei soli prodotti scalari, αᵢ > 0 solo sui punti a margine. Regolarizzazione: ‖β‖² ≤ t e λ‖β‖² sono lo stesso problema, e t ↔ λ è lo scarto complementare.

Cheat sheet.

3 concetti: il moltiplicatore è il prezzo marginale del vincolo; lo scarto complementare riduce i casi a due; il duale è sempre un limite inferiore, e sotto Slater è esatto. 3 errori: sbagliare il segno non usando la forma standard; confondere il coefficiente di penalizzazione con il moltiplicatore; leggere come nullo un moltiplicatore che vale 1e-9. 3 best practice: forma standard prima di tutto; verificare le quattro condizioni sulla soluzione; provare su un caso con soluzione nota a mano. 1 esercizio: il mini-progetto sulla proiezione sul simplesso.

Prossima lezione: l'entropia, e la scoperta che quasi tutte le funzioni di costo che userai sono la stessa formula scritta in tre modi.

Domande per andare avanti

• Se il duale è sempre concavo anche quando il primale non lo è, perché non si risolve sempre il duale? (Perché il gap può essere grande, e ricostruire un x primale ammissibile da un μ ottimo non è automatico: rilassamento lagrangiano, ottimizzazione combinatoria.)
• Che cosa succede ai moltiplicatori quando due vincoli attivi hanno gradienti paralleli? (Le condizioni di regolarità dei vincoli — LICQ, MFCQ — e i casi in cui le KKT smettono di essere necessarie: Nocedal e Wright, cap. 12.)
• Come si scrive un vincolo «al più k coefficienti diversi da zero»? (Non è convesso: è la norma L0, e il rombo L1 di questa lezione è il suo rilassamento convesso più usato. Lezione 44, modulo 03.)

Le tre domande puntano oltre la lezione: la prima sul prezzo che si paga per risolvere il duale, la seconda sulle ipotesi che rendono valide le KKT, la terza sul legame fra la norma L0 e il rombo L1. Ognuna ha una risposta breve tra parentesi e un riferimento da cui partire per approfondire.

Nella stessa serie trovi anche: 25 - Calcolo matriciale e differenziazione automatica: dal Jacobiano a un autograd scritto da zero (la lezione precedente), 27 - Entropia, entropia incrociata e divergenza KL: perché le funzioni di costo sono tutte la stessa cosa (la lezione successiva).