Algorithmes pour problème convexe

Méthode de descente la plus raide

Cette méthode est également appelée méthode Gradient ou méthode de Cauchy. Cette méthode implique les terminologies suivantes -

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

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

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

En différenciant $ \ phi $ et en l'assimilant à zéro, nous pouvons obtenir $ \ alpha $.

Donc, l'algorithme va comme suit -

  • Initialisez $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ et définissez $ k = 0 $.

  • Définissez $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ droit \ |} $.

  • trouver $ \ alpha_k $ tel qu'il minimise $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

  • Définissez $ x_ {k + 1} = x_k + \ alpha_kd_k $.

  • Si $ \ left \ | x_ {k + 1-x_k} \ droit \ | <\ varepsilon_1 $ ou $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, passez à l'étape 6, sinon définissez $ k = k + 1 $ et passez à l'étape 2.

  • La solution optimale est $ \ hat {x} = x_ {k + 1} $.

Méthode Newton

La méthode Newton fonctionne sur le principe suivant -

$ 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} \ gauche (x-x_k \ droite) ^ TH \ gauche (x_k \ droite) \ gauche (x-x_k \ droite) $

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

À $ 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 \ droite) $

Pour que $ x_ {k + 1} $ soit la solution optimale $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

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

Ici, $ H \ left (x_k \ right) $ doit être non singulier.

Par conséquent, l'algorithme va comme suit -

Step 1 - Initialisez $ x_0, \ varepsilon $ et définissez $ k = 0 $.

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

Step 3 - Résoudre pour le système linéaire $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ pour $ h \ left (x_k \ right) $.

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

Step 5- Si $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ ou $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ puis passez à l'étape 6, sinon définissez $ k = k + 1 $ et passez à l'étape 2.

Step 6 - La solution optimale est $ \ hat {x} = x_ {k + 1} $.

Méthode de gradient conjugué

Cette méthode est utilisée pour résoudre les problèmes des types suivants -

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

où Q est une matrice nXn définie positive et b est constant.

Étant donné $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

Définissez $ d_0 = -g_0 $ pour $ k = 0,1,2, ..., $

Définir $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

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

Définir $ g_ {k + 1} = g_k + \ alpha_kd_k $

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

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

Définir $ g_ {k + 1} = x_k + \ alpha_kQd_k $

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

Définissez $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.