Metodi e Modelli per le DecisioniCorso di Laurea in Informatica e Corso di Laurea in Matematica

Roberto Cordone

DI - Universita degli Studi di Milano

Lezioni: Giovedı 13.30 - 15.30

Venerdı 15.30 - 17.30

Ricevimento: su appuntamento

Tel.: 02 503 16235

E-mail: roberto.cordone@unimi.it

Web page: http://homes.di.unimi.it/~cordone/courses/2015-mmd/2015-mmd.html

Lezione 4: Programmazione Matematica Milano, A.A. 2015/16

1 / 1

Ottimi locali e globali

Dato un insieme X ⊆ Rn e una funzione f : X → R• punto di ottimo globale e un punto x◦ ∈ X tale che

f (x◦) ≤ f (x) per ogni x ∈ X

2 / 1

Ottimi locali e globali

Dato un insieme X ⊆ Rn e una funzione f : X → R• punto di ottimo globale e un punto x◦ ∈ X tale che

f (x◦) ≤ f (x) per ogni x ∈ X

• punto di ottimo locale e un punto x∗ ∈ X tale che

∃ε > 0 : f (x∗) ≤ f (x) per ogni x ∈ X ∩ Ux∗,ε

dove Ux∗,ε = {x ∈ Rn : ‖x − x∗‖ < ε} e un intorno di x∗ di ampiezza ε

Un punto di ottimo globale e sempre punto di ottimo locale: X ◦ ⊆ X ∗

3 / 1

Dove vogliamo arrivare?

Vorremmo X ◦, ma cerchiamo condizioni necessarie per l’ottimalita locale

Ottimo globale ⇒ Ottimo locale ⇒ Condizioni di KKT

X ◦ ⊆ X ∗ ⊆ XKKT

Le condizioni di KKT individuano punti candidatia essere punti di ottimo locale, e quindi di ottimo globale

1 si risolve il sistema delle condizioni, costruendo XKKT

2 si valutano uno per uno i punti di XKKT

3 i migliori formano X ◦

Si spera che XKKT sia un insieme finito o descrivibile analiticamente

4 / 1

Serie di Taylor

Ogni funzione regolare si puo approssimare localmente con un polinomio

Sia f ∈ C k (Ux,ε) funzione di una sola variabile x ∈ R:

f (x) =k∑

i=0

f (i) (x) (x − x)i + Rk (x − x) per ogni x ∈ Ux,ε

con f (0) = f , f (i) =d i f

dx iper ogni i > 0, e lim

x→x

Rk (x − x)

‖x − x‖k= 0

Per k = 1 si ottiene l’approssimazione lineare

f (x) = f (x) + f ′ (x) (x − x) + R1 (|x − x |)

che per funzioni di piu variabili (x ∈ Rn) diventa

f (x) = f (x) + (∇f (x))T (x − x) + R1 (‖x − x‖)

5 / 1

Direzioni

Dato un punto x ∈ Rn, un vettore d ∈ Rn si dice “direzione” se e pensatocome termine da modulare e aggiungere a x per spostarsi in altri punti

Direzione ammissibile in x ∈ X e un vettore d ∈ Rn tale che

∃α > 0 : x + αd ∈ X ∀α ∈ [0; α)

Spostandosi da x di poco in direzione d , la soluzione resta ammissibile

Direzione migliorante in x ∈ X e un vettore d ∈ Rn tale che

∃α > 0 : f (x + αd) < f (x) ∀α ∈ (0; α)

Spostandosi da x di poco in direzione d , la soluzione migliora

6 / 1

Condizioni necessarie di ottimalita locale

Se x∗ e un punto di ottimo locale,nessuna direzione d e insieme ammissibile e migliorante in x∗

Se x∗ e un punto di ottimo locale, allora f (x) ≥ f (x∗) per ogni x ∈ Ux∗,ε ∩ X

Per assurdo, sia d e ammissibile e migliorante: esistono α1 e α2 tali che

• x∗ + αd ∈ X per ogni α ∈ [0; α1)

• f (x∗ + αd) < f (x∗) per ogni α ∈ (0; α2)

Ora poniamo α = 12

min(

ε‖d‖ , α1, α2

)> 0 e x = x∗ + αd

Dai tre termini dell’operatore di minimo deriva che:

• ‖x − x∗‖ ⇒ x ∈ Ux∗,ε• x ∈ X

• f (x) < f (x∗)

