Algoritmi per problemi convessi

Metodo di discesa più ripida

Questo metodo è anche chiamato metodo Gradient o metodo di Cauchy. Questo metodo prevede le seguenti terminologie:

$$ x_ {k + 1} = x_k + \ alpha_kd_k $$

$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ o $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $

Sia $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

Differenziando $ \ phi $ e equiparandolo a zero, possiamo ottenere $ \ alpha $.

Quindi l'algoritmo funziona come segue:

  • Inizializza $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ e imposta $ k = 0 $.

  • Imposta $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ o $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.

  • trova $ \ alpha_k $ tale da ridurre a icona $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

  • Imposta $ x_ {k + 1} = x_k + \ alpha_kd_k $.

  • Se $ \ sinistra \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ o $ \ sinistra \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, vai al passaggio 6, altrimenti imposta $ k = k + 1 $ e vai al passaggio 2.

  • La soluzione ottimale è $ \ hat {x} = x_ {k + 1} $.

Metodo Newton

Il metodo Newton funziona secondo il seguente principio:

$ f \ sinistra (x \ destra) = y \ sinistra (x \ destra) = f \ sinistra (x_k \ destra) + \ sinistra (x-x_k \ destra) ^ T \ bigtriangledown f \ sinistra (x_k \ destra) + \ frac {1} {2} \ left (x-x_k \ right) ^ TH \ left (x_k \ right) \ left (x-x_k \ right) $

$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x-x_k \ right) $

A $ x_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ right) $

Affinché $ x_ {k + 1} $ sia la soluzione ottimale $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

Quindi, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $

Qui $ H \ left (x_k \ right) $ dovrebbe essere non singolare.

Quindi l'algoritmo funziona come segue:

Step 1 - Inizializza $ x_0, \ varepsilon $ e imposta $ k = 0 $.

Step 2 - trova $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.

Step 3 - Risolvi per il sistema lineare $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ per $ h \ left (x_k \ right) $.

Step 4 - trova $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.

Step 5- Se $ \ sinistra \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ o $ \ left \ | \ bigtriangledown f \ sinistra (x_k \ destra) \ destra \ | \ leq \ varepsilon $ quindi vai al passaggio 6, altrimenti imposta $ k = k + 1 $ e vai al passaggio 2.

Step 6 - La soluzione ottimale è $ \ hat {x} = x_ {k + 1} $.

Metodo del gradiente coniugato

Questo metodo viene utilizzato per risolvere i problemi dei seguenti tipi:

$ min f \ sinistra (x \ destra) = \ frac {1} {2} x ^ T Qx-bx $

dove Q è una matrice nXn definita positiva eb è costante.

Dato $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

Imposta $ d_0 = -g_0 $ per $ k = 0,1,2, ..., $

Imposta $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

Calcola $ x_ {k + 1} = x_k + \ alpha_kd_k $

Imposta $ g_ {k + 1} = g_k + \ alpha_kd_k $

Calcola $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $

Calcola $ x_ {k + 1} = x_k + \ alpha_kd_k $

Imposta $ g_ {k + 1} = x_k + \ alpha_kQd_k $

Calcola $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $

Imposta $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.