Ottimizzazione statica, deterministica e stocastica

OTTIMIZZAZIONE STATICA IN AMBITO DETERMINISTICO

Gli elementi fondamentali di un problema di ottimizzazione.

Il primo è certamente costituito dalle variabili decisionali, chiameremo il vettore delle

variabili decisionali.

1

2

=[ ]

⋮

()

Esso sarà un vettore di componenti. Si possono avere più variabili decisionali, perciò non è

corretto parlare di un’unica variabile scalare ma di una collezione di variabili scalari che

().

raccogliamo in un vettore di dimensione

() (), ( ),

Se il vettore ha dimensione allora lo spazio delle decisioni sarà

2

(

banalmente se = 2) allora tale spazio delle decisioni sarà un piano. Ciascun

punto di tale piano determina una possibile decisione.

Un altro elemento fondamentale di un problema di ottimizzazione è una

funzione obiettivo. Il più semplice dei problemi di ottimizzazione è il minimo

()

su di ():

() 1

Affinché il problema sia ben posto è necessario specificare il dominio e il codominio della

funzione ().

(): →

()

Il dominio è l’insieme di tutti i valori di in cui la funzione () è definita ossia lo spazio delle

( ). ()

decisioni, che abbiamo detto essere Il codominio è proprio in quanto non avrebbe

2

( );

senso calcolare il minimo di una funzione che assume valori in i valori assunti da ()

().

saranno dunque valori scalari in

In questo caso abbiamo formulato un problema a minimizzare, ma in molte circostanze

potrebbe essere necessario risolvere problemi a (2)

(1)

massimizzare. Si dà tuttavia il caso che:

() = − ()

Ossia la minimizzazione di tale funzione (1) equivale alla

minimizzazione di quest’altra (2).

La formulazione che abbiamo dato è dunque generale, poiché

basta invertire il segno della funzione obiettivo per ricondurre un problema di massimizzazione

a uno di minimizzazione. Inoltre, vale che:

() = −()

Ossia l’argomento che minimizza rispetto ad la funzione () è uguale all’argomento che

(),

massimizza, rispetto a la funzione −(). ∗

( )

La condizione necessaria affinché il punto sia un punto di minimo per la funzione ()è

() (0).

porre il gradiente di posto uguale a Mentre una condizione sufficiente e necessaria nel

caso di una funzione scalare di variabile scalare, una condizione sufficiente è:

2

() | =0

∗

=

2

() | >0

2

{ ∗

= (0).

Ossia la derivata seconda delle funzione deve essere strettamente maggiore di La nullità

della derivata prima ci dice infatti che la retta tangente alla funzione () in quel determinato

punto è piatta; la derivata seconda, che in generale ci dice come varia la derivata prima, deve

(0)

essere maggiore di poiché intorno al punto di minimo la funzione deve crescere.

∗

( )

La risoluzione del problema () consiste nel dimostrare che è punto di minimo se e

()

soltanto se, nel caso più generale di funzione scalare di variabili reali:

∗ )

∇( = 0

{ ∗

( )

è .

∗

() ( )

Se e soltanto se il gradiente di valutato in è nullo e la matrice hessiana della funzione

∗

() ( )

in è una matrice definita positiva. Ciò si dimostra con il metodo variazionale.

IL METODO VARIAZIONALE

∗ L(u)

( ) ()

Assumiamo di conoscere che è l’argomento che minimizza rispetto a la funzione

∗

= ()

∗

( ()

se consideriamo una piccola variazione + ) con infinitesimo, allora ( + ) sarà

∗

∗

certamente maggiore di ( ) ∗ ∗

( + ) > ( )

Il metodo variazionale procede in questo modo: assume di conoscere la soluzione del problema,

∗

( ),

effettua una variazione, verifica quali sono le proprietà di cui gode il punto dopodiché si

ottengono le condizioni di ottimalità per un punto. A questo punto, si può rimuovere l’ipotesi

sulla conoscenza della soluzione del problema.

∗

( )

Sappiamo che, perché sia un valore di minimo locale, per valori sufficientemente piccoli di

() si ha che: ∗ ∗

( + ) ≥ ( )

Sfruttando lo sviluppo in serie di Taylor possiamo esprimere una qualunque funzione come un

∗

polinomio. In particolare, ( + ) può essere scritta come:

1

∗ ∗

)

( + ) = ( + ∇| + + ⋯

∗

=

2

()

Lo sviluppo in serie di Taylor ha infiniti termini, ma se è sufficientemente piccolo, allora il

∗

segno di ( + ) è con buona approssimazione determinato dallo sviluppo arrestato al

∗

( )

primo termine. È nostra intenzione soltanto assicurarci, affinché sia un punto di minimo,

∗ ∗

che valga la seguente relazione ( + ) ≥ ( ), per cui ci interessa il segno di

∗ ∗

( + ) − ( ). ∗

Per le considerazioni fatte prime, dello sviluppo in serie di Taylor di ( + ) possiamo in

prima approssimazione trascurare tutti i termini di ordine successivo al primo; per cui avremo:

∗ ∗ )

( + ) − ( ≅ ∇| ≥ 0 ∀

∗

=

Questa condizione è verificata soltanto quando ∇| = 0. Essendo un prodotto scalare sarà

∗

= Quindi assicurarci che

( (0) (

(> 0) per > 0), mentre sarà minore di per = −).

è una condizione necessaria

(| = 0) , non basta.

∗

= 3

Ricordiamoci ora che nello sviluppo in serie vi era anche un termine di ordine superiore che è

(∇| (∇|

trascurabile nel caso in cui ≠ 0). Tuttavia, una volta dimostrato che =

∗ ∗

= =

0), a questo punto acquisisce importanza anche il termine:

1

2

(∇|

Infatti, se = 0), allora il segno dell’espressione ( + ) − ( ) è determinato

∗ ∗

∗

=

dal segno di ((1/2) ). Proveremo dunque a imporre che il segno dell’ultima quantità

(0).

scritta sia strettamente maggiore di ∗

() ( ) (0) (∇|

Nel caso vettoriale, se il gradiente di valutato in è uguale a ossia = 0),

∗

=

allora il segno della differenza ( + ) − ( ) è determinato dal termine del secondo ordine

∗ ∗

d