ma poiche x ∈ X ∩ Ux∗,ε deve essere anche f (x) ≥ f (x∗), che e un assurdo

7 / 1

Condizioni necessarie del primo ordine

Ora usiamo l’approssimazione lineare di f (x)f ∈ C 1 (X )

x∗ e punto di ottimo locale

d e direzione ammissibile in x∗⇒ (∇f (x∗))T d ≥ 0

Se d e direzione ammissibile, ∃α tale che per ogni α ∈ [0; α) e

(x∗ + αd) ∈ X ⇒⇒ f (x∗ + αd) ≥ f (x∗)⇒

⇒ f (x∗) + (∇f (x∗))T

(x∗ + αd − x∗) + R1 (αd) ≥ f (x∗)⇒

⇒ (∇f (x∗))Td +

R1 (αd)

α≥ 0

Ora facciamo tendere α a 0; la disuguaglianza si conserva:

limα→0

[(∇f (x∗))

Td +

R1 (αd)

α ‖d‖ ‖d‖]≥ 0⇒ (∇f (x∗))

Td ≥ 0

8 / 1

Una via verso l’ottimo

Un approccio algoritmico per trovare punti candidati:

• scorriamo tutti i punti ammissibili

• scartiamo quelli che hanno direzioni ammissibili e miglioranti

Algorithm TrovaCandidati(f ,X )

C := X ;

For each x ∈ C do

{ Scarta i punti che si dimostrano non candidati }For each d ∈ Rn ammissibile in x do

If (∇f (x))T d < 0 then C := C \ {x}{ Restituisce il miglior punto candidato }Return arg min

x∈Cf (x)

Parrebbe peggio che scorrere esaustivamente i punti di X

9 / 1

Vincoli di uguaglianza non lineari

