Financial Polis

  Expand All  |  Contact All

 




 E' nota da molto tempo una soluzione analitica al problema di ottimo vincolato classico. Il tema viene trattato estensivamente su tutti i testi di Analisi Matematica II. In questa sede ci limitiamo a riportarne una sintesi intuitiva compiuta sotto un'ottica "operativa".

Il problema di ottimo vincolato classico consiste nel trovare il massimo od il minimo di una funzione differenziabile z(x) definita su Rn con immagine su R. Il punto di minimo deve però appartenere all'insieme determinato da un vettore di m funzioni implicite di forma generale g(x) = 0. Si sottolinea che i vincoli del problema di ottimo vincolato classico consistono esclusivamente di espressioni in forma di uguaglianza.

Si definisce lagrangiana (dal nome del grande matematico italo-francese Giovanni Luigi Lagrange) la funzione Rn+m -> R ottenuta sommando alla funzione scalare z(x) il vettore g(x) premoltiplicato per il trasposto di un vettore v formato da m variabili, dette anche moltiplicatori di Lagrange. I moltiplicatori v devono essere considerati variabili indipendenti della Lagrangiana. Essi vanno ad aggiungersi alle variabili originarie x.

Formalmente, se indichiamo la funzione lagrangiana con L(x, v), essa assume, secondo la definizione, la forma generale:

 

L(x, v) = z(x) - v' g(x)

 

Si osservi che in ciascuno dei punti x in cui ogni funzione gi(x) è uguale a zero, vale a dire, per costruzione, nella regione ammissibile per il problema di ottimo vincolato originario, la funzione L assume lo stesso valore di z.

La Lagrangiana gode di una utile proprietà. Se una soluzione del problema originario esiste finita, se g(x) e z(x) hanno derivate parziali prime continue, se la Jacobiana di g(x) ha rango pieno almeno nella soluzioneottimale, allora condizione necessaria affinché‚ un punto x0 sia soluzione del problema originale è che esista un v0 tale che il gradiente della Lagrangiana, quindi il vettore delle derivate parziali rispetto ad x ed a v, si annulli. In altri termini, costruire la Lagrangiana significa trasformare un problema di ottimo vincolato in uno di ottimo libero, tramite l'artificio di trattare i moltiplicatori come variabili sotto controllo a tutti gli effetti.

Il motivo di tale equivalenza è presto detto. Le derivate parziali rispetto a v non sono altro, per costruzione, che i vincoli in forma nulla. La parte del sistema formata eguagliando a zero tali derivate non fa altro che imporre le limitazioni del sistema originario. Per cui si è certi che la soluzione che verifica il sistema di Lagrange è ammissibile per il problema originario. Inoltre si è già osservato che, almeno per le soluzioni ammissibili del problema originario, la lagrangiana equivale alla funzione obiettivo z. In conclusione, l'ottimo della lagrangiana, globale o locale che sia, è anche, per costruzione, rispettivamente ottimo locale o globale per la funzione obiettivo originaria.

La trasformazione da problema vincolato a libero consente di utilizzare i tradizionali strumenti analitici e/o numerici di ottimizzazione libera, tra i quali il metodo del gradiente, per trovare la soluzione. E' importante osservare che la condizione non è sufficiente; essa cioè non garantisce in generale che risolvendo il sistema formato dall'uguaglianza delle derivate prime a zero si trovi a colpo sicuro la soluzione del problema. A parte il caso banale che la soluzione non esista finita, può esserci per esempio più di un punto che verifica il sistema delle derivate prime uguagliate a zero, poiché‚ ogni ottimo locale è compreso nelle soluzioni; oppure può darsi che le ipotesi del teorema relative alle caratteristiche delle funzioni sotto esame non siano verificate, per cui l'ottimo globale potrebbe addirittura non essere tra le soluzioni del sistema.

Nel caso specifico della programmazione quadratica convessa, avendosi a che fare con funzioni quadratiche semidefinite sotto vincoli lineari, la condizione in questione è però anche sufficiente; infatti tali tipi di funzioni sono sempre differenziabili almeno due volte con continuità e la convessità del problema, che, ricordiamo, significa convessità di funzione obiettivo da minimizzare sotto vincoli convessi, consente di affermare che ogni ottimo locale è anche globale. La dimostrazione si ricava per assurdo. Poniamo che esista un ottimo locale che non sia anche globale. Si consideri il

segmento che congiunge l'ottimo locale con quello globale. Si consideri la proiezione di questo segmento sulla funzione e sul suo insieme di definizione. I punti della funzione su cui si proietta il segmento sono sempre ammissibili per la convessità dell'insieme di definizione. Inoltre i punti di proiezione giacciono sempre "al di sotto" (o, al limite, in coincidenza) con il segmento per la convessità della curva. Essendo la funzione continua, esiste almeno un punto nell'intorno dell'ipotetico minimo globale che giace al di sotto di esso. Per cui o il punto non è di ottimo locale, oppure esso è situato alla stessa altezza dell'ottimo globale, ed è quindi globale esso stesso.

Il sistema che origina dal metodo dei moltiplicatori, essendo lineare, è risolvibile coi normali metodi di calcolo algebrico nonché‚ numerico, per esempio con l'algoritmo di Gauss-Jordan.

Purtroppo, però, il tipo di problema di cui si occupa il presente lavoro, così come molti altri problemi di ricerca operativa, contiene anche dei vincoli in forma di disuguaglianza. Abbiamo visto che le disuguaglianze, se presenti nel problema originale, anche se sono sempre trasformabili in equazioni e disuguaglianze semplici, non sono mai del tutto eliminabili dal problema. Esso, se non altro, richiede la non negatività della soluzione. Nel nostro caso, dunque, non si può applicare direttamente il metodo dei moltiplicatori di Lagrange per risolvere il problema in questione.