Stima di parametri

Stima di parametri

Il gestore di un sito turistico dove si pratica il bungee-jumping deve fornire alla so- vrintendenza municipale un documento che riguarda la sicurezza del servizio fornito. Il documento chiede in particolare che siano stimate la costante di rigidit`a della corda (ap- prossimata in questo caso a una molla) e il coefficiente di frizione dell’aria durante la caduta (si assume che non ci sia vento). Il gestore dispone di un campionamento di 10 osservazioni (prese in vari istanti temporali) che riguardano posizione verticale, velocit`a e accelerazione di un corpo da 75kg in caduta, come da tavola seguente.

Campione Posizione Velocit` a Accelerazione

1 0.00000 0.00000 9.80000

2 1.49407 4.09921 2.51785

3 5.08617 3.69224 -1.91904

4 8.13735 -0.01369 -2.40609

5 4.19690 -4.08376 -1.49847

6 0.47600 -2.74398 6.82717

7 0.31475 2.27558 7.77440

8 3.11767 4.36378 -0.58929

9 7.16305 2.15017 -2.33155

10 6.99693 -2.32061 -2.31096

Si formuli un modello di programmazione matematica senza vincoli per risolvere il pro-

blema, e si risolva l’istanza considerata per mezzo di Matlab.

Le forze agenti sul corpo in caduta sono: la gravit`a F 1 (t) = mg (dove m `e la massa del corpo e g `e l’accelerazione di gravit`a), la tensione della corda elastica (si assume l’utilizzo della forza di Hooke con coefficiente k) F 2 (t) = −kx(t) e l’attrito dell’aria con coefficiente f , che dipende dal quadrato della velocit`a: F 3 (t) = −f v(t) <sup>2</sup> , dove x(t) e v(t) sono la posizione verticale (si assume che la direzione positiva sia verso il basso) e la velocit`a del corpo al tempo t. L’equazione di moto del corpo `e:

F (t) =

3

X

i=1

F i (t) = ma(t),

dove a(t) `e l’accelerazione del corpo al tempo t. Di qui si ottiene ¨ x = g − _m ^k x − _m ^f ˙x ² , dove

˙x = v e ¨ x = a. Le costanti g, k, f sono tutte non negative. Il problema chiede di usare le osservazioni campionate per effettuare una stima di k e f . Riscriviamo l’equazione di moto usando i simboli (x, v, a); otteniamo

a + k

m x + f

m v ² − g = 0. (1)

In altre parole, le triple (x ⁱ , v ⁱ , a ⁱ ) campionate (per i ≤ n, con n = 10) devono obbedire approssimativamente al modello lineare (1). Avremo dunque, per ogni i ≤ n,

a ⁱ + k

m x ⁱ + f

m (v ⁱ ) ² − g =  i ,

dove  i `e un errore sperimentale. L’errore accumulato su tutti i campionamenti `e dato da  = P n

i=1 || i || ² . Il problema da risolvere `e quello di minimizzare l’errore accumulato come funzione dei parametri da stimare k, f :

min k,f n

X

i=1

ka ⁱ + k

m x ⁱ + f

m (v ⁱ ) ² − gk ² . (2)

Dato che la funzione norma `e convessa (si veda il Riquadro 1), che il quadrato di una funzione non-negativa convessa `e convesso (si veda il Riquadro 2) e che la somma di fun- zioni convesse `e convessa (si veda il Riquadro 3), il problema (2) `e un problema nonlineare convesso. Dato infine che in un problema convesso ogni ottimo locale `e anche un ottimo globale (si veda il Riquadro 4), il problema pu`o essere risolto mediante un algoritmo di ottimizzazione locale come per esempio il metodo di Newton (si veda il Riquadro 5).

Dato che per ogni i ≤ n si ha che ka ⁱ + k

m x ⁱ + f

m (v ⁱ ) ² − gk ² =

= (a ⁱ − g) ² + 2x ⁱ

m (a ⁱ − g)k + 2(v ⁱ ) ²

m (a ⁱ − g)f + (x ⁱ /m) ² k ² + ( 2x ⁱ (v ⁱ ) ²

m ² )kf + ((v ⁱ ) ² /m) ² f ² ,

Riquadro 1.

Una funzione f : S ⊆ R

→ R si dice convessa su S se per ogni x, y ∈ S e per ogni λ ∈ [0, 1] si ha:

f(λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). (3) Geometricamente, questo significa che il segmento tra (x, f (x)) e (y, f (y)) si trova sopra il valore di f valutato per ogni punto del segmento.

Consideriamo ora f (x) = ||x||, dove || · || `e una norma (non si assume necessariamente la norma Euclidea). Si ha ||λx + (1 − λ)y|| ≤ ||λx|| + ||(1 − λ)y|| per la disuguaglianza triangolare; dato che la norma `e lineare rispetto alla moltiplicazione scalare, si ha anche

||λx + (1 − λ)y|| ≤ λ||x|| + (1 − λ)||y||, che prova la convessit`a della norma.

Figura 1: Convessit`a della norma.

Riquadro 2.

Sia f : S ⊆ R

→ R

una funzione convessa su S a valori non-negativi; si ha dunque che per x, y ∈ S e λ ∈ [0, 1], f (λx+(1−λ)y) ≤ λf (x)+(1−λ)f (y). Sia ora g : R → R data da g(x) = x

(si dimostri, come esercizio, che g `e convessa su R). Si consideri la funzione h data dalla composizione di g e f : dimostriamo che h = g ◦ f `e una funzione convessa. Siano x, y ∈ S e λ ∈ [0, 1]. Per la convessit`a di f , si ha f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). Dato che f ha valori non-negativi, g

`e non decrescente (il quadrato di quantit`a positive `e una funzione strettamente crescente), quindi mantiene la direzione delle disuguaglianze. In particolare, g(f (λx + (1 − λ)y)) ≤ g(λf (x) + (1 − λ)f (y)). Ora, dato che g `e convessa, si ha g(λf (x) + (1 − λ)f (y)) ≤ λg(f (x)) + (1 − λ)g(f (y)).

Dalle due disuguaglianze si desume che h(λx + (1 − λ)y) ≤ λh(x) + (1 − λ)h(y), che implica che h `e convessa. Si noti che questa dimostrazione vale per ogni coppia di funzioni convesse f, g con g non descrescente e tali che la composizione g ◦ f possa essere definita.

Figura 2: Il quadrato di una funzione convessa `e convesso.

la funzione obiettivo di (2) pu`o essere scritta come F (k, f ) = c 1 + c 2 k + c 3 f + c 4 k ² + c 5 kf + c 6 f ² , dove

c 1 =

n

P

i=1

(a ⁱ − g) ² , c 2 =

n

P

i=1

2x

(a

−g)

m , c 3 =

n

P

i=1

2(v

)

(a

−g)

m ,

c 4 =

n

P

i=1

(x ⁱ /m) ² , c 5 =

n

P

i=1 2x

(v

)

m

, c 6 =

n

P

i=1

(v ⁱ ) ⁴ /m ² .

Dunque il problema min F (k, f ) `e un problema di minimizzazione della forma quadratica convessa in due variabili raffigurata in Fig. 7.

Verifichiamo ora che il metodo di Newton pu`o essere utilizzato per la soluzione del

Siano f, g : S ⊆ R

→ R due funzioni convesse su S, e siano x, y ∈ S e λ ∈ [0, 1]. Si ha allora che f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)

g(λx + (1 − λ)y) ≤ λg(x) + (1 − λ)g(y)

da cui f (λx + (1 − λ)y) + g(λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) + λg(x) + (1 − λ)g(y), e quindi (f + g)(λx + (1 − λ)y) ≤ λ(f + g)(x) + (1 − λ)(f + g)(y), che dimostra la convessit`a di f + g.

Figura 3: La somma di funzioni convesse `e convessa.

Riquadro 4.

Sia f : S ⊆ R

→ R una funzione convessa su S. Dimostriamo che se x

∈ S `e un minimo locale, allora `e anche un minimo globale.

Il fatto che x

sia un minimo locale di f rispetto a S implica che esiste una sfera B(x

, ε) ⊂ S (con centro in x

e raggio ε > 0) tale che

∀ x ∈ B(x

, ε (f (x

) ≤ f (x)).

Si consideri ora un qualsiasi punto x ∈ S tale che x 6= x

. ` E facile verificare che possiamo scegliere un punto ¯ x 6= x

sul segmento tra x

e x tale che ¯ x ∈ B(x

, ε); cio`e che esiste λ ∈ (0, 1] tale che

¯

x = λx

+ (1 − λ)x. Per la convessit`a di f si ottiene f (¯ x) ≤ λf (x

) + (1 − λ)f (x), che pu`o essere scritto come

f (x) ≥ f (¯ x ) − λf (x

) 1 − λ .

Dato che ¯ x ∈ B(x

, ε), per la minimalit`a locale di x

, si ha f (¯ x) ≥ f (x

), e quindi

f (x) ≥ f (x

) − λf (x

)

1 − λ = f (x

).

Abbiamo quindi mostrato che per ogni x 6= x

in S si ha f (x

) ≤ f (x), che prova che x

`e un minimo globale.

Figura 4: Ogni ottimo locale di un problema convesso `e anche globale.

problema. L’Hessiana `e H = ∇ ² F =  2c 4 c 5

c 5 2c 6



. Si ottengono facilmente i valori numerici per c = (c ₁ , . . . , c ₆ ) e per gli autovalori λ ₁ , λ ₂ di H:

c = (881.74, −11.288, −21.935, 0.0395, 0.1066, 0.221) λ 1 = 0.050011

λ 2 = 0.470989,

da cui si desume che l’Hessiana `e definita positiva (quindi il metodo di Newton converge

per quanto detto nel Riquadro 5). Inoltre, dato che la funzione obiettivo `e quadratica, `e

sufficiente effettuare una sola iterazione del metodo di Newton (Riquadro 6).

Riquadro 5.

In generale, i metodi di programmazione nonlineare per problemi senza vincoli nella forma min

f (x) sono dei metodi iterativi in cui viene mantenuta una soluzione x all’iterazione corrente, e la soluzione x

all’iterazione successiva viene definita come

x

= x − γD∇f (x), (4)

dove D `e una matrice definita positiva. In questo modo, si ha che la retta tra x e x

ha direzione d = −D∇f (x). Dato che D `e definita positiva, per ogni vettore v si ha v

Dv > 0, e quindi (∇f (x))

D∇f (x) > 0, da cui (∇f (x))

d < 0, e quindi d `e una direzione di diminuzione per il valore della funzione obiettivo. Il metodo cos`ı definito converge a un ottimo locale. L’ordine di convergenza dipende dalla scelta della matrice D. Nel metodo di Newton si utilizza D = (∇

f (x))

, ovvero l’inversa dell’Hessiana della funzione obiettivo. Se f `e due volte differenziabile e convessa su S, si pu`o dimostrare che l’Hessiana `e semidefinita positiva per ogni punto in S, ma non definita positiva; perci`o il metodo di Newton potrebbe anche non convergere. Vedremo per`o che nel caso del problema (2) l’Hessiana `e definita positiva, e quindi il metodo di Newton converge.

Figura 5: Metodo di Newton per problemi senza vincoli.

Riquadro 6.

Si dimostra inoltre che il metodo di Newton, con γ = 1, applicato a una funzione quadratica convessa, converge in una iterazione.

Si consideri l’espansione di Taylor al secondo ordine ˆ f (x+d) = f (x)+∇f (x)

d +

d

(∇

f (x))

d di f a x. Se f `e quadratica convessa, si ha che f (x + d) = ˆ f (x + d). Le condizioni di ottimalit`a per f (x + d) sono ∇f (x + d) = 0, che significa ∇f (x) + ∇

f (x)d = 0. Ne segue che d =

−(∇

f(x))

∇f (x); dunque d `e tale che f ha un minimo a x + d. Dato che alla prima iterazione del metodo di Newton si ha l’aggiornamento x ← x + d, la tesi `e dimostrata.

Figura 6: Convergenza del metodo di Newton per funzioni quadratiche convesse.

A questo punto possiamo scrivere il codice Matlab.

• objfun.m: calcola il valore della funzione obiettivo in un punto x = (k, f ).

% objfun.m

function F = objfun(x, c) c1 = c(1);

cprime = [c(2) c(3)];

H = [2*c(4), c(5) ; c(5), 2*c(6)];

F = c1 + cprime*x + 0.5 * x’*H*x;

%end function

• gradobjfun.m: calcola il gradiente della funzione obiettivo in un punto x = (k, f ).

0 100 200 300

0 10 20 f 30 40 50

100

150 k

Figura 7: La funzione obiettivo.

% gradobjfun.m

function gof = gradobjfun(x, c)

gf1 = c(2) + 2*c(4)*x(1) + c(5)*x(2);

gf2 = c(3) + c(5)*x(1) + 2*c(4)*x(2);

gof = [gf1; gf2];

%end function

• newton.m: risolve il problema.

% newton.m

function [xstar, fstar, k] = newton(x) OPTIONS = [ ];

maxiterations = 1;

c = [ 881.74 -11.288 -21.935 0.0395 0.1066 0.221 ];

cprime = [c(2), c(3)];

H = [ 2*c(4), c(5) ; c(5), 2*c(6) ];

Hinv = H^(-1);

termination = 0;

counter = 1;

while termination == 0 gradF = gradobjfun(x, c);

d = -Hinv*gradF;

if (counter > maxiterations) termination = 1;

xstar = x;

fstar = objfun(x, c);

k = counter;

else

lambda = 1;

x = x + lambda*d;

counter = counter + 1;

end end

%end function

Scegliamo arbitrariamente il punto di partenza x = (0, 0); lanciamo il codice con il comando:

[xstar, fstar, k] = newton([0;0]) Si ottiene

xstar = 112.549

22.483

fstar = -0.063196 k = 2

Quindi l’ottimo ¹ `e x <sup>∗</sup> = (k <sup>∗</sup> , f <sup>∗</sup> ) = (112.549, 22.483). Il valore della funzione obiettivo `e negativo per via di errori numerici nei calcoli in floating point.

1

I dati sono stati ottenuti mediante una simulazione con k = 112.5 e f = 22.5, dunque l’errore `e

dell’ordine di grandezza di 10

.