Inoltre, questo filtro per scartare punti candidati e ingannevolmente forte{f ∈ C 1 (X )

x∗ punto di ottimo locale⇒ (∇f (x∗))

Td ≥ 0 per ogni d ammissibile in x

Il filtro non puo scartare i punti privi di direzioni ammissibili(ad es., quelli che soddisfano vincoli di uguaglianza non lineari)

Esempio:

I punti di X ={x ∈ R2 : x2

1 + x22 = 1

}non hanno direzioni ammissibili

Consideriamo x = (1, 0) ∈ X e supponiamo per assurdo che d sia ammissibile

x + αd = [1 + αd1 αd2]T ∈ X per ogni α ∈ [0; α)

Ma (1 + αd1)2 + (αd2)2 = 1⇒ 2αd1 + α2(d2

1 + d22

)= 0⇒

⇒ α = − d1

d21 + d2

2

, cioe α e fissato, e non libero in un intervallo

Poiche questo vale in ogni punto di X , il procedimento termina con C = X

10 / 1

Archi ammissibili

Arco ammissibile in un punto x ∈ X euna linea parametrica che passa per x e appartiene a X

ξ : R+ → Rn tale che

{ξ (0) = x

ξ (α) ∈ X per ogni α ∈ [0; α)

Dato X ={x ∈ R2 : x2

1 + x22 = 1

}, nel punto x = (1, 0) e ammissibile l’arco

ξ (α) =

[cosαsinα

]dato che ξ (0) = x e ξ (α) ∈ X per ogni α ≥ 0

11 / 1

Direzione tangente

Ogni arco ξ (α) ammissibile in x ha una direzione tangente

pξ =

[dξ1

dα

∣∣∣∣0

. . .dξndα

∣∣∣∣0

]T

Esempio:

L’arco ammissibile

ξ (α) =

[cosαsinα

]ha direzione tangente

pξ =

[− sin 0cos 0

]=

[01

]

12 / 1

Relazione fra direzioni e archi ammissibili

Per ogni direzione d ammissibile in x si puo costruire un arco ammissibile

ξ (α) = x + αd

che e una semiretta

La tangente a tale arco e la direzione stessa: pξ = d

Le tangenti ad archi ammissibili generalizzano le direzioni ammissibili:

• alcuni archi ammissibili hanno come tangente una direzioneammissibile

• altri archi ammissibili hanno come tangente una direzione nonammissibile

Vedremo che si possono scartare punti da C anche con le tangenti

13 / 1

Condizioni necessarie del primo ordine

f ∈ C 1 (X )

x∗ punto di ottimo locale

ξ arco ammissibile in x∗⇒ (∇f (x∗))T pξ ≥ 0

Se ξ (α) e un arco ammissibile, ∃α tale che ξ (α) ∈ X per ogni α ∈ [0; α)

f (ξ (α)) ≥ f (x∗)⇒

⇒ f (ξ (0)) + αdf

dα

∣∣∣∣α=0

+ R1 (ξ (α)− ξ (0)) ≥ f (x∗)⇒

⇒ (∇f (x∗))Tpξ +

R1 (ξ (α)− ξ (0))

α≥ 0

Se facciamo tendere α a 0, la disuguaglianza si conserva:

limα→0

((∇f (x∗))

Tpξ +

R1 (ξ (α)− ξ (0))

‖ξ (α)− ξ (0)‖‖ξ (α)− ξ (0)‖

α

)≥ 0⇒ (∇f (x∗))

Tpξ ≥ 0

Ma come facciamo a scorrere le tangenti ad archi ammissibili?

14 / 1

Caratterizzazione degli archi ammissibili

Supponiamo di descrivere analiticamente la regione ammissibile

X ={x ∈ Rn : gj (x) ≤ 0, con gj ∈ C 1 (X ) , j = 1, . . . , s

}

Se ξ (α) e un arco ammissibile in x ∈ X , allora (∇gj (x))T pξ ≤ 0per ogni vincolo “attivo”, cioe tale che gj (x) = 0

Se ξ (α) e un arco ammissibile in x , esiste α > 0 tale che

gj (ξ (α)) ≤ 0 per ogni α ∈ [0; α) j = 1, . . . , s

ovvero

gj (ξ (α)) = gj (ξ (0)) +dgjdα

∣∣∣∣0

α + R1 (ξ (α)− ξ (0)) =

= gj (x) + α (∇gj (x))T pξ + R1 (ξ (α)− ξ (0)) ≤ 0

Per i vincoli non attivi in x , la disuguaglianza e ovvia perche gj (x) < 0

15 / 1

Caratterizzazione degli archi ammissibili

Invece per i vincoli attivi in x e gj (x) = 0, per cui

gj (ξ (α)) = α (∇gj (x))T pξ + R1 (ξ (α)− ξ (0)) ≤ 0

Dividendo ambo i membri per α e passando al limite, si ha la tesi:

limα→0

[∇gj (x)T pξ +

R1 (ξ (α)− ξ (0))

α

]= pT

ξ ∇gj (x) ≤ 0

Osservazione:

I vincoli di uguaglianza hi (x) = 0 sono sempre attivi e si possono vederecome coppie di disuguaglianze attive hi (x) ≤ 0 e −hi (x) ≤ 0, per cui{

(∇hi (x))T pξ ≤ 0

− (∇hi (x))T pξ ≤ 0⇒ (∇hi (x))T pξ = 0

Ci piacerebbe dire l’inverso: se un arco ha certe proprieta, allora e ammissibile

16 / 1

Punti regolari

Se un arco ξ e ammissibile, il vettore pξ soddisfa le condizioni appena viste,ma se un vettore p le soddisfa, non sempre e tangente a un arco ξ ammissibile

E un problema, perche non si puo usare p per filtrare i punti candidati

Punto regolare e un punto in cui i vincoli attivi hanno gradienti linearmenteindipendenti

Nei punti regolari, le condizioni diventano sufficienti (constraint qualification)

Se

{x e un punto regolare

(∇gj (x))T d ≤ 0 per ogni j : gj (x) = 0

allora esiste un arco ξ (α) ammissibile in x con direzione tangente pξ = d

Nota:

Un vincolo di uguaglianza produce due vincoli con gradienti opposti ±∇hi (x)

Questi sono ovviamente dipendenti, ma se ne considera uno solo, poiche esiste

sempre un arco ammissibile che “striscia” lungo il vincolo hi (x) = 0

17 / 1

Riscriviamo l’algoritmo

• Nei punti regolari, cerchiamo le direzioni p che soddisfano le condizioni suigradienti dei vincoli attivi e le usiamo per valutare punti candidati

• Nei punti non regolari, ogni direzione e inaffidabile (puo scartare punti diottimo locale), per cui consideriamo i punti non regolari come candidati

Algorithm TrovaCandidati(f , g1, . . . , gs)

C ′ := NonRegular(g);

C := X \ C ′;For each x ∈ C do

{ Scarta i punti che si dimostrano non candidati }For each p ∈ Rn : (∇gj (x))T p ≥ 0∀j : gj (x) = 0 do

If (∇f (x))T d < 0 then C := C \ {x}{ Restituisce il miglior punto candidato }Return arg min

x∈C∪C ′f (x)

18 / 1

Lemma di Farkas

Dati f ∈ Rn e gj ∈ Rn con j = 1, . . . , s

∃µj ≥ 0 : f =s∑

j=1

µjgj ⇔ pT f ≤ 0 ∀p : pTgj ≤ 0 ∀j

f e combinazione conica dei gj se e solo se i vettori che puntano dallaparte opposta di tutti i gj puntano dalla parte opposta di f

L’implicazione diretta e banale

L’implicazione inversa e complessa

Ci serve l’implicazione inversa con

• f = −∇f (x∗)

• gj = ∇gj (x∗)

19 / 1

Applicazione agli ottimi locali

Nei punti di ottimo locale le direzioni ammissibili sono non miglioranti

pT∇f (x∗) ≥ 0 ∀p : pT∇gj (x∗) ≤ 0

Questo e il secondo membro del lemma di Farkas, dove si e posto

• f = −∇f (x∗)

• gj = ∇gj (x∗)

Quindi vale il primo membro del lemma di Farkas, secondo il qualese f ∈ C 1 (X ), se x∗ e punto di ottimo locale e se e regolare, allora

∃µj ≥ 0 : ∇f (x∗) +∑

j :gj (x∗)=0

µj∇gj (x∗) = 0

L’antigradiente −∇f (x∗) cade nel cono dei gradienti dei vincoli attivi

20 / 1

Interpretazione geometrica

• L’antigradiente −∇f (x) e la direzione in cui f migliora (cala) piurapidamente

• I gradienti dei vincoli attivi ∇gj (x∗) sono le direzioni in cui essivengono violati (crescono) piu rapidamente

• Variando i moltiplicatori µj ≥ 0,∑

j :gj (x∗)=0

µj∇gj (x∗) disegna un cono

• Avere l’antigradiente dell’obiettivo nel cono dei gradienti dei vincoliattivi indica che l’obiettivo migliora solo violando almeno un vincolo

Quindi non ci sono direzioni ammissibili e miglioranti

21 / 1

Forma standard delle condizioni

In genere, le condizioni di KKT si formulano osservando che

• la somma si puo estendere dai soli vincoli attivi a tutti i vincoliimponendo moltiplicatori nulli ai vincoli inattivi:

∑j :gj (x∗)=0

µj∇gj (x∗) =s∑

j=1

µj∇gj (x∗) con µjgj (x) = 0, ∀j

• per i vincoli di uguaglianza, anziche due gradienti opposti conmoltiplicatori ≥ 0 si puo usare un gradiente con moltiplicatore libero

hi (x) = 0⇔

{gj′i (x) = hi (x) ≤ 0

gj′′i (x) = −hi (x) ≤ 0

. . .+ µj′i∇hi (x) + µj′′i

(−∇hi (x)) + . . . con µj′i, µj′′i

≥ 0

. . .+ λi∇hi (x) + . . . con λi = µj′i− µj′′i

libero

22 / 1

Condizioni di Karush-Kuhn-Tucker

Se

• f ∈ C 1 (X )

• X ={x ∈ Rn : gj (x) ≤ 0, con gj ∈ C 1 (X ) , j = 1, . . . , s

}• x∗ e punto di ottimo locale per f in X

• x∗ e punto regolare in X

allora esistono moltiplicatori λi liberi e µj ≥ 0 tali che

∇f (x∗) +m∑i=1

λi∇hi (x∗) +s∑

j=1

µj∇gj (x∗) = 0

µjgj (x∗) = 0 j = 1, . . . , s

µj ≥ 0 j = 1, . . . , s

Dunque, non dobbiamo scorrere tutti i punti e gli archi ammissibili,ma risolvere un sistema di equazioni e disequazioni

23 / 1

Casi particolari interessanti

• Problemi non vincolati: ∇f (x∗) = 0

I punti candidati sono punti di minimo, di massimo, di flesso. . .

• Problemi discreti: X ⊆ Zn

I vincoli hi (x) = sin (πxi ) = 0 vanno imposti esplicitamente, maquesto significa che ogni punto ammissibile e candidato

Del resto e ovvio: i punti isolati sono punti di ottimo locale

24 / 1

25 / 1