MODIFICA DELL'ASPETTO DI UN DOCUMENTO

OTTIMI GLOBALI E LOCALI

Generale problema di ottimizzazione:

min   (1)

esempi di X (con xIAⁿ

X₁ :=

X₂ :=

X₃ :=

X₄ := , i }

X₅ :=

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

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

Se  X=X₄ X₅ 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 Aⁿ 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 Aⁿ, 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 Aⁿ è 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

S_d

È convesso.

DIMOSTRAZIONE: siano x,y I S_d. 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 zIS_d

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=X₁ X₂ è un problema di programmazione matematica convessa se f(x) è convessa, le g_i(x) sono concave, e le h_j(x) sono lineari.