Programmazione Non Lineare (PNL) - Ricerca operativa

3.4-PROGRAMMAZIONE NON LINEARE VINCOLATA QUADRATICA

DEFINIZIONE DI PROBLEMA DI PQ

Un problema di Programmazione Quadra ca PQ è un problema del po:

1

min () = +

2

. . ()

ℎ = ∈

()

≥ ∈

Dove i vincoli e sono funzioni lineari, ovvero possono essere espresse nel

ℎ () ()

seguente modo: () ()

ℎ = ℎ ∈ = ∈

Inoltre, è quadra ca e è simmetrica e coincide con la matrice hessiana.

()

La regione ammissibile è un

() ()

= ∈ ℝ ℎ = ℎ ∈ , = ∈

insieme convesso (perché composto da funzioni convesse) e si suppone essere un poliedro

limitato e non vuoto.

CONSIDERAZIONI

 Se è semidefinita posi va allora è un punto di minimo globale

∗

 Se è definita posi va, allora è l’unico punto di minimo globale

∗

Queste considerazioni discendono dal fa o che è convessa ed è un insieme convesso

Il Problema di PQ è una par colare istanza di un problema di PNL Vincolata e quindi valgono

le condizioni di KKT: se si conosce il punto esisterà un tale per cui le condizioni di KKT

∗ ∗

sono verificate. E questo è un punto di minimo globale.

∗

Se è definita posi va è l’unico punto di minimo globale.

∗

METODO RISOLUTIVO PER PQ: METODO DELL’INSIEME ATTIVO

Si considera il problema di partenza (problema di PQ). Si sfru erà un approccio itera vo,

definito dall’iterazione -esima.

Si definisce inoltre come la soluzione all’iterazione

( )

-esima.

A questa soluzione è associato l’insieme dei vincoli a vi .

( )

Bisogna verificare se è soluzione o ma e quindi bisogna verificare se le condizioni di

( )

KKT sono soddisfa e, e cioè verificare che: ( )

≥ 0 ℎ ∈

In tal caso sarebbe soluzione o ma perché, come già visto, esiste un solo punto che

()

minimizza la funzione obie vo, e quella rappresenterà la soluzione o ma.

Se non è un punto di KKT bisogna risolvere il so oproblema , che è il problema

() ()

di con solo i vincoli a vi : la soluzione del so oproblema è un nuovo punto

( )

.

( )

Bisogna quindi verificare se questo nuovo punto è o mo o meno e l’algoritmo si reitera.

Vediamo la formalizzazione di questa procedura che è stata discussa:

( )

: , , ∇, = 0

Dato il punto si determina l’insieme dei vincoli a vi

( ) ( )

E’ possibile determinare i valori dei mol plicatori di Lagrange ( )

( )

( ) ( ) ( )

→ = ∇

Se per qualche vincolo allora non è o mo e allora bisogna determinare un

( ) ( )

< 0

nuovo punto: si toglie da il vincolo associato al più nega vo.

( )

Si costruisce allora il so oproblema quadra co ponendo una nuova soluzione come

( )

la soluzione all’iterazione più una direzione di discesa (ci si vuole allontanare da

-esima

e bisogna garan re che il valore di funzione obie vo decrementa):

( )

( ) ( )

= +

La direzione di discesa si ricava risolvendo e in par colare risolvendo il seguente

( )

sistema: ( )

∇ = 0

→ ( ) ( )

+ = ∀ ∈

Se qualche bisogna verificare l’ammissibilità di (questo perché si è calcolata

( )

> 0

la direzione di discesa su un so oinsieme dei vincoli del problema di partenza), quindi la

nuova soluzione è sicuramente ammissibile per ma non per il problema generale.

( )

Se è inammissibile per qualche vincolo , allora bisogna considerare una

( ) ( )

∉

nuova soluzione calcolata nel modo seguente, introducendo il passo (se la soluzione è

inammissibile vuol dire che la direzione di discesa conduce verso una direzione per cui si

esce fuori dalla regione ammissibile)

( ) ( ) ∗

= +

E’ come se ci fosse un passo pari ad se è inammissibile vuol dire che il passo

( )

1;

è troppo grande, quindi sarà necessario calcolare un passo che sarà minore di 1

= 1

(non bisogna scendere troppo come valore di funzione obie vo grazie alla direzione di

discesa che si è trovata, bisogna limitarsi in qualche modo alla regione ammissibile).

Si determina quindi un nuovo punto, questa volta parametrizzato ad :

( )

−

= ∀

∗

Per quanto de o prima: ∗

= min 1,

Quindi: ( ) ( ) ∗ ∗

= +

Dopodichè si pone: =+1

Inizia nuovamente l’iterazione e si ripete tu o

ESERCIZIO

