Algorithmen für konvexes Problem
Methode des steilsten Abstiegs
Diese Methode wird auch als Gradientenmethode oder Cauchy's-Methode bezeichnet. Diese Methode umfasst die folgenden Terminologien:
$$ x_ {k + 1} = x_k + \ alpha_kd_k $$
$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ oder $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $
Sei $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $
Durch Differenzieren von $ \ phi $ und Gleichsetzen mit Null können wir $ \ alpha $ erhalten.
Der Algorithmus lautet also wie folgt:
Initialisieren Sie $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ und setzen Sie $ k = 0 $.
Setze $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ oder $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.
finde $ \ alpha_k $ so, dass $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $ minimiert wird.
Setze $ x_ {k + 1} = x_k + \ alpha_kd_k $.
Wenn $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ oder $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, gehe zu Schritt 6, andernfalls setze $ k = k + 1 $ und gehe zu Schritt 2.
Die optimale Lösung ist $ \ hat {x} = x_ {k + 1} $.
Newton-Methode
Die Newton-Methode arbeitet nach folgendem Prinzip:
$ f \ left (x \ right) = y \ left (x \ right) = f \ left (x_k \ right) + \ left (x-x_k \ right) ^ T \ bigtriangledown f \ left (x_k \ right) + \ 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) $
Bei $ x_ {k + 1} ist \ 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) $
Damit $ x_ {k + 1} $ die optimale Lösung ist $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $
Somit ist $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $
Hier sollte $ H \ left (x_k \ right) $ nicht singulär sein.
Daher lautet der Algorithmus wie folgt:
Step 1 - Initialisieren Sie $ x_0, \ varepsilon $ und setzen Sie $ k = 0 $.
Step 2 - finde $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.
Step 3 - Löse nach dem linearen System $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ für $ h \ left (x_k \ right) $.
Step 4 - finde $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.
Step 5- Wenn $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ oder $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ dann gehe zu Schritt 6, sonst setze $ k = k + 1 $ und gehe zu Schritt 2.
Step 6 - Die optimale Lösung ist $ \ hat {x} = x_ {k + 1} $.
Gradientenmethode konjugieren
Diese Methode wird zur Lösung der folgenden Probleme verwendet:
$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $
wobei Q eine positiv definierte nXn-Matrix ist und b konstant ist.
Wenn $ x_0, \ varepsilon gegeben ist, berechnet $ $ g_0 = Qx_0-b $
Setze $ d_0 = -g_0 $ für $ k = 0,1,2, ..., $
Setze $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $
Berechnen Sie $ x_ {k + 1} = x_k + \ alpha_kd_k $
Setze $ g_ {k + 1} = g_k + \ alpha_kd_k $
Berechnen Sie $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $
Berechnen Sie $ x_ {k + 1} = x_k + \ alpha_kd_k $
Setze $ g_ {k + 1} = x_k + \ alpha_kQd_k $
Berechnen Sie $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $
Setze $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.