Financial Polis

  Expand All  |  Contact All

 




Le limitazioni operative del teorema dei moltiplicatori di Lagrange possono però venire superate. Il principio fondamentale su cui si basano, previa una necessaria generalizzazione, può essere esteso fino a comprendere anche vincoli in forma di disuguaglianza. Il ragionamento si presta ad una esposizione intuitiva, per cui rinunciamo ad una formulazione rigorosa e rimandiamo come di consueto alla Bibliografia per maggiori dettagli.

Consideriamo un problema consistente in una funzione da minimizzare, la cui unica condizione sia la non negatività di una variabile xi. La funzione in esame può essere benissimo una Lagrangiana costruita partendo da un problema sottoposto a vincoli di uguaglianza. Essendo la funzione di minimo libero, a parte i valori di xi, si possono assegnare alle variabili valori a piacimento.

Se la derivata parziale della funzione obiettivo rispetto ad xi è negativa, e il valore corrente della variabile è ammissibile, cioè positivo, la funzione

obiettivo diminuisce, cioè migliora, se ceteris paribus xi viene aumentato. Se la derivata parziale è positiva, la funzione può venire migliorata diminuendo xi. In tal caso, la funzione si presta ad essere diminuita, migliorando con ciò l'obiettivo, fintantoché‚ xi non "arriva" al valore zero. Oltre non si può andare, poiché‚ diminuendo ulteriormente il valore assegnato ad xi si uscirebbe dall'insieme di ammissibilità per il problema. Perciò, se la derivata parziale rispetto ad xi è positiva o al limite nulla nel punto xi = 0, si è in presenza di un minimo locale rispetto ad xi, quindi di un punto "candidato" all'ottimalità.

Un punto in cui xi è maggiore di zero non può essere di ottimo, a meno che non vi sia, rispetto ad essa, un "avvallamento", cioè un annullamento con cambiamento di segno della derivata parziale. Anche un punto siffatto è "sospettabile" di essere di ottimo almeno per quanto concerne xi. Gli altri valori di xi possono essere esclusi a priori dalla ricerca, in quanto sicuramente non ottimali rispetto a tale variabile.

Riassumendo, nella ricerca dell'ottimo rispetto a xi, la ricerca andrà limitata a quei valori di xi per cui si verifica almeno uno dei due casi seguenti:

- o xi è uguale a zero e la relativa derivata parziale è ivi positiva o, al limite, nulla;

- oppure la derivata parziale è uguale a zero e xi è maggiore di zero o, al limite, nulla.

Tale principio vale, naturalmente, quando le variabili limitate in segno sono più d'una. Si è così ristretto l'insieme dei punti "candidati" all'ottimalità. Va osservato che il secondo caso di ottimalità locale comprende la nullità della derivata che sarebbe necessaria secondo il teorema dei moltiplicatori di Lagrange. Inoltre, si nota che c'è simmetria fra xi e la derivata parziale ad essa relativa. Per brevità, indicheremo d'ora in poi con il simbolo u il vettore delle derivate parziali prime della funzione obiettivo rispetto ad x, vale a dire il gradiente. Diremo anche che xi e ui sono variabili complementari l'una rispetto all'altra per ogni i.

La condizione di ottimalità appena descritta può essere formalizzata come segue:

 

│ xi ≥ 0

< ui ≥ 0

│ xi ui = 0

Visto e considerato che tanto xi che ui sono sottoposte a vincoli di segno, l'equazione si verifica solo se almeno una delle due variabili è nulla. Ciò esprime il principio detto anche della "nullità complementare" come una delle condizioni necessarie di ottimalità.

Tale condizione deve venir posta per ciascuna delle variabili limitate in segno in aggiunta alle normali equazioni del sistema di Lagrange. Le condizioni in questione sono dette di Karush-Kuhn-Tucker dal nome, rispettivamente, del laureando e della coppia di studiosi che le hanno indipendentemente scoperte. Una condizione di KKT va formulata per ogni xi sottoposta a vincolo di non negatività. Per le variabili "libere", cioè non limitate in segno, è necessario imporre semplicemente che la rispettiva ui sia uguale a 0, come per le normali condizioni di Lagrange.