Dato il punto iniziale trovare la soluzione o ma

( ) [0

= 0] ( (

min () = − 6) + − 1)

. . 5 + 2 ≤ 3

+ 2 ≤ 10

≥0

≥0

Riscriviamo il problema di PQ in forma standard:

( (

min () = − 6) + − 1)

. . −5 − 2 + 3 ≥ 0

− − 2 + 10 ≥ 0

≥0

≥0

Ricaviamo: 1 0

−5 −1

= 0 1

−2 −2

2( − 6)

∇() = 2( − 1)

A questo punto vediamo qual è l’insieme dei vincoli a vi, sos tuendo il punto ai

[0 0]

vincoli del problema. I vincoli 3 e 4 sono vincoli a vi:

( )

= {3,4}

( ) ( )

Ora determiniamo i valori di e :

( )

( ) ( )

= ∇Q

( ) ( )

= −12

1 0 −12

= →

( ) ( )

0 1 −2

= −2

( ) ( )

No amo che quindi è non o male.

( )

, < 0

Bisogna trovare un nuovo punto in modo da allontanarci dal vincolo che ci dà

( )

maggiormente “fas dio”, cioè quello rela vo a che è il più nega vo.

= −12,

Di conseguenza: ( )

= {4}

0

( ) ( )

= + = + =

0

Bisogna risolvere che avrà la seguente forma:

( )

( ) ( (

min = − 6) + − 1)

. . =0

Tenendo conto del vincolo: ( ) (

= − 6) + 1

Si ha una funzione quadra ca che ha una sola variabile: basta determinare la derivata e

porla uguale a 0: ( )

( ) = 0 → 2( − 6) = 0 → = 6

Quindi: 6

( )

= 0

Bisogna verificare che sia ammissibile perché si è calcolata una direzione di discesa,

( )

quindi una nuova soluzione che minimizza il più possibile la funzione obie vo. Quindi il

vincolo 4 è sicuramente soddisfa o, ma bisogna verificare gli altri tre vincoli.

Si può facilmente verificare che il vincolo 1 è inammissibile:

−5(6) − 2(0) + 3 ≥ 0? −30 + 3 ≥ 0?

Vincolo 2 e 3 sono soddisfa (si può provare banalmente).

In generale, la soluzione è inammissibile.

( )

Bisogna determinare la nuova soluzione come:

( )

0 6 6

( ) ( )

= + = + =

0 0 0

A questo punto va individuato il valore di che soddisfi il primo vincolo:

−5(6) − 2(0) + 3 = 0

Abbiamo posto uguale a 0: il primo vincolo è inammissibile perché questa re a è stata

superata dalla direzione di discesa (dal passo quindi bisogna trovare un valore di

= 1),

in modo da rientrare nella regione ammissibile e il caso migliore in termini di valore di

funzione obie vo è quando il vincolo viene soddisfa o esa amente per uguaglianza

(entrando troppo nella regione ammissibile si rischia di determinare un valore di funzione

obie vo più alto). −30 = −3

1

= 10

Il nuovo punto sarà: 1 3/5

6 ∙

( )

= =

10 0

0

A questo punto bisogna reiterare l’algoritmo.

L’insieme a vo sarà: ( )

= {1,4}

( )

( ) ( )

= ∇ 54 54

( ) ( )

3 −5 = − =

( )

2 −6

−5 0 5 25

= → →

5 58 58

( )

−2 1 ( ) ( ) ( )

2(0 − 1) −2 + = =

25 25

( ) ( )

A questo punto e quindi:

, ≥ 0 3/5

( )

= :

0

ESERCIZIO

Dato il punto iniziale ( ) [1

= 5]

min () = + − 2 − 10 − 20

. . − − ≤ −6

≥0

≥0

− ≥ −3

− ≥ −5

Ricaviamo: −1 1 0 −1 0

= −1 0 1 0 −1

2 − 2 − 10

∇() = 2 − 2 − 20

Calcoliamo l’insieme a vo: ( )

= {1,5}

( )

( ) ( )

= ∇q

( ) ( ) ( )

− = −18 = 18

−1 0 −18

= → →

( ) ( ) ( ) ( )

−1 −1 −12

− − = −12 = −6

( )

Dato che allora non è o ma e quindi:

( )

< 0 1+

( ) ( )

= + = 5+

Per calcolare la direzione di discesa si toglie dall’insieme dei vincoli a vi quello più

“fas dioso” e cioè il vincolo 5: ( )

= {1}

Si costruisce ( )

:

( (

min ( ) = + 1) + + 5) − 2( + 1)( + 5) − 10( + 1) − 20( + 5)

. . − − 1 − − 5 = −6 → − − = 0

Le variabili sono e , quindi si possono sfru are le condizioni necessarie del primo

ordine perché sappiamo c