Cos'è la programmazione quadratica?
La programmazione quadratica è un metodo utilizzato per ottimizzare una funzione quadratica multivariabile che può o meno essere limitata 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, potrebbe esistere una soluzione fattibile e può essere risolta da algoritmi noti come l'algoritmo Simplex espanso. Esistono metodi per risolvere alcune funzioni quadratiche non convesse ma sono complicati e non prontamente disponibili.
Le tecniche di ottimizzazione matematica sono utilizzate nella programmazione quadratica per ridurre al minimo una funzione obiettiva. La funzione obiettivo è composta da una serie di variabili di decisione che possono o meno essere limitate. Le variabili decisionali hanno poteri 0, 1 o 2. La funzione obiettivo può essere sottoposta a una serie di vincoli di uguaglianza lineare e disuguaglianza riguardanti le variabili di decisione. Un esempio di programmazione quadratica è:Riduci al minimo f (x, y) = x
È spesso interessante utilizzare funzioni quadratiche multivariate per descrivere i 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 minimizzano il rischio associato a un determinato rendimento atteso. Un'equazione quadratica composta da pesi patrimoniali e la correlazione tra le risorse descrive la varianza del portafoglio che può essere ridotta al minimo usando la programmazione quadratica. Un altro esempio potrebbe essere un produttore che utilizza un'equazione quadratica per descrivere la relazione tra 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.
Uno dei più importanti ConditioNS nella risoluzione di un programma quadratico è la convessità dell'equazione oggettiva. La convessità di una funzione quadratica è determinata dall'essiano o dalla matrice dei suoi secondi derivati. La funzione è chiamata convessa se la matrice dell'Assia è semi-definita definita o positiva positiva, cioè se tutti gli autovalori sono rispettivamente positivi o non negativi. Se l'Assia è positiva ed esiste una soluzione fattibile, allora quel minimo locale è unico ed è un minimo globale. Se l'Assia è semi-positiva, una soluzione fattibile potrebbe non essere unica. Le funzioni quadratiche non convesse possono avere minimi locali o globali, ma sono più difficili da determinare.
Ci sono molti approcci per risolvere una funzione quadratica convessa usando la programmazione quadratica. L'approccio più comune è un'espansione dell'algoritmo Simplex. Alcuni altri metodi includono il punto interno o il metodo della barriera, il metodo di set attivo e il metodo del gradiente coniugato. Questi metodi sono integrati in CERprogrammi tain come Mathematica® e Matlab® e sono disponibili nelle biblioteche per molti linguaggi di programmazione.