Condizioni di KKT si possono formulare in modo analogo per i vincoli propri in forma di disuguaglianza, anche se, considerata la possibilità di "convertire" i vincoli propri, non sarebbero indispensabili. Tuttavia essa evidenzia che esiste ancora una "complementarità": quella tra i moltiplicatori di Lagrange e le variabili inattive che dovrebbero venire aggiunte ai vincoli in forma di disuguaglianza.

I moltiplicatori di Lagrange sono, nel punto di ottimo, diversi da zero, a meno che non ci sia degenerazione. Se si ha un vincolo in forma di disuguaglianza, può accadere che in un punto interno alla regione ammissibile la derivata parziale della Lagrangiana rispetto a gi(x) si annulli, determinando così un ottimo locale. Tale derivata non è altro che il moltiplicatore vi, mentre la variabile che in questo caso assume valore positivo è semplicemente la slack yi del vincolo. Quest'ultima sarà invece zero nel primo caso, cioè quando il vincolo è soddisfatto con l'uguaglianza, mentre non potrà mai essere negativa, pena la violazione del vincolo. Sintetizzando i due casi in un sistema analogo a quello riferito ad un vincolo improprio si ottiene:

 

│ yi ≥ 0

< vi ≥ 0

│ yi vi = 0

In generale, a differenza delle derivate prime di x, non è obbligatorio che il moltiplicatore di Lagrange sia non negativo, quando la slack è nulla. La condizione di non negatività è stata scoperta da Slater, ed è sottoposta alla condizione che l'insieme delimitato dai vincoli, posti in forma di disuguaglianza, abbia almeno un punto interno. Questa circostanza, detta condizione di Slater alias qualificazione del vincolo, per disequazioni lineari, si verifica sempre.

La validità delle condizioni di KKT è in generale condizionata alle stesse ipotesi del teorema di Lagrange, e in più, ma solo per quanto riguarda il segno dei moltiplicatori v, alla condizione di Slater. Si può dire che le condizioni di Lagrange sono l'applicazione in un caso particolare delle condizioni di KKT.

Coerentemente anche queste condizioni sono necessarie e non sufficienti, essendo di carattere "locale". Rispetto alle condizioni di semplice nullità delle derivate, offrono però il vantaggio di consentire di lavorare anche su vincoli in forma di disuguaglianza. Ciò è per i problemi di programmazione un requisito fondamentale. Dato poi che, nel nostro caso, l'ottimalità globale è necessaria per quella locale, le condizioni di KKT possono essere impiegate direttamente come base teorica per la elaborazione di procedure risolutive di problemi di programmazione matematica.

Alcuni tra i più citati metodi risolutivi specifici per i problemi di programmazione quadratica si basano su varianti del metodo del simplesso per la programmazione lineare. L'opportunità dell'applicazione di tale approccio deriva dal fatto che le condizioni di KKT per un problema quadratico formano un sistema in parte lineare, per il trattamento del quale gli studi hanno ottenuto buoni risultati. Tuttavia sono necessarie alcune modifiche al metodo del simplesso, per il fatto che il sistema ottenuto tramite le condizioni di KKT non è interamente lineare. Di seguito viene esaminato in dettaglio un algoritmo per la programmazione quadratica tra i più efficienti e di uso piuttosto esteso. Dopo di che vedremo come il metodo del simplesso possa essere utilizzato per risolvere un problema di programmazione quadratica parametrica del tipo generato dal modello di Markowitz, partendo dall'impostazione "tabellare" data da Sharpe.

 

2.4.4 Il metodo del simplesso applicato alla programmazione quadratica.

 

La forma generale del problema quadratico a cui si farà riferimento d'ora in avanti è la seguente:

 

Min z = x' C x + c' x

 

con C simmetrica semidefinita positiva, sottoposto agli m + n + m vincoli lineari:

 

 

A x + y = b

x ≥ 0

y ≥ 0.

 

I vincoli propri sono stati trasformati in uguaglianze aggiungendo m variabili slack, a cui noi diamo l' etichetta distintiva y. Per quei vincoli già in forma di uguaglianza la relativa slack verrà, come si vedrà, trattata come artificiale e dunque forzata fuori della base. Tale procedura porta al calcolo di una soluzione ammissibile per il metodo del simplesso.

La Lagrangiana per questo tipo problema assume la forma:

 

L(x, u) = x' C x + c' x - v' ( A x + y - b)

 

Le condizioni di KKT per questo problema si compongono delle relazioni ottenute tramite le considerazioni seguenti:

 

- essendo stati espressi i vincoli propri in forma di uguaglianza tramite un vettore di variabili inattive, si impone direttamente la nullità del gradiente rispetto ai moltiplicatori v, n‚ più e n‚ meno che nel sistema di Lagrange. Il che equivale, come già osservato in precedenza, esattamente alle equazioni che compongono il sistema dei vincoli propri:

A x + y = b

- Si introduce il vettore gradiente u sotto forma di variabili "fittizie" e si eguaglia al gradiente della Lagrangiana rispetto a x:

u = 2 C x + c - A' v

- si pone uguale a zero il prodotto tra u ed x per il principio della nullità complementare:

u' x = 0

 

- analogamente si pone uguale a zero il prodotto tra y e il relativo gradiente, il quale, osservando la Lagrangiana, è uguale a - v:

v' y = 0

- si tiene conto dei vincoli di segno per tutte le variabili impiegate, cioè x, y, u, v:

x ≥ 0, y ≥ 0, u ≥ 0, v ≥ 0

Riassumendo le condizioni si ottiene il sistema seguente:

│ u = 2 C x + c - A' v

│ A x + y = b

│ u' x = 0

│ v' y = 0

<

│ x ≥ 0

│ y ≥ 0

│ u ≥ 0

│ v ≥ 0

Si è già stabilito che, essendo il problema per ipotesi convesso e dunque essendo ogni minimo locale anche di ottimo, essendo poi la soddisfazione delle relazioni di KKT condizione necessaria di ottimalità almeno locale, ergo risolvendo questo sistema si trova senza fallo il punto di ottimo globale.

I primi due gruppi di equazioni, poiché‚ formano un sistema lineare, possono venire rappresentati in forma di prodotto matriciale.

 

 

┌ ┐ ┌ ┐ ┌ ┐

│ -2 C 0 I A'│ │ x │ │ c │

│ │ │ │ = │ │

│ A I 0 0 │ │ y │ │ b │

└ ┘ │ │ └ ┘

│ u │

│ │

│ v │

└ ┘

 

 

Questo sistema si presta ad essere rappresentato in un Tableau simile a quello per il metodo del simplesso per la programmazione lineare. La tabella seguente, nel quale viene rappresentato tale sistema, in analogia con quello

dei vincoli nella programmazione lineare, è detto anche tableau di set-up, cioè tavola di allestimento e partenza.

 

significato delle colonne:

. x y u v Riga n.

┌───┬───────┬───────┬───────┬───────┐

│ │ ┤ │ │ │ 0

significato ├───┼───────┼───────┼───────┼───────┤

delle │ │ │ │ │ │ 1

righe u │ c │ -2 C │ 0 │ I │ A' │

│ │ │ │ │ │

├───┼───────┼───────┼───────┼───────┤

│ │ │ │ │ │ n+1

y │ b │ A │ I │ 0 │ 0 │

│ │ │ │ │ │

└───┴───────┴───────┴───────┴───────┘

Colonna n. 0 1 n+1 m+1 2*m+1

 

La riga zero è momentaneamente vuota. Essa è destinata ai criteri "ausiliari". La colonna zero contiene invece i termini noti. La configurazione di partenza prevede che u ed y siano in base, e che assumano i valori, rispettivamente, c e b. Nel tableau di set-up x e v sono fuori base, assumendo naturalmente il valore zero.

Per applicare questo algoritmo, noto come metodo di Dantzig, Whinston e van de Panne, occorre una soluzione ammissibile per i vincoli del problema originario e che rispetti il principio della nullità complementare. A tal fine bisogna applicare preliminarmente una procedura che consenta di trovarne una.