ePerTutti


Appunti, Tesina di, appunto informatica

MODIFICA DELL’ASPETTO DI UN DOCUMENTO



Scrivere la parola
Seleziona una categoria

OTTIMI GLOBALI E LOCALI


Generale problema di ottimizzazione:


min                                   (1)


esempi di X (con xIAn


X1 :=

X2 :=

X3 :=

X4 := , i }

X5 :=


Se X=X1 X2, la (1) fornisce un problema di Programmazione Matematica Non-lineare (PNL) in forma generale.





Se X=X3 X5 e f(x) è lineare, la (1) fornisce un problema di Programmazione Lineare (PL) Intera (PLI).


Se  X=X4 X5 e f(x) è lineare, la (1) fornisce un problema di PL- o PL Binaria.


Un caso particolare (un’istanza) di (1) si ottiene quindi definendo una regione di ammissibilità X e una funzione f: X T A. Il problema richiede di trovare un punto x* di An tale f(x*) f(x), xIX.

Tale punto (vettore) x è detto ottimo globale dell’istanza di (1) corrispondente ai dati forniti.


Se ha senso definire una distanza fra i punti di X, si può parlare di intorno N(x) di un punto x, intendendo con ciò l’insieme dei punti di X “abbastanza vicini” a x. Ad esempio se x è un vettore n-dimensionale a valori reali, si può adottare come distanza quella Euclidea e definire per un certo e


N(x) := .          (2)


Per molti problemi la ricerca di un ottimo globale può essere molto difficile, mentre è possibile determinare un punto che è ottimo locale rispetto ad un assegnato intorno.


DEFINIZIONE 1 – Dati due vettori x ed y in An, una combinazione convessa di essi è un qualunque vettore


z := lx + (1-l)y                        (3)

con lI


DEFINIZIONE 2 – Una regione X dello spazio a n dimensioni An è convessa se e solo se è chiusa rispetto alla combinazione convessa di qualunque coppia di vettori ad essa appartenenti, cioè se per ogni coppia di punti x,y di X ogni vettore del tipo (3) appartiene anch’esso ad X.


LEMMA 1 – L’intersezione di un qualunque numero di regioni convesse è una regione convessa. (Dimostrazione per esercizio.)


DEFINIZIONE 3 – Sia S una regione convessa. Una funzione f: S T A si dice convessa se per ogni coppia di vettori x,y di S succede che, per ogni lI


f(z) = f(lx + (1-l)y) lf(x) + (1-l)f(y).


LEMMA 2 – Sia f(x) una funzione convessa su un insieme convesso S. Allora per ogni numero reale d, l’insieme

Sd

È convesso.


DIMOSTRAZIONE: siano x,y I Sd. Allora un punto z definito dalla (3) appartiene ad S e, dato che f(x) è convessa,


f(lx + (1-l)y) lf(x) + (1-l)f(y) ld l d d


e quindi zISd


DEFINIZIONE 4 – Una funzione f è detta concava in una regione convessa S, se –f è ivi convessa.


Si dimostra la seguente proprietà fondamentale della Programmazione Matematica Convessa:


TEOREMA – Se in (1) X è una regione convessa e f(x) è una funzione convessa, allora per ogni e>0, un ottimo locale di (1) nell’ intorno N definito come in (2) è anche ottimo globale.


DIMOSTRAZIONE: sia x* un ottimo locale per (1) in N e sia y un punto di X qualunque (de quindi in generale esterno ad N). Possiamo scegliere nella (3) l sufficientemente vicino ad 1 affinché z appartenga ad N. Si ha allora


f(z) =  f(lx* + (1-l)y) lf(x*) + (1-l)f(y)


ovvero

f(y) (f(z) - lf(x*))/ (1-l


Ma siccome zIN, f(z) f(x*) e quindi


f(y) (f(x*) - lf(x*))/ (1-l) = f(x*).    


Si osservi che nessuna ulteriore ipotesi è stata fatta per f(x) che quindi può anche essere non-differenziabile.


ESERCIZIO: dimostrare che un problema di tipo (1) con X=X1 X2 è un problema di programmazione matematica convessa se f(x) è convessa, le gi(x) sono concave, e le hj(x) sono lineari.








Privacy

© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta