Parte V: Rilassamento Lagrangiano

Parte V:

Rilassamento Lagrangiano

Tecnica Lagrangiana

Consideriamo il seguente problema di Programmazione Lineare Intera:

P¹_{L I} min c^Tx Ax > b

Cx > d

x > 0, intera in cui

• A = matrice m x n

• C = matrice m₁ x n

• b = vettore di dimensione m

• d = vettore di dimensione m₁

• x, c = vettori di dimensione n

Tecnica Lagrangiana

Supponiamo che

● P¹

L I sia un problema difficile, e

● min c^Tx Cx > d

x > 0, intera

sia un problema facile.

In altre parole, stiamo supponendo che i vincoli Ax > b siano quelli che complicano la risoluzione del problema.

Tecnica Lagrangiana

Costruiamo allora un nuovo problema P²_{L I} “inserendo” nella funzione obiettivo i vincoli complicati nel modo seguente:

P²_{L I} min c^Tx – λ^T(Ax – b) Cx > d

x > 0, intera

λ∈R^m₊ = vettore dei moltiplicatori di Lagrange

P²_{L I} = problema Lagrangiano

L(λ) = min{c^Tx – λ^T(Ax – b): Cx > d, x > 0, intera }= funzione Lagrangiana

Tecnica Lagrangiana

Per ogni valore di λ > 0 fissato, la soluzione ottima del problema lagrangiano costituisce un bound duale sull'ottimo del problema originario. Infatti, il problema lagrangiano corrisponde ad un rilassamento (lagrangiano) del problema iniziale.

Proposizione: Sia z* il valore della soluzione ottima di P¹_{L I}^.

Per ogni vettore non negativo λ si ha L(λ) < z*.

Tecnica Lagrangiana

Dim. Per ogni soluzione ammissibile x di P¹_{L I} si ha Ax > b ⇒ Ax – b > 0.

Poiché λ > 0, abbiamo che λ^T(Ax – b) > 0.

Pertanto, per ogni vettore non negativo λ si ha z* = min{c^Tx : Ax > b, Cx > d, x > 0, intera}

> min {c^Tx – λ^T(Ax – b): Ax > b, Cx > d, x > 0, intera}

> min {c^Tx – λ^T(Ax – b): Cx > d, x > 0, intera} = L(λ).

Duale Lagrangiano

L'obiettivo di questo approccio è quello di determinare il vettore λ*

che fornisce il miglior lower bound L(λ*) per z*.

Per calcolare λ* è necessario risolvere il seguente problema di ottimizzazione

L(λ*) = max{L(λ): λ > 0}.

denominato duale Lagrangiano.

Perché si utilizza la denominazione di duale?

Duale Lagrangiano

Consideriamo un problema lineare della forma

PL = min{c^Tx : Ax > b, x > 0}

ed applichiamo il rilassamento lagrangiano sui vincoli Ax > b L(λ) = min{(c^T – λA)x + λb: x > 0}.

Il duale lagrangiano avrà la forma

L(λ*) = max{L(λ): λ > 0}= max{min{(c^T – λA)x + λb: x > 0}, λ > 0}.

Per λ fissato, se (c^T – λA) < 0 la corrispondente componente di x sarà posta a +∞ e quindi L(λ) = –∞.

Poiché il duale lagrangiano è in forma di max ha senso considerare solo quei vettori λ per cui (c^T – λA) > 0. Pertanto il duale lagrangiano può essere riscritto nella forma

L(λ*) = max{λb: (c^T – λA) > 0, λ > 0}

che corrisponde proprio al duale di PL.

Rilassamento lagrangiano e rilassamento lineare

Che relazione esiste tra il bound ottenibile con il rilassamento lineare z_RL e quello ottenibile con il rilassamento lagrangiano L(λ*)?

Teorema: L(λ*) > z_RL.

Pertanto il rilassamento lagrangiano è almeno tanto buono quanto il rilassamento lineare.

Tuttavia l'efficacia del rilassamento lagrangiano è legata all'efficienza con cui si riesce a risolvere il duale Lagrangiano.

Condizioni di ottimalità

per il rilassamento lagrangiano

● La soluzione ottima del rilassamento lagrangiano potrebbe non essere ammissibile per P¹_{L I} a causa dei vincoli rilassati.

● Inoltre, se anche la soluzione del rilassamento lagrangiano è ammissibile, non è detto che essa sia ottima per P¹_{L I}^.

Proposizione(condizione sufficiente): Se, per un fissato valore di λ*, si ha che

1. La soluzione ottima x_L* del problema lagrangiano è ammissibile per P¹_LI

2. (λ*)^T(Ax_L* – b) = 0

allora x_L* è una soluzione ottima anche per P¹_{L I}.

Condizioni di ottimalità

per il rilassamento lagrangiano

Dim: Per definizione, fissato λ, L(λ) = min{c^Tx – λ^T(Ax – b)}.

Dalla condizione 2, si ottiene che L(λ*) = c^Tx_L*.

Inoltre L(λ*) è un lower bound per l'ottimo di P¹_{L I}, ossia c^Tx_L* = L(λ*) < c^Tx

per ogni soluzione ammissibile x.

Dalla condizione 1. sappiamo che x_L* è ammissibile per P¹_{L I} ^e

pertanto deduciamo che x_L* è anche ottima per P¹_{L I}^.

Soluzione del duale lagrangiano

Consideriamo il problema lagrangiano

e sia X = {x¹, ..., x^H} l'insieme di punti interi che soddisfano i vincoli di P²_{L I}.

Per un dato λ, in ciascun punto x^h, la funzione lagrangiana assume il valore (c^T – λ^TA)x^h + λ^Tb, per h = 1, ..., H. Pertanto,

L(λ) = min {(c^T – λ^TA)x¹ + λ^Tb, (c^T – λ^TA)x² + λ^Tb,

...

(c^T – λ^TA)x^H + λ^Tb}

P²_{L I} min c^Tx – λ^T(Ax – b) Cx > d

x > 0, intera

Soluzione del duale lagrangiano

Pertanto

L(λ) = max v

v < (c^T – λ^TA)x^h + λ^Tb per h = 1, ..., H λ > 0

Ricordiamo che:

Una funzione f: Rⁿ → R si dice concava se per ogni coppia x¹, x²∈Rⁿ e per ogni α, 0 < α < 1, risulta

αf(x¹) + (1 – α)f(x²) < f(x¹ + (1 – α)x²).

L(λ) è una funzione continua, lineare a tratti e concava.

Funzione lagrangiana per m = 1

λ L(λ)

λ*

L(λ*)

(c^T – λa^T)x¹ + λ^Tb

(c^T – λa^T)x² + λ^Tb

(c^T – λa^T)x³ + λ^Tb (c^T – λa^T)x⁴ + λ^Tb

(c^T – λa^T)x⁵ + λ^Tb

Soluzione del duale lagrangiano

Pertanto risolvere il duale lagrangiano significa determinare il punto di massimo della funzione L(λ).

Osserviamo che L(λ) è una funzione non differenziabile.

Uno dei metodi più utilizzati per risolvere il duale lagrangiano è il metodo del subgradiente, che può essere applicato a funzioni continue ma non differenziabili.

Metodo del subgradiente

Def: Data L(λ) concava e un punto λ ∈ R^m in cui L non è differenziabile un subgradiente di L in λ è un vettore s ∈R^m tale che, per qualsiasi altro punto λ'∈ R^m, si ha

L(λ') – L(λ) < s^T(λ' – λ)

Osservazione 1: Possono esistere molti vettori s che soddisfano la relazione precedente.

Osservazione 2: Se L fosse differenziabile il suo unico subgradiente in λ sarebbe il suo gradiente ∇L(λ^).

Osservazione 3: λ* è un punto di ottimo per la funzione L(λ) se 0 è un subgradiente di L in λ*.

Metodo del subgradiente

Il metodo del subgradiente per il calcolo di λ* consiste nel generare una successione di valori λ⁽⁰⁾, λ⁽¹⁾, ..., λ^(k), … convergente a λ* in cui

λ^(k+1)= λ^(k)+ θ^(k)d^(k) con

– d^(k) = direzione di spostamento

– θ^(k) = passo opportunamente specificato

Se il passo è scelto in maniera opportuna, l'algoritmo del subgradiente converge a λ*.

Scelta del subgradiente

Teorema: Siano λ^(k) ∈ R^m e x^(k) ∈ Zⁿ₊ due vettori tali che

L(λ^(k)) = min{c^Tx – λ^(k)T(Ax – b): Cx > d, > 0, intera}

= c^Tx^(k) – λ^(k)T(Ax^(k) – b).

Allora il vettore (b – Ax^(k)) è un subgradiente di L(λ) in λ^(k).

Dim: Per un generico vettore λ risulta:

L(λ) = min{c^Tx + λ^T(b– Ax): Cx > d, > 0, intera}

< c^Tx^(k) + λ^T(b– Ax^(k))

= c^Tx^(k) + λ^(k)T(b– Ax^(k)) + (λ – λ^(k))(b– Ax^(k)) = L(λ^(k)) + (b– Ax^(k))(λ – λ^(k))

Dalla definizione di subgradiente segue la tesi.

Scelta del passo

La scelta del passo θ^(k) è fondamentale per la convergenza o meno ad un punto di massimo λ*.

Inoltre, nel caso di convergenza, la scelta di θ^(k) ne influenza notevolmente la velocità.

Se la sequenza θ^(k) soddisfa le condizioni lim θ^(k) = 0

∑

allora la successione {λ^(k)} generata scegliendo d^(k) = s^(k)/||s^(k)||

converge a λ*.

k→ +∞

k=0 +∞

Algoritmo del subgradiente

Input: L(λ), λ⁽⁰⁾ =punto iniziale , K_MAX = massimo numero di iterazioni senza miglioramento 1. Inizializzazione k := 1.

2. Per un dato λ^(k), calcola la soluzione x^(k) del problema Lagrangiano.

3. s^(k) := b − Ax^(k). Se s^(k) = 0, STOP 4. θ^(k) := (z_UB − L(λ^{(k – 1)}))/||s^(k) ||

5. λ^(k+1) := λ^(k) + θ^(k) s^(k)/||s^(k) ||

6. k := k + 1

7. Se il lower bound non è migliorato nelle ultime K

MAX iterazioni, STOP, altrimenti vai al passo 2.

Esempio: TSP simmetrico

Una delle applicazioni più efficaci della tecnica lagrangiana è quella del TSP simmetrico.

Dati

• G = (V, E) grafo completo, |V| = n

• c_ij = costo associato all'arco ij, per ogni ij ∈E

determinare un ciclo hamiltoniano su G di costo minimo.

Per formulare il TSP simmetrico, definiamo

• S = sottoinsieme di nodi di V

• E(S) = archi con entrambi gli estremi in S

• δ(S) = archi con un estremo in S ed uno in V\S.

Esempio: TSP simmetrico

Consideriamo le variabili binarie x_ij = 1 se l'arco ij appartiene al ciclo hamiltoniano, x_ij = 0 altrimenti.

Formulazione:

min

∑

∑

∑

ij∈E

ij∈δ(i)

ij∈E(S)

Esempio: TSP simmetrico

I vincoli

∑ ^x_ij ^{= 2} per ogni i ∈V

indicano che su ogni nodo del grafo devono incidere esattamente due archi del ciclo hamiltoniano.

ij∈δ(i)

ij∈E(S)

I vincoli

∑ ^x_ij < |S|– 1 2 < |S| < n–1

garantiscono che nessun sottografo indotto dai nodi in S contenga sottocicli.

Tali vincoli sono in numero esponenziale (O(2ⁿ))!

Esempio: TSP simmetrico

Tuttavia alcuni degli (O(2ⁿ)) vincoli sono superflui.

Infatti, consideriamo un nodo arbitrario, sia esso v = 1, e scriviamo i vincoli soltanto per i sottoinsiemi S che non contengono tale nodo.

Una soluzione ammissibile per il TSP con questi vincoli corrisponde ancora ad un ciclo hamiltoniano.

Se, per assurdo, non fosse un ciclo hamiltoniano dovrebbe contenere un sottociclo. In realtà, dai vincoli di uguaglianza deduciamo che dovrebbe contenere almeno due sottocicli. Di questi, uno sicuramente non conterrà il nodo v = 1. Ma allora, per questo sottociclo il vincolo precedente sarebbe violato!!!

∑ ^x_ij < |S|– 1 2 < |S| < n–1, 1 ∉S

ij∈E(S)

Esempio: TSP simmetrico

Pertanto possiamo riformulare il problema come segue:

Formulazione:

min

∑

∑

∑

∑

∑

ij∈E

ij∈δ(1)

ij∈E(S)

ij∈E

ij∈δ(i)

Esempio: TSP simmetrico

Dato che il problema così formulato è difficile da risolvere, proviamo ad applicare il rilassamento lagrangiano rilassando gli n – 1 vincoli di uguaglianza sui nodi

Problema Lagrangiano:

L(

λ

∑

∑ λ

( ∑

∑

∑

∑

x_ij ∈{0, 1} per ogni ij ∈E

ij∈E

ij∈δ(1)

ij∈E(S)

ij∈E

ij∈δ(i) i =2

n

Esempio: TSP simmetrico

Le soluzioni ammissibili del problema lagrangiano sono tutti gli 1-alberi sul grafo iniziale in cui ogni arco ij ha peso

c_ij –

λ

λ

Pertanto, il problema lagrangiano è facile da risolvere.

Ad una generica iterazione i, dato il moltiplicatore

λ ' ,

s⁽ⁱ⁾ = 2 –

∑

dove x' è la soluzione ottima del corrispondente problema lagrangiano L(

λ '

||s||²=

∑ ( ∑

i =2 n

ij∈δ(i) ij∈δ(i)