La méthode de descente la plus raide (dans la littérature anglaise « méthode de descente la plus raide ») est une méthode numérique itérative (premier ordre) de résolution de problèmes d'optimisation, qui permet de déterminer l'extremum (minimum ou maximum) de la fonction objectif :

sont les valeurs de l'argument de la fonction (paramètres contrôlés) sur le domaine réel.

Conformément à la méthode considérée, l'extremum (maximum ou minimum) de la fonction objectif est déterminé dans le sens de l'augmentation (diminution) la plus rapide de la fonction, c'est-à-dire dans le sens du gradient (anti-gradient) de la fonction. Fonction de gradient en un point est un vecteur dont les projections sur les axes de coordonnées sont les dérivées partielles de la fonction par rapport aux coordonnées :

où i, j,…, n sont des vecteurs unitaires parallèles aux axes de coordonnées.

Dégradé au point de base est strictement orthogonal à la surface, et sa direction montre la direction de l'augmentation la plus rapide de la fonction, et la direction opposée (antigradient), respectivement, montre la direction de la diminution la plus rapide de la fonction.

La méthode de descente la plus raide est un développement ultérieur de la méthode de descente en pente. En général, le processus de recherche de l'extremum d'une fonction est une procédure itérative, qui s'écrit comme suit :

où le signe "+" est utilisé pour trouver le maximum d'une fonction, et le signe "-" est utilisé pour trouver le minimum d'une fonction ;

Vecteur de direction unitaire, déterminé par la formule :

- le module gradient détermine le taux d'augmentation ou de diminution de la fonction dans le sens du gradient ou de l'anti-gradient :

Une constante qui détermine la taille du pas et qui est la même pour toutes les i-èmes directions.

La taille du pas est choisie à partir de la condition du minimum de la fonction objectif f(x) dans la direction du mouvement, c'est-à-dire à la suite de la résolution du problème d'optimisation unidimensionnelle dans la direction du gradient ou de l'antigradient :

En d’autres termes, la taille du pas est déterminée en résolvant cette équation :

Ainsi, le pas de calcul est choisi de telle sorte que le mouvement soit effectué jusqu'à ce que la fonction s'améliore, atteignant ainsi un extremum à un moment donné. A ce stade, la direction de recherche est à nouveau déterminée (à l'aide du gradient) et un nouveau point optimal de la fonction objectif est recherché, etc. Ainsi, dans cette méthode, la recherche s'effectue par étapes plus grandes et le gradient de la fonction est calculé en un plus petit nombre de points.

Dans le cas d'une fonction à deux variables, cette méthode a l'interprétation géométrique suivante : la direction du mouvement à partir d'un point touche la ligne de niveau au point . La trajectoire de descente est en zigzag, avec des liens en zigzag adjacents orthogonaux les uns aux autres. La condition d'orthogonalité des vecteurs de directions de descente en points voisins s'écrit par l'expression suivante :

La trajectoire de mouvement jusqu'au point extremum en utilisant la méthode de descente la plus raide, représentée sur le graphique de la ligne d'égal niveau de la fonction f(x)

La recherche d'une solution optimale se termine à l'étape de calcul itératif (plusieurs critères) :

La trajectoire de recherche reste dans un petit voisinage du point de recherche actuel :

L'incrément de la fonction objectif ne change pas :

Le gradient de la fonction objectif au point minimum local devient nul :

Il convient de noter que la méthode de descente de gradient s'avère très lente lors du déplacement le long d'un ravin, et à mesure que le nombre de variables dans la fonction objectif augmente, ce comportement de la méthode devient typique. Le ravin est une dépression dont les lignes de niveau ont approximativement la forme d'ellipses dont les demi-axes diffèrent plusieurs fois. En présence d'un ravin, la trajectoire de descente prend la forme d'une ligne en zigzag avec un petit pas, ce qui ralentit considérablement la vitesse de descente qui en résulte au minimum. Ceci s'explique par le fait que la direction de l'antigradient de ces fonctions s'écarte sensiblement de la direction vers le point minimum, ce qui entraîne un retard supplémentaire dans le calcul. En conséquence, l’algorithme perd en efficacité de calcul.

Fonction ravin

La méthode du gradient, avec ses nombreuses modifications, est une méthode courante et efficace pour rechercher l'optimum des objets étudiés. L'inconvénient de la recherche par gradient (ainsi que des méthodes évoquées ci-dessus) est que lors de son utilisation, seul l'extremum local de la fonction peut être détecté. Pour trouver d’autres extrema locaux, il faut chercher à partir d’autres points de départ. En outre, la vitesse de convergence des méthodes de gradient dépend également de manière significative de la précision des calculs de gradient. La perte de précision, qui se produit généralement à proximité des points minimaux ou dans une situation de ravin, peut généralement perturber la convergence du processus de descente de gradient.

Méthode de calcul

Étape 1 : Définition d'expressions analytiques (sous forme symbolique) pour calculer le gradient d'une fonction

Étape 2: Définir l'approximation initiale

Étape 3 : La nécessité de redémarrer la procédure algorithmique pour réinitialiser la dernière direction de recherche est déterminée. Suite au redémarrage, la recherche est à nouveau effectuée dans le sens de la descente la plus rapide.

Figure 3. Interprétation géométrique de la méthode de descente la plus raide. A chaque étape, on choisit pour que l'itération suivante soit le point minimum de la fonction sur le rayon L.

Cette version de la méthode du gradient est basée sur le choix de l'étape à partir des considérations suivantes. A partir du point on se déplacera dans la direction de l'antigradient jusqu'à atteindre le minimum de la fonction f dans cette direction, c'est à dire sur le rayon :

Autrement dit, il est choisi pour que l'itération suivante soit le point minimum de la fonction f sur le rayon L (voir Fig. 3). Cette version de la méthode du gradient est appelée méthode de descente la plus raide. Notez au passage que dans cette méthode, les directions des marches adjacentes sont orthogonales.

La méthode de descente la plus raide nécessite de résoudre un problème d’optimisation unidimensionnel à chaque étape. La pratique montre que cette méthode nécessite souvent moins d'opérations que la méthode du gradient à pas constant.

Dans la situation générale, cependant, le taux de convergence théorique de la méthode de la descente la plus raide n'est pas supérieur au taux de convergence de la méthode du gradient avec un pas constant (optimal).

Exemples numériques

Méthode de descente de gradient à pas constant

Pour étudier la convergence de la méthode de descente de gradient à pas constant, la fonction a été choisie :

Des résultats obtenus, nous pouvons conclure que si l’écart est trop grand, la méthode diverge ; si l’écart est trop petit, elle converge lentement et la précision est moins bonne. Il faut choisir le pas le plus grand parmi ceux vers lesquels la méthode converge.

Méthode de dégradé avec division par étapes

Pour étudier la convergence de la méthode de descente de gradient avec division par échelons (2), la fonction a été choisie :

La première approximation est le point (10,10).

Critère d'arrêt utilisé :

Les résultats de l'expérience sont présentés dans le tableau :

A partir des résultats obtenus, nous pouvons conclure sur le choix optimal des paramètres : , bien que la méthode soit peu sensible au choix des paramètres.

Méthode de descente la plus raide

Pour étudier la convergence de la méthode de descente la plus raide, la fonction suivante a été choisie :

La première approximation est le point (10,10). Critère d'arrêt utilisé :

Pour résoudre les problèmes d’optimisation unidimensionnels, la méthode du nombre d’or a été utilisée.

La méthode a atteint une précision de 6e-8 en 9 itérations.

De cela, nous pouvons conclure que la méthode de descente la plus raide converge plus rapidement que la méthode de gradient à pas divisé et la méthode de descente à gradient à pas constant.

L’inconvénient de la méthode de descente la plus raide est qu’elle nécessite de résoudre un problème d’optimisation unidimensionnel.

Lors de la programmation des méthodes de descente de gradient, vous devez être prudent lors du choix des paramètres, à savoir

• · Méthode de descente de gradient avec un pas constant : le pas doit être choisi inférieur à 0,01, sinon la méthode diverge (la méthode peut diverger même avec un tel pas, selon la fonction étudiée).
• · La méthode du gradient avec division par échelons est peu sensible au choix des paramètres. Une des options de sélection des paramètres :
• · Méthode de descente la plus raide : la méthode du nombre d'or (le cas échéant) peut être utilisée comme méthode d'optimisation unidimensionnelle.

La méthode du gradient conjugué est une méthode itérative d'optimisation inconditionnelle dans un espace multidimensionnel. Le principal avantage de cette méthode est qu’elle résout un problème d’optimisation quadratique en un nombre fini d’étapes. Par conséquent, la méthode du gradient conjugué pour optimiser la fonctionnelle quadratique est d'abord décrite, des formules itératives sont dérivées et des estimations du taux de convergence sont données. Après cela, nous montrons comment la méthode adjointe est généralisée pour optimiser une fonctionnelle arbitraire, diverses variantes de la méthode sont considérées et la convergence est discutée.

Énoncé du problème d'optimisation

Soit un ensemble donné et une fonction objectif définie sur cet ensemble. Le problème d’optimisation consiste à trouver la borne supérieure ou inférieure exacte de la fonction objectif sur l’ensemble. L'ensemble des points auxquels la limite inférieure de la fonction objectif est atteinte est désigné.

Si, alors le problème d’optimisation est dit sans contrainte. Si, alors le problème d’optimisation est appelé contraint.

Méthode du gradient conjugué pour la fonctionnelle quadratique

Énoncé de la méthode

Considérez le problème d'optimisation suivant :

Voici une matrice symétrique de taille définie positive. Ce problème d'optimisation est appelé quadratique. Noter que. La condition pour un extremum d'une fonction est équivalente au système. La fonction atteint sa limite inférieure en un seul point défini par l'équation. Ainsi, ce problème d'optimisation se réduit à résoudre un système d'équations linéaires. L'idée de la méthode du gradient conjugué est la suivante : Soit la base de. Ensuite, pour n'importe quel point, le vecteur est développé dans la base. Ainsi, il peut être représenté sous la forme.

Chaque approximation ultérieure est calculée à l'aide de la formule :

Définition. Deux vecteurs et sont dits conjugués par rapport à la matrice symétrique B si

Décrivons la méthode de construction d'une base dans la méthode du gradient conjugué. Nous sélectionnons un vecteur arbitraire comme première approximation. A chaque itération les règles suivantes sont sélectionnées :

Les vecteurs de base sont calculés à l'aide des formules :

Les coefficients sont choisis pour que les vecteurs et soient conjugués par rapport à A.

Si l'on note , alors après plusieurs simplifications nous obtenons les formules finales utilisées lors de l'application pratique de la méthode du gradient conjugué :

Pour la méthode du gradient conjugué, le théorème suivant est valable : Théorème Let, où est une matrice de taille définie positive symétrique. Ensuite, la méthode du gradient conjugué converge en seulement quelques étapes et les relations suivantes sont vérifiées :

Convergence de la méthode

Si tous les calculs sont exacts et que les données initiales sont exactes, alors la méthode converge vers la résolution du système en un maximum d'itérations, où est la dimension du système. Une analyse plus fine montre que le nombre d'itérations ne dépasse pas, où est le nombre de valeurs propres différentes de la matrice A. Pour estimer le taux de convergence, l'estimation suivante (assez grossière) est correcte :

Il permet d'estimer le taux de convergence si les estimations des valeurs propres maximales et minimales de la matrice sont connues. En pratique, le critère d'arrêt suivant est le plus souvent utilisé :

Complexité informatique

A chaque itération du procédé, des opérations sont effectuées. Ce nombre d'opérations est nécessaire pour calculer le produit - c'est la procédure la plus longue à chaque itération. D'autres calculs nécessitent des opérations O(n). La complexité de calcul totale de la méthode ne dépasse pas - puisque le nombre d'itérations n'est pas supérieur à n.

Exemple numérique

Appliquons la méthode du gradient conjugué pour résoudre un système où, en utilisant la méthode du gradient conjugué, la solution de ce système est obtenue en deux itérations. Les valeurs propres de la matrice sont 5, 5, -5 - parmi elles il y en a deux différentes, donc, selon l'estimation théorique, le nombre d'itérations ne pourrait pas dépasser deux

La méthode du gradient conjugué est l’une des méthodes les plus efficaces pour résoudre les SLAE avec une matrice définie positive. La méthode garantit la convergence en un nombre fini d’étapes et la précision requise peut être obtenue beaucoup plus tôt. Le principal problème est qu'en raison de l'accumulation d'erreurs, l'orthogonalité des vecteurs de base peut être violée, ce qui altère la convergence.

La méthode du gradient conjugué en général

Considérons maintenant une modification de la méthode du gradient conjugué pour le cas où la fonctionnelle minimisée n'est pas quadratique : Nous allons résoudre le problème :

Fonction différenciable en continu. Pour modifier la méthode du gradient conjugué afin de résoudre ce problème, il faut obtenir pour les formules qui n'incluent pas la matrice A :

peut être calculé à l’aide de l’une des trois formules suivantes :

1. - Méthode Fletcher-Reeves

• 2. - Méthode Polak-Ribière

Si la fonction est quadratique et strictement convexe, alors les trois formules donnent le même résultat. Si est une fonction arbitraire, alors chacune des formules correspond à sa propre modification de la méthode du gradient conjugué. La troisième formule est rarement utilisée car elle nécessite la fonction et le calcul de la Hesse de la fonction à chaque étape de la méthode.

Si la fonction n'est pas quadratique, la méthode du gradient conjugué peut ne pas converger en un nombre fini d'étapes. De plus, un calcul précis à chaque étape n’est possible que dans de rares cas. Par conséquent, l'accumulation d'erreurs conduit au fait que les vecteurs n'indiquent plus le sens de diminution de la fonction. Puis, à un moment donné, ils croient. L'ensemble de tous les nombres auxquels il est accepté sera désigné par. Les nombres sont appelés moments de mise à jour de méthode. En pratique, on choisit souvent où se situe la dimension de l'espace.

Convergence de la méthode

Pour la méthode de Fletcher-Reeves, il existe un théorème de convergence qui impose des conditions pas trop strictes sur la fonction à minimiser : Théorème. Soit les conditions suivantes remplies :

La variété est limitée

La dérivée satisfait la condition de Lipschitz avec une constante dans un certain voisinage

définit M : .

Pour la méthode Polak-Reiber, la convergence est prouvée sous l’hypothèse qu’elle est une fonction strictement convexe. Dans le cas général, il est impossible de prouver la convergence de la méthode Polak-Reiber. Au contraire, le théorème suivant est vrai : Théorème. Supposons que dans la méthode Polak-Reiber les valeurs à chaque étape soient calculées exactement. Ensuite, il y a une fonction, et une première supposition, telle que.

Cependant, en pratique, la méthode Polak-Reiber fonctionne mieux. Les critères d'arrêt les plus courants en pratique : La norme de gradient devient inférieure à un certain seuil La valeur de la fonction est restée quasiment inchangée pendant m itérations consécutives

Complexité informatique

A chaque itération des méthodes Polak-Reiber ou Fletcher-Reeves, la fonction et son gradient sont calculés une fois, et le problème d'optimisation unidimensionnelle est résolu. Ainsi, la complexité d’une étape de la méthode du gradient conjugué est du même ordre de grandeur que la complexité d’une étape de la méthode de la descente la plus raide. En pratique, la méthode du gradient conjugué montre la meilleure vitesse de convergence.

Nous rechercherons le minimum de la fonction en utilisant la méthode du gradient conjugué

Le minimum de cette fonction est 1 et est atteint au point (5, 4). En utilisant cette fonction comme exemple, comparons les méthodes Polak-Reiber et Fletcher-Reeves. Les itérations dans les deux méthodes s'arrêtent lorsque la norme au carré du gradient devient plus petite à l'étape en cours. La méthode du nombre d'or est utilisée pour la sélection

Deux versions de la méthode du gradient conjugué ont été implémentées : pour minimiser une fonctionnelle quadratique et pour minimiser une fonction arbitraire. Dans le premier cas, la méthode est implémentée par la fonction vectorielle RechercherSolution(matrice A, vecteur b) Ici A et b sont la matrice et le vecteur impliqués dans la définition du problème d'optimisation quadratique. Pour minimiser les fonctionnalités arbitraires, vous pouvez utiliser l'une des deux fonctions suivantes : vecteur FletcherRievesMethod(int spaceSize, Fonction F, vecteur (*GradF) (vecteur )) vecteur PolakRibierMethod(int spaceSize, Fonction F, vecteur (*GradF) (vecteur )) Les paramètres des deux fonctions sont les mêmes et ont la signification suivante : spaceSize - la dimension de l'espace (le nombre de variables dont dépend la fonctionnelle minimisée) F - un pointeur vers la fonction à minimiser. La fonction doit être de la forme double<имя функции>(vecteur ) GradF - pointeur vers une fonction qui calcule le gradient de la fonctionnelle minimisée. Les deux méthodes utilisent une fonction auxiliaire pour résoudre un problème d'optimisation unidimensionnel. Le programme implémente une optimisation unidimensionnelle en utilisant la méthode du nombre d'or.

Les méthodes de descente de gradient sont des outils assez puissants pour résoudre les problèmes d’optimisation. Le principal inconvénient de ces méthodes est leur champ d’application limité. La méthode du gradient conjugué utilise uniquement des informations sur la partie linéaire de l'incrément en un point, comme dans les méthodes de descente de gradient. De plus, la méthode du gradient conjugué permet de résoudre des problèmes quadratiques en un nombre fini d'étapes. Sur de nombreux autres problèmes, la méthode du gradient conjugué surpasse également la méthode de la descente de gradient. La convergence de la méthode du gradient dépend de manière significative de la précision avec laquelle le problème d’optimisation unidimensionnelle est résolu. Les boucles de méthode possibles sont résolues à l’aide de mises à jour. Cependant, si une méthode atteint un minimum local d’une fonction, elle ne pourra probablement pas en échapper.

La méthode de descente la plus raide est une méthode de gradient avec un pas variable. A chaque itération, la taille du pas k est sélectionnée à partir de la condition du minimum de la fonction f(x) dans le sens de la descente, c'est-à-dire

Cette condition signifie que le mouvement le long de l'antigradient se produit tant que la valeur de la fonction f (x) diminue. D'un point de vue mathématique, à chaque itération il faut résoudre le problème de minimisation unidimensionnelle par fonction

()=f (x (k) -f (x (k)))

Utilisons pour cela la méthode du nombre d'or.

L'algorithme de la méthode de descente la plus raide est le suivant.

Les coordonnées du point de départ x (0) sont précisées.

Au point x (k) , k = 0, 1, 2, ..., la valeur du gradient f (x (k)) est calculée.

La taille du pas k est déterminée par minimisation unidimensionnelle à l'aide de la fonction

()=f (x (k) -f (x (k))).

Les coordonnées du point x (k) sont déterminées :

x je (k+1) = x je (k) - k f je (x (k)), je=1, …, n.

La condition d'arrêt du processus itératif est vérifiée :

||f (x(k+1))|| .

Si cela est rempli, les calculs s'arrêtent. Sinon, nous passons à l'étape 1. L'interprétation géométrique de la méthode de descente la plus raide est présentée sur la Fig. 1.

Riz. 2.1. Schéma fonctionnel de la méthode de descente la plus raide.

Implémentation de la méthode dans le programme :

Méthode de descente la plus raide.

Riz. 2.2. Mise en œuvre de la méthode de descente la plus raide.

Conclusion : Dans notre cas, la méthode a convergé en 7 itérations. Le point A7 (0,6641 ; -1,3313) est un point extrême. Méthode des directions conjuguées. Pour les fonctions quadratiques, vous pouvez créer une méthode de gradient dans laquelle le temps de convergence sera fini et égal au nombre de variables n.

Appelons une certaine direction et conjuguons-la par rapport à une matrice de Hess définie positive H si :

Alors c'est-à-dire Donc pour l'unité H, la direction conjuguée signifie leur perpendiculaire. Dans le cas général, H n’est pas trivial. Dans le cas général, la conjugaison est l'application de la matrice de Hess à un vecteur - cela signifie faire pivoter ce vecteur d'un certain angle, l'étirer ou le comprimer.

Et maintenant, le vecteur est orthogonal, c'est-à-dire que la conjugaison n'est pas l'orthogonalité du vecteur, mais l'orthogonalité du vecteur tourné.

Riz. 2.3. Schéma fonctionnel de la méthode des directions conjuguées.

Implémentation de la méthode dans le programme : Méthode des directions conjuguées.

Riz. 2.4. Implémentation de la méthode des directions conjuguées.

Riz. 2.5. Graphique de la méthode des directions conjuguées.

Conclusion : Le point A3 (0,6666 ; -1,3333) a été trouvé en 3 itérations et constitue un point extremum.

3. Analyse des méthodes de détermination de la valeur minimale et maximale d'une fonction en présence de restrictions

Rappelons qu'un problème général d'optimisation sous contrainte ressemble à ceci :

f(x) ® min, x О W,

où W est un sous-ensemble propre de R m. Une sous-classe de problèmes avec contraintes de type égalité se distingue par le fait que l'ensemble  est défini par des contraintes de la forme

f i (x) = 0, où f i : R m ®R (i = 1, …, k).

Ainsi,W = (x О R m : f i (x) = 0, i = 1, …, k).

Il nous conviendra d'écrire l'indice "0" pour la fonction f. Ainsi, le problème d’optimisation avec contraintes de type égalité s’écrit

f 0 (x) ® min, (3.1)

f je (x) = 0, je = 1, …, k. (3.2)

Si l'on note maintenant par f une fonction sur R m avec des valeurs dans R k, dont la notation de coordonnées a la forme f(x) = (f 1 (x), ..., f k (x)), alors ( 3.1)–(3.2) on peut aussi l’écrire sous la forme

f 0 (x) ® min, f(x) = Q.

Géométriquement, un problème avec les contraintes de type égalité est un problème de recherche du point le plus bas du graphique d'une fonction f 0 sur la variété  (voir Fig. 3.1).

Les points qui satisfont toutes les contraintes (c'est-à-dire les points de l'ensemble ) sont généralement appelés admissibles. Un point admissible x* est appelé un minimum conditionnel de la fonction f 0 sous les contraintes f i (x) = 0, i = 1, ..., k (ou une solution au problème (3.1)–(3.2)), si pour tous les points admissibles x f 0 (x *)  f 0 (x). (3.3)

Si (3.3) n'est satisfait que pour x admissible situé dans un certain voisinage V x * du point x*, alors on parle de minimum conditionnel local. Les notions de minima locaux et globaux stricts conditionnels sont définies de manière naturelle.

Annotation: Cette conférence couvre largement des méthodes d'optimisation multiparamétriques telles que la méthode de descente la plus raide et la méthode Davidon – Fletcher – Powell. De plus, une analyse comparative des méthodes ci-dessus est réalisée afin de déterminer la plus efficace, leurs avantages et inconvénients sont identifiés ; et considère également des problèmes d'optimisation multidimensionnels, tels que la méthode des ravins et la méthode multiextrémale.

1. Méthode de descente la plus raide

L'essence de cette méthode est qu'en utilisant la méthode mentionnée précédemment méthode de descente de coordonnées une recherche est effectuée à partir d'un point donné dans une direction parallèle à l'un des axes jusqu'au point minimum dans cette direction. La recherche s'effectue alors dans une direction parallèle à l'autre axe, et ainsi de suite. Les directions sont bien entendu fixes. Il semble raisonnable d'essayer de modifier cette méthode pour qu'à chaque étape la recherche du point minimum s'effectue dans la « meilleure » direction. On ne sait pas quelle direction est la « meilleure », mais on sait que direction du dégradé est la direction de l'augmentation la plus rapide de la fonction. Par conséquent, la direction opposée est la direction de la diminution la plus rapide de la fonction. Cette propriété peut être justifiée comme suit.

Supposons que nous nous déplacions du point x au point suivant x + hd, où d est une certaine direction et h est un pas d'une certaine longueur. Par conséquent, le mouvement s'effectue du point (x 1, x 2, ..., x n) au point (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Où

Le changement des valeurs de fonction est déterminé par les relations

Jusqu'au premier ordre zx i , les dérivées partielles étant calculées au point x . Comment choisir les directions d i qui satisfont à l'équation (1.2) afin d'obtenir la plus grande valeur de changement dans la fonction df ? C’est là que se pose un problème de maximisation avec une contrainte. Appliquons la méthode des multiplicateurs de Lagrange, à l'aide de laquelle on détermine la fonction

La valeur df satisfaisant la contrainte (1.2) atteint un maximum lorsque la fonction

Atteint le maximum. Son dérivé

Ainsi,

(1.6)

Alors di ~ df/dx i et la direction d est parallèle à la direction V/(x) au point x.

Ainsi, plus forte augmentation locale la fonction pour un petit pas donné h se produit lorsque d est la direction de Vf(x) ou g(x) . Par conséquent, la direction de la descente la plus raide est la direction

Sous une forme plus simple, l’équation (1.3) peut s’écrire comme suit :

Où est l'angle entre les vecteurs Vf(x) et dx. Pour une valeur donnée de dx, on minimise df en choisissant que la direction de dx coïncide avec la direction de -Vf(x) .

Commentaire. Direction du dégradé perpendiculaire à n’importe quel point d’une ligne de niveau constant, puisque le long de cette ligne la fonction est constante. Ainsi, si (d 1, d 2, ..., d n) est un petit pas le long de la ligne de niveau, alors

Et donc

(1.8)

Lorsque vous utilisez la méthode de descente la plus raide à chaque itération, la taille du pas UN k est sélectionné à partir de la condition minimale de la fonction f(x) dans le sens de la descente, c'est-à-dire

f(x[k] -un k f"(x[k])) = f(x[k] -af"(x[k])) .

Cette condition signifie que le mouvement le long de l'antigradient se produit tant que la valeur de la fonction f(x) diminue. D'un point de vue mathématique, à chaque itération il faut résoudre le problème de minimisation unidimensionnelle selon UN fonctions

j (un) = f(x[k]-af"(x[k])) .

L'algorithme de la méthode de descente la plus raide est le suivant.

• 1. Définissez les coordonnées du point de départ X.
• 2. Au point X[k], k = 0, 1, 2, ... calcule la valeur du gradient f"(x[k]) .
• 3. La taille du pas est déterminée un k, par minimisation unidimensionnelle sur UN fonctions j (un) = f(x[k]-af"(x[k])).
• 4. Les coordonnées du point sont déterminées X[k+ 1]:

X je [k+ 1]=x je [k] -UN k f" je (X[k]), je = 1,..., p.

5. Les conditions d'arrêt du processus de stération sont vérifiées. S'ils sont remplis, les calculs s'arrêtent. Sinon, passez à l'étape 1.

Dans la méthode considérée, la direction du mouvement à partir du point X[k] touche la ligne de niveau au point x[k+ 1] (Fig. 2.9). La trajectoire de descente est en zigzag, avec des liens en zigzag adjacents orthogonaux les uns aux autres. En effet, une étape un k est choisi en minimisant par UN fonctions ? (un) = f(x[k] -af"(x[k])) . Condition nécessaire pour le minimum d'une fonction d j (a)/da = 0. Après avoir calculé la dérivée d'une fonction complexe, on obtient la condition d'orthogonalité des vecteurs de directions de descente en points voisins :

d j (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.

Riz. 2.9.

Les méthodes de gradient convergent vers un minimum à grande vitesse (vitesse de progression géométrique) pour des fonctions convexes lisses. De telles fonctions ont le plus grand M et le moins m valeurs propres de la matrice des dérivées secondes (matrice de Hesse)

diffèrent peu les uns des autres, c'est-à-dire la matrice N(x) bien conditionné. Rappelons que les valeurs propres l i, je =1, …, n, les matrices sont les racines de l'équation caractéristique

Cependant, en pratique, en règle générale, les fonctions minimisées ont des matrices de dérivées secondes mal conditionnées (t/m<< 1). Les valeurs de ces fonctions dans certaines directions changent beaucoup plus rapidement (parfois de plusieurs ordres de grandeur) que dans d'autres directions. Leurs surfaces planes dans le cas le plus simple sont fortement allongées (Fig. 2.10), et dans les cas plus complexes, elles se plient et ressemblent à des ravins. Les fonctions avec de telles propriétés sont appelées ravine. La direction de l'antigradient de ces fonctions (voir Fig. 2.10) s'écarte considérablement de la direction vers le point minimum, ce qui entraîne un ralentissement de la vitesse de convergence.

Riz. 2.10.

Le taux de convergence des méthodes de gradient dépend également de manière significative de la précision des calculs de gradient. La perte de précision, qui se produit généralement à proximité des points minimaux ou dans une situation de ravin, peut généralement perturber la convergence du processus de descente de gradient. Pour les raisons ci-dessus, les méthodes de gradient sont souvent utilisées en combinaison avec d'autres méthodes plus efficaces au stade initial de la résolution d'un problème. Dans ce cas, le point X est loin du point minimum, et des pas en direction de l'antigradient permettent d'obtenir une diminution significative de la fonction.