Metodo del Punto Interno in Programmazione Lineare
Si scriva un programma Matlab che implementi il metodo del punto interno per la programmazione lineare, e si risolva il seguente problema:
min x 1 − x 2
−x 1 + x 2 ≤ 1 x 1 + x 2 ≤ 3 x 1 , x 2 ≥ 0
a partire dal punto ammissibile ¯ x = (1, 1). Si risolva il medesimo problema con il metodo del simplesso usando AMPL e il solutore CPLEX. Si verifichi che la soluzione trovata dal metodo del punto interno non `e su un vertice del poliedro ammissibile, mentre quella trovata da CPLEX s`ı, e se ne spieghi il motivo. Si commenti sulla possibile caratterizza- zione univoca dell’insieme delle soluzioni ottimali di un problema di PL. Si risolva poi il problema:
min 1 2 x 1 − x 2
−x 1 + x 2 ≤ 1 x 1 + x 2 ≤ 3 x 1 , x 2 ≥ 0
(in cui la funzione obiettivo `e stata modificata). In questo caso le soluzioni fornite dai
due metodi sono uguali? Perch´e?
Soluzione
Utilizzeremo un metodo del punto interno che risolve problemi di PL in forma standard [P] min{c ⊤ x | Ax = b ∧ x ≥ 0}.
Sia x ∗ la soluzione di P. Il problema `e prima di tutto riformulato (e parametrizzato) come segue:
[P(β)] min c ⊤ x − β
n
P
j=1
ln x j
s.t. Ax = b.
dove β ≥ 0 `e un parametro. Sia x ∗ (β) la soluzione di P(β). L’obiettivo di questa riformulazione `e quello di eliminare i vincoli x ≥ 0 “spostandoli” nella funzione obiettivo.
Dato che − ln x j → ∞ per x j → 0, la modifica alla funzione obiettivo fa s`ı che pi` u un punto si avvicina alla frontiera della regione ammissibile, pi` u il valore della funzione obiettivo cresce. Dato che vogliamo minimizzare questo valore, i punti privilegiati saranno quelli interni. Utilizzeremo questa forma parametrizzata per risolvere il problema P. Per ogni β > 0 si ha che la soluzione x ∗ (β) a P(β) soddisfa a Ax = b e x > 0 (infatti la funzione obiettivo non `e definita se x ∗ j (β) = 0 per qualche j ≤ n). Richiedendo che β → 0 permettiamo a x di avvicinarsi alla frontiera (in altre parole, diminuiamo l’influenza della barriera logaritmica sul valore della funzione obiettivo) minimizzando c ⊤ x e mantenendo l’ammissibilit`a a Ax = b. Pertanto, intuitivamente, x ∗ (β) → x ∗ per β → 0. Si veda il Riquadro 1 per una spiegazione pi` u esauriente.
Il metodo del punto interno che utilizzeremo si basa su una successione (β k ) con β k ≥ 0 per ogni k ∈ N e β k → 0 per k → ∞. Per ogni k ∈ N, viene calcolata la soluzione x ∗ (β k ) a P(β k ). La soluzione corrispondente duale ammissibile `e data da y ∗ j (β k ) = x∗β
j
(β
k) , come specificato nel Riquadro 1. Dato che per ogni k e per ogni j ≤ n abbiamo x ∗ j (β k )y j ∗ (β k ) = β , otterremo anche che y ∗ (β k )x ∗ (β k ) = P
j≤n
y i ∗ (β k )x ∗ i (β k ) = P
j≤n
β = nβ. Dato inoltre che la Lagrangiana di P `e:
L(x, y, z) = c ⊤ x −
n
X
j=1
y j x j + z(Ax − b),
e che l’ammissibilit`a rispetto a Ax − b deve essere sempre mantenuta ad ogni iterazione (e quindi Ax − b = 0), abbiamo che per ogni soluzione di P(β k ),
L(x ∗ (β k ), y ∗ (β k ), z ∗ ) = c ⊤ x ∗ − nβ k .
Pertanto, il salto di dualit`a `e dato proprio da nβ k . Terminando il processo iterativo ad un’iterazione K tale che nβ K < ε, dove ε > 0 `e un parametro prefissato tale che ε << 1, si avr`a che la soluzione ottenuta x ∗ (β K ) ha un valore della funzione obiettivo che non `e distante pi` u di ε dal valore ottimale (questa considerazione `e alla base della dimostrazione che questo algoritmo risolve problemi di PL in tempo polinomiale rispetto alla dimensione dell’istanza).
Fatte queste considerazioni, `e possibile derivare un metodo iterativo che risolva il
problema P.
Riquadro 1.
Verifichiamo che x ∗ (β) (soluzione di P(β)) converge a x ∗ (soluzione di P) per β → 0.
Mostriamo prima di tutto che per ogni soluzione x ∗ (β k ) (ottima in P(β) e ammissibile in P) si pu` o facilmente calcolare la corrispondente soluzione duale ammissibile (sia in P(β) che in P).
Si considerino le variabili duali y j relative ai vincoli di nonnegativit` a di x espressi nella forma
“inversa” −x j ≤ 0 per j ≤ n. La funzione Lagrangiana del problema P `e:
L(x, y, z) = c ⊤ x −
n
X
j=1
y j x j + z(Ax − b),
e la funzione Lagrangiana del problema P(β) `e:
L β (x, z) = c ⊤ x(β) − β
n
X
j=1
ln x j (β) + z(Ax − b).
Richiedere che x sia primale ammissibile e (y, z) duale ammissibile di P significa imporre la condizione ∇L = 0, ovvero
∀j ≤ n (c j − y j + zA j = 0),
dove A j `e la j-esima colonna di A. Ora imponiamo che x sia primale ammissibile e z duale ammissibile in P(β) mediante l’equazione ∇L β = 0, ovvero
∀j ≤ n (c j − β x j
+ zA j = 0).
Si consideri ora che essendo x ∗ (β) una soluzione di P(β), soddisfa alla condizione di ottimalit` a
∇L β (x ∗ (β), z ∗ ) = 0 (ammissibilit` a primale/duale in P(β)). Definendo y j ∗ (β) = x
∗β
j
(β) otteniamo
∇L(x ∗ (β), y ∗ (β), z ∗ ) = 0, ovvero l’ammissibilit` a primale/duale in P, perci`o x ∗ `e primale ammis- sibile e y ∗ duale ammissibile (corrispondente ai vincoli x ≥ 0) del problema P. In sintesi, da ogni soluzione ottima x ∗ (β) di P(β) possiamo facilmente ricavare una soluzione duale ammissibile y ∗ (β) di P tale che x ∗ j (β)y j ∗ (β) = β per ogni j ≤ n.
Ora, per β → 0, otteniamo che la coppia primale/duale (x ∗ (β), y ∗ (β)) converge a una coppia (x ′ , y ′ ). Dato che x ∗ j (β)y ∗ j (β) = β per ogni j ≤ n e per ogni β > 0, si ha che x ∗ j (β)y ∗ j (β) → 0 per β → 0 e quindi x ′ j y ′ j = 0 per ogni j ≤ n. Quindi per costruzione x ′ e y ′ soddisfano le equazioni degli scarti complementari ∀j ≤ n (x j y j = 0) derivate dal problema P. Ci` o significa che (x ′ , y ′ ) `e una coppia primale/duale ottima per P, ovvero x ′ = x ∗ , come volevasi dimostrare.
Figura 1: Dimostrazione che x ∗ (β) → x ∗ per β → 0.
1. Si consideri un valore iniziale per β 1 con x(β 1 ) ammissibile in P tale che x(β 1 ) > 0.
Siano α < 1 e ε > 0 dei parametri. Sia k = 1.
2. Si risolva P(β k ) dal punto iniziale x(β k ) ottenendo una soluzione x ∗ (β k ).
3. Se nβ k < ε, l’algoritmo termina con soluzione x ∗ (β k ).
4. Sia β k+1 = αβ k , x(β k+1 ) = x ∗ (β k ) e k ← k + 1.
5. Si ripeta dal passo 2.
L’unico punto ancora da chiarire `e: come risolvere P(β k ) partendo dalla soluzione iniziale ammissibile x(β k )? Si noti che P(β k ) `e un problema nonlineare convesso; pu`o quindi essere risolto con il metodo di Newton (si veda il Riquadro 2).
Riquadro 2.
In generale, la direzione d di Newton per un problema senza vincoli min f (x) in un punto ¯ x, con f convessa, `e data da:
d = −(∇ 2 f (¯ x )) −1 ∇f (¯ x ).
Dato che ∇ 2 f (¯ x) `e positiva definita (per la convessit` a di f ), si ottiene (∇f (¯ x)) ⊤ d = −(∇f (¯ x)) ⊤ (∇ 2 f (¯ x)) −1 ∇f (¯ x) < 0, quindi d `e una direzione di diminuzione per il valore della funzione obiettivo.
In questo caso, dobbiamo trovare una direzione di diminuzione che sia anche ammissibile per Ax = b, cio`e A(¯ x + d) = b, quindi A¯ x + Ad = b e pertanto, dato che A¯ x = b, tale che Ad = 0.
Risolviamo quindi il sistema:
∇ 2 f (¯ x) A ⊤
A 0
d z ⊤
=
−∇f (¯ x) 0
,
per (d, z), dove z sono le variabili duali associate ai vincoli Ax = b. L’aggiornamento iterativo di x `e x = ¯ x + γd, dove γ `e il risultato di una ricerca monodimensionale, per esempio:
γ = argmin s≥0 f(¯ x + sd).
Si noti che ¯ x + γd `e ammissibile in Ax = b per ogni γ ≥ 0 perch´e Ax = A¯ x + Aγd = b + γAd = b dato che Ad = 0 per costruzione.
Figura 2: Metodo di Newton per l’ottimizzazione di problemi convessi soggetti a vincoli lineari in forma di equazione.
Nel nostro caso specifico dobbiamo risolvere il problema P(β) definito come:
x
1,x min2,x
3,x
4
x 1 − x 2 − β
4
P
j=1
ln x j
−x 1 + x 2 + x 3 = 1 x 1 + x 2 + x 4 = 3.
La matrice A `e:
−1 1 1 0 1 1 0 1
. Il gradiente della funzione obiettivo `e dato da
(1 − β
x 1 , −1 − β x 2 , − β
x 3 , − β x 4 )
⊤
, e l’Hessiana `e
diag( β x 2 1 , β
x 2 2 , β x 2 3 , β
x 2 4 ).
Il sistema da risolvere nel metodo di Newton `e quindi:
β
x
21−1 1
β
x
221 1
β
x
231 0
β
x
240 1
−1 1 1 0
1 1 0 1
d 1 d 2 d 3 d 4 z 1 z 2
=
−1 + x β
1
1 + x β
2
β x
3β x
40 0
,
Abbiamo ora tutti gli elementi per scrivere un codice Matlab 1 che implementa il metodo del punto interno descritto. Il codice consta di due file, ipm.m e linesearch.m.
% file ipm.m - metodo del punto interno per PL
function [xstar, ystar, k, B] = ipm(c, A, b, beta, xfeas, alpha, epsilon)
%% initialization OPTIONS = [ ];
[m, n] = size(A);
Ineq = A(:, 1 : n-m);
nx = size(xfeas);
if nx < n
s = b - Ineq*xfeas;
x = [ xfeas ; s ];
else
x = xfeas;
end
J = zeros(n, 1);
H = zeros(n, n);
d = zeros(n, 1);
nu = zeros(m, 1);
termination = 0;
counter = 1;
%% iterative method while termination == 0
for i = 1 : n
J(i) = c(i) - beta / x(i);
H(i,i) = beta/x(i)^2;
end
N = [ H, A’; A, zeros(m, m) ];
bN = [ -J; zeros(m, 1) ];
direction = N \ bN;
d = direction(1 : n, 1);
nu = direction(n + 1 : n + m);
lambda = fminbnd(’linesearch’, 0, 1, OPTIONS, c, x, d, beta);
xstar = x + lambda * d;
1 Il codice funziona anche sul software GNU Octave, versione 2.1.64, con pacchetti aggiuntivi Octave-
forge.
if n * beta < epsilon termination = 1;
k = counter;
ystar = beta ./ xstar;
B = zeros(1, n);
for i = 1 : n
if xstar(i) > ystar(i) B(i) = 1;
end end end
beta = alpha * beta;
x = xstar;
counter = counter + 1;
end
%end function
function y = linesearch(lambda, c, x, d, beta)
y = c*(x + lambda*d) - beta*sum(log(x + lambda*d),1);
%end function
Utilizziamo i parametri β 1 = 1, α = 0.5, ε = 0.01. Si ricordi che c ⊤ = (1, −1, 0, 0), b ⊤ = (1, 3) e x(β 1 ) ⊤ = (1, 1).
Per eseguire il codice diamo il comando:
ipm([1 -1 0 0 ], [-1 1 1 0 ; 1 1 0 1], [1; 3], 1, [1; 1], 0.5, 0.01)
ottenendo come soluzione x ∗ = (0.5777, 1.5763, 0.0015, 0.8460). L’algoritmo traccia la successione di punti illustrata in Figura 3. Si noti che la soluzione ottimale x ∗ non `e su un vertice del poliedro.
0 0.5 1 1.5 2 2.5 3
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
Figura 3: Punti x ∗ (β k ) individuati dall’algoritmo.
Utilizziamo adesso il modello AMPL:
# file: ipm-simplex.mod var x{1..4} >= 0;
minimize f : x[1] - x[2];
c1 : -x[1] + x[2] + x[3] = 1;
c2 : x[1] + x[2] + x[4] = 3;
option solver cplex;
solve;
display x;
display x.lrc;
L’istruzione display x.lrc stampa i costi ridotti delle variabili al loro limite inferiore;
in pratica, sono i valori ottimali delle variabili duali y ∗ relative ai vincoli di nonnegati- vit`a x ≥ 0. Utilizziamo il comando ampl < ipm-simplex.mod per eseguire il modello, ottenendo la soluzione x s = (0, 1, 0, 2) e y s = (0, 0, 1, 0), che corrisponde a un vertice del poliedro.
La soluzione trovata con il metodo del punto interno `e diversa da quella trovata dal metodo del simplesso. In particolare, la seconda si trova su un vertice del poliedro e la prima no. Questo succede perch´e il gradiente della funzione obiettivo `e perpendicolare alla retta −x 1 + x 2 = 1 relativa al primo vincolo, e quindi tutti i punti sul segmento tra R = (0, 1) e S = (1, 2) sono ottimali; in altre parole, esiste una faccia ottimale del poliedro, piuttosto che un unico vertice ottimale.
Riquadro 3.
Mentre il metodo del simplesso non permette una caratterizzazione univoca di una moltitudine di soluzioni ottimali, col metodo del punto interno questo `e possibile. La traiettoria definita da x ∗ (β) per β → 0 traccia un cammino interno al poliedro ammissibile chiamato cammino centrale.
Il cammino centrale converge a una soluzione ottimale del problema P che ha particolari propriet` a geometriche: per il teorema di Goldman-Tucker (1956) si ha infatti che se (x ∗ , y ∗ ) `e una coppia primale/duale ottenuta come punto di convergenza del cammino centrale, allora (x ∗ , y ∗ ) `e una coppia strettamente complementare, ovvero tale per cui valgono:
∀j ≤ n (x ∗ j y ∗ j = 0)
∀j ≤ n (x ∗ j + y ∗ j > 0).
Si noti che la soluzione (x s , y s ) ottenuta con il metodo del simplesso non `e strettamente comple- mentare, infatti si ha che x s 1 + y 1 s = 0 + 0 = 0. Tutte le soluzioni strettamente complementari possono essere univocamente associate a una partizione di {1, . . . , n} chiamata partizione ottimale che identifica l’insieme delle soluzioni ottimali di un problema di PL. La partizione ottimale B, N
`e definita come B = {j ≤ n | x ∗ i > 0} e N = {j ≤ n | y i ∗ > 0}. Nel nostro caso abbiamo che B = {1, 2, 4} e N = {3}, che implica che le soluzioni ottimali si trovano sulla faccia identificata da x 3 = 0 (ovvero il segmento RS).
Figura 4: Definizione di partizione ottimale.
Per concludere l’esercizio, risolviamo con i due metodi il problema modificato in cui c ⊤ = ( 1 2 , −1, 0, 0), ottenendo
x ∗ = (0.998, 1.996, 0.001, 0.005) y ∗ = (0.001, 0.001, 0.757, 0.248) x s = (1, 2, 0, 0)
y s = (0, 0, 0.75, 0.25).
La tolleranza d’errore abbastanza lasca ε = 0.01 data come parametro al punto interno giustifica la differenza di valori tra le due soluzioni, ma `e evidente che la soluzione del punto interno converge in effetti allo stesso valore di quella del simplesso, come si pu`o vedere dal cammino centrale in Figura 5. In una implementazione realistica del metodo del punto interno l’approssimazione “al vertice pi` u vicino” farebbe parte dell’algoritmo stesso; essa svolge inoltre un ruolo teorico notevole nella dimostrazione di complessit`a polinomiale del metodo). Il metodo del punto interno fornisce una partizione ottimale B = {1, 2}, N = {3, 4} che implica che le soluzioni ottimali si trovano sulla faccia identificata da x 3 = x 4 = 0 (ovvero il punto S = (1, 2)) (si veda il Riquadro 3). Dato che in questo caso la faccia consiste di un solo punto, anche il metodo del simplesso d`a la medesima soluzione ottimale;
per il teorema di Goldman-Tucker si deve ottenere quindi che la soluzione ottimale fornita dal metodo del simplesso `e strettamente complementare, cosa che pu`o facilmente essere verificata numericamente dato che 1 + 0 > 0, 2 + 0 > 0, 0 + 0.75 > 0 e 0 + 0.25 > 0.
0 0.5 1 1.5 2 2.5 3
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
