La programmazione quadratica è un metodo utilizzato per ottimizzare una funzione quadratica multivariabile che può essere o meno vincolata linearmente. Molti problemi del mondo reale, come l’ottimizzazione del portafoglio di un’azienda o la riduzione dei costi di un produttore, possono essere descritti utilizzando un programma quadratico. Se la funzione obiettivo è convessa, allora può esistere una soluzione ammissibile e può essere risolta da algoritmi noti come l’algoritmo del simplesso espanso. Esistono metodi per risolvere alcune funzioni quadratiche non convesse, ma sono complicati e non facilmente disponibili.
Le tecniche di ottimizzazione matematica sono utilizzate nella programmazione quadratica per minimizzare una funzione obiettivo. La funzione obiettivo è composta da un numero di variabili decisionali che possono o non possono essere limitate. Le variabili di decisione hanno poteri 0, 1 o 2. La funzione obiettivo può essere soggetta a una serie di vincoli di uguaglianza e disuguaglianza lineari riguardanti le variabili di decisione. Un esempio di programmazione quadratica è: minimizza f(x,y) = x2 + 3y2 – 12y + 12 dove x + y = 6 e x > 0 e y ≥ 0.
È spesso interessante utilizzare funzioni quadratiche multivariate per descrivere problemi del mondo reale. Ad esempio, utilizzando la moderna teoria del portafoglio, un analista finanziario cercherà di ottimizzare il portafoglio di un’azienda scegliendo la proporzione di attività che riduce al minimo il rischio associato a un dato rendimento atteso. Un’equazione quadratica composta dai pesi degli asset e dalla correlazione tra gli asset descrive la varianza del portafoglio che può essere minimizzata utilizzando la programmazione quadratica. Un altro esempio potrebbe essere un produttore che utilizza un’equazione quadratica per descrivere la relazione tra i diversi componenti di qualità e il costo di un prodotto. Il produttore può ridurre al minimo i costi mantenendo determinati standard aggiungendo vincoli lineari al programma quadratico.
Una delle condizioni più importanti nella risoluzione di un programma quadratico è la convessità dell’equazione obiettivo. La convessità di una funzione quadratica è determinata dall’Assia o dalla matrice delle sue derivate seconde. La funzione si dice convessa se la matrice hessiana è definita positiva o semidefinita positiva, cioè se tutti gli autovalori sono rispettivamente positivi o non negativi. Se l’Hessiano è positivo ed esiste una soluzione ammissibile, allora quel minimo locale è unico ed è un minimo globale. Se l’Assia è semi-positiva, una soluzione ammissibile potrebbe non essere unica. Le funzioni quadratiche non convesse possono avere minimi locali o globali, ma sono più difficili da determinare.
Esistono molti approcci per risolvere una funzione quadratica convessa utilizzando la programmazione quadratica. L’approccio più comune è un’espansione dell’algoritmo del simplesso. Alcuni altri metodi includono il metodo del punto interno o della barriera, il metodo dell’insieme attivo e il metodo del gradiente coniugato. Questi metodi sono integrati in alcuni programmi come Mathematica® e Matlab® e sono disponibili in librerie per molti linguaggi di programmazione.