Méthode de descente la plus raide en technologie chimique. Fonction minimale par méthode de descente la plus raide

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 aussi longtemps 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 les 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 dégradé 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 les 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 à un rythme élevé (taux de progression géométrique) pour les 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.

Objet de la prestation. Calculateur en ligne utilisé pour trouver fonction minimale méthode de descente la plus raide ou Méthode Cauchy(voir exemple). La solution est rédigée au format Word.

Règles de saisie d'une fonction

DANS méthode de descente la plus raide un vecteur dont la direction est opposée à la direction du vecteur gradient de la fonction ▽f(x) est sélectionné comme direction de recherche. De l'analyse mathématique, on sait que le vecteur grad f(x)=▽f(x) caractérise la direction de l'augmentation la plus rapide de la fonction (voir gradient de la fonction). Par conséquent, le vecteur - grad f (X) = -▽f(X) est appelé anti-dégradé et c'est la direction de sa diminution la plus rapide. La relation de récurrence avec laquelle la méthode de descente la plus raide est mise en œuvre a la forme X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
où λ k >0 est la taille du pas. En fonction du choix de la taille du pas, vous pouvez obtenir différentes options pour la méthode du dégradé. Si pendant le processus d'optimisation la taille du pas λ est fixe, alors la méthode est appelée méthode du gradient avec un pas discret. Le processus d'optimisation dans les premières itérations peut être considérablement accéléré si λ k est sélectionné à partir de la condition λ k = min f(X k + λS k) .
Pour déterminer λ k, n'importe quelle méthode d'optimisation unidimensionnelle est utilisée. Dans ce cas, la méthode est appelée méthode de descente la plus raide. En règle générale, dans le cas général, une étape ne suffit pas pour atteindre le minimum de la fonction ; le processus est répété jusqu'à ce que les calculs ultérieurs améliorent le résultat.
Si l'espace est très allongé dans certaines variables, alors un « ravin » se forme. La recherche peut ralentir et zigzaguer au fond du « ravin ». Parfois, une solution ne peut être obtenue dans un délai acceptable.
Un autre inconvénient de la méthode peut être le critère d'arrêt ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Exemple. À partir du point x k =(-2, 3), déterminez le point x k +1 en utilisant la méthode de descente la plus raide pour minimiser la fonction.
Comme direction de recherche, sélectionnez le vecteur dégradé au point actuel

Vérifions le critère d'arrêt. Nous avons
Calculons la valeur de la fonction au point initial f(X 1) = 35. Faisons
avancer dans la direction antigradiente

Calculons la valeur de la fonction à un nouveau point
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Trouvons un pas tel que la fonction objectif atteigne un minimum dans cette direction. De la condition nécessaire à l'existence d'un extremum de la fonction
f'(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
ou f'(X 2) = 2598 λ 1 – 425 = 0.
On obtient le pas λ 1 = 0,164
Terminer cette étape mènera au point

dans lequel la valeur du gradient , valeur de la fonction f(X 2) = 0,23. La précision n'est pas atteinte, à partir du moment où l'on fait un pas dans la direction de l'antigradient.

f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f'(X 2) = 11,76 – 6,12λ 1 = 0
On obtient λ 1 = 0,52

Formulation du problème

Soit la fonction donnée f(x) Rn

Requis f(x) X = Rn

Stratégie de recherche

xk } , k = 0,1,..., tel que , k = 0,1,... . Points de séquence ( xk ) sont calculés selon la règle

où est le point x0 défini par l'utilisateur; taille de pas merci déterminé pour chaque valeur k de l'état

Le problème (3) peut être résolu en utilisant la condition minimale nécessaire suivie de la vérification de la condition minimale suffisante. Ce chemin peut être utilisé soit pour une fonction assez simple à minimiser, soit pour une approximation préliminaire d'une fonction assez complexe polynôme P(tk) (généralement du deuxième ou du troisième degré), puis la condition est remplacée par la condition, et la condition par la condition

Séquençage (xk) se termine au point xk , pour quoi , où ε - un petit nombre positif donné, ou k ≥M , Où M - le nombre limite d'itérations, soit avec deux exécutions simultanées de deux inégalités , Où ε 2 - petit nombre positif. La question est de savoir si un point peut xk être considéré comme l'approximation trouvée du point minimum local souhaité X* , est résolu grâce à des recherches supplémentaires.

Interprétation géométrique de la méthode pour n=2 En figue. 4.

Méthode de descente de coordonnées

Formulation du problème

Soit la fonction donnée f(x) , délimité en dessous sur l'ensemble Rn et ayant des dérivées partielles continues en tous ses points.

f(x) sur l'ensemble des solutions réalisables X = Rn , c'est à dire. trouver un point tel que

Stratégie de recherche

La stratégie pour résoudre le problème consiste à construire une séquence de points ( xk } , k = 0,1,..., tel que , k = 0,1,... . Points de séquence ( xk ) sont calculés sur des cycles conformément à la règle

(4)

Où j - numéro du cycle de calcul ; j = 0,1,2,...; k - numéro d'itération à l'intérieur de la boucle, k = 0,1,... ,n - 1; e k +1 , k = 0,l,...,n - 1 -vecteur unitaire, (k+1) -ème projection dont est égale à 1 ; point x00 défini par l'utilisateur, taille de pas merci est sélectionné à partir de la condition

ou .

Si la condition sélectionnée à l'heure actuelle merci n'est pas remplie, l'étape est divisée par deux et la période est calculé à nouveau. Il est facile de voir que pour un j fixe, en une itération de nombre k une seule projection du point change xjk , ayant un numéro k+1 , et pendant tout le cycle avec numéro j , c'est à dire. commençant par k = 0 et se terminant k = n-1 , toutes les n projections du point changent j0 . Après ce point xjn le numéro est attribué xj + 1,0 , et il est pris comme point de départ pour les calculs dans j+1 faire du vélo. Le calcul se termine au point xjk lorsqu'au moins un des trois critères de fin de comptage est rempli : , ou , ou double exécution des inégalités.

Les points obtenus à la suite de calculs peuvent être écrits comme éléments d'une séquence (xl), Où l=n*j+k - numéro de série du point,

L'interprétation géométrique de la méthode pour n = 2 est présentée sur la Fig. 5.

4. Méthode Frank-Wolfe .

Supposons que nous devions trouver la valeur maximale d'une fonction concave

Sous conditions

Un trait caractéristique de ce problème est que son système de contraintes ne contient que des inégalités linéaires. Cette fonctionnalité constitue la base du remplacement de la fonction objectif non linéaire par une fonction linéaire à proximité du point étudié, grâce à quoi la solution du problème d'origine est réduite à la solution séquentielle de problèmes de programmation linéaire.
Le processus de recherche d'une solution au problème commence par l'identification d'un point appartenant à la région des solutions réalisables au problème.
270
datchas Que ce soit le point X(k) alors à ce stade le gradient de la fonction (57) est calculé

Et construisons une fonction linéaire

Trouvez ensuite la valeur maximale de cette fonction sous les restrictions (58) et (59). Laissez la solution à ce problème être déterminée par le point Z(k) . Ensuite, les coordonnées du point sont considérées comme une nouvelle solution réalisable au problème d'origine. X(k+1) :

Où λk - un certain nombre appelé pas de calcul et compris entre zéro et un (0<λk < 1). Это число λk pris arbitrairement ou déterminé

de sorte que la valeur de la fonction au point X (k +1) f(X (k +1)) , selon λk , était le maximum. Pour ce faire, vous devez trouver une solution à l’équation et choisir sa plus petite racine. Si sa valeur est supérieure à un, alors nous devrions mettre λk=1 . Après avoir déterminé le nombre λk trouver les coordonnées d'un point X(k+1) calculer la valeur de la fonction objectif et déterminer la nécessité de se déplacer vers un nouveau point X(k+2) . S'il y a un tel besoin, calculez au point X(k+1) gradient de la fonction objectif, accédez au problème de programmation linéaire correspondant et trouvez sa solution. Déterminez les coordonnées du point et X(k+2) et étudier la nécessité de calculs supplémentaires. Après un nombre fini d’étapes, une solution au problème initial est obtenue avec la précision requise.

Ainsi, le processus de recherche d'une solution au problème (57) - (59) à l'aide de la méthode Frank-Wolfe comprend les étapes suivantes:

1. Déterminez la solution réalisable initiale au problème.
2. Trouvez le gradient de la fonction (57) au point d'une solution admissible.
3. Construisez la fonction (60) et trouvez sa valeur maximale dans les conditions (58) et (59).
4. Déterminez l'étape de calcul.
5. À l'aide des formules (61), les composantes d'une nouvelle solution réalisable sont trouvées.
6. Vérifiez la nécessité de passer à la prochaine solution réalisable. Si nécessaire, passez à l'étape 2, sinon une solution acceptable au problème initial est trouvée.

Méthode de fonctions de pénalité.

Considérons le problème de la détermination de la valeur maximale de la fonction concave

f (x 1, x 2, .... xn) sous conditions g je (x 1, x 2, .... x n) ≤ b je (je = l, m) , xj ≥ 0 (j=1, n) , Où g je (x 1, x 2, .... x n) - les fonctions convexes.

Au lieu de résoudre ce problème directement, trouvez la valeur maximale de la fonction F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) qui est la somme de la fonction objectif du problème et d'une fonction

H(x 1, x 2, ...., x n), défini par un système de restrictions et appelé fonction de pénalité. La fonction de pénalité peut être construite de différentes manières. Cependant, le plus souvent, cela ressemble à

UN un je > 0 - quelques nombres constants représentant des coefficients de pondération.
À l’aide de la fonction de pénalité, ils se déplacent séquentiellement d’un point à un autre jusqu’à obtenir une solution acceptable. Dans ce cas, les coordonnées du point suivant sont trouvées à l'aide de la formule

De la dernière relation, il s'ensuit que si le point précédent se situe dans la région des solutions réalisables au problème d'origine, alors le deuxième terme entre crochets est égal à zéro et la transition vers le point suivant n'est déterminée que par la pente de l'objectif. fonction. Si le point spécifié n'appartient pas à la région des solutions admissibles, alors grâce à ce terme dans les itérations suivantes, un retour à la région des solutions admissibles est obtenu
les décisions. En même temps, moins un je , plus une solution acceptable est trouvée rapidement, mais la précision de sa détermination diminue. Par conséquent, le processus itératif démarre généralement à des valeurs relativement faibles. un je et, en continuant, ces valeurs augmentent progressivement.

Ainsi, le processus de recherche d'une solution à un problème de programmation convexe à l'aide de la méthode de la fonction de pénalité comprend les étapes suivantes :

1. Déterminez la solution réalisable initiale.
2. Sélectionnez l'étape de calcul.
3. Trouver, pour toutes les variables, les dérivées partielles de la fonction objectif et des fonctions qui déterminent l'éventail de solutions réalisables au problème.

4. À l'aide de la formule (72), les coordonnées du point qui détermine une nouvelle solution possible au problème sont trouvées.
5. Vérifiez si les coordonnées du point trouvé satisfont au système de contraintes du problème. Si ce n’est pas le cas, passez à l’étape suivante. Si les coordonnées du point trouvé déterminent une solution admissible au problème, alors la nécessité de passer à la solution admissible suivante est étudiée. Si nécessaire, passez à l'étape 2, sinon une solution acceptable au problème initial a été trouvée.
6. Définissez les valeurs des coefficients de pondération et passez à l'étape 4.

Méthode Arrow-Hurwitz.

Lors de la recherche de solutions aux problèmes de programmation non linéaire à l'aide de la méthode de la fonction de pénalité, nous avons choisi les valeurs un je , arbitrairement, ce qui a conduit à des fluctuations importantes de la distance entre les points déterminés et la région des solutions réalisables. Cet inconvénient est éliminé lors de la résolution du problème par la méthode Arrow-Hurwitz, selon laquelle à l'étape suivante les nombres un je (k) calculé par la formule

Comme valeurs initiales un je (0) prenez des nombres arbitraires non négatifs.

EXEMPLE DE SOLUTION

Exemple 1.

Trouver le minimum local d'une fonction

Définir un point xk

1. Posons .

2. Mettons k = 0 .

trente . Calculons

4 0 . Calculons . Passons à l'étape 5.

50 . Vérifions l'état . Passons à l'étape 6.

6 0 . Mettons t0 = 0,5 .

7 0 . Calculons

8 0 . Comparons . Nous avons . Conclusion : condition pour k = 0 n'est pas exécuté. Mettons t0 = 0,25 , passez à la répétition des étapes 7 et 8.

7 01. Calculons.

8 01. Comparons f (x 1) et f (x 0) . Conclusion: f (x 1)< f (x 0) . Passons à l'étape 9.

9 0 . Calculons

Conclusion : nous croyons k =1 et passez à l'étape 3.

3 1. Calculons

4 1. Calculons . Passons à l'étape 5.

5 1. Vérifions l'état k ≥ M : k = 1< 10 = M . Passons à l'étape 6.

6 1. Mettons t 1 = 0,25.

7 1. Calculons

8 1. Comparons f (x 2) avec f (x 1) . Conclusion: f (x 2)< f (х 1). Passons à l'étape 9.

9 1. Calculons

Conclusion : nous croyons k = 2 et passez à l'étape 3.

3 2. Calculons

4 2 . Calculons. Passons à l'étape 5.

5 2. Vérifions l'état k ≥M : k = 2< 10 = М , passez à l'étape 6.

6 2. Mettons t 2 =0,25 .

7 2. Calculons

8 2. Comparons f (x 3) Et f (x 2) . Conclusion: f (x 3)< f (х 2) .Passez à l'étape 9.

9 2. Calculons

Conclusion : nous croyons k = 3 et passez à l'étape 3.

3 3 . Calculons

4 3 . Calculons. Passons à l'étape 5.

5 3. Vérifions l'état k ≥M : k = 3<10 = М , passez à l'étape 6.

6 3. Mettons t 3 = 0,25.

7 3. Calculons

8 3. Comparons f (x 4) Et f (x 3) : f (x 4)< f (х 3) .

9 3. Calculons

Les conditions sont remplies lorsque k = 2,3 . Calcul

fini. Point trouvé

En figue. Les 3 points résultants sont reliés par une ligne pointillée.

II. Analyse des points x4 .

Fonction est deux fois différentiable, nous vérifierons donc les conditions suffisantes pour le minimum au point x4 . Pour ce faire, analysons la matrice hessienne.

La matrice est constante et définie positive (c'est-à-dire . H > 0 ) puisque ses deux mineurs angulaires sont positifs. Par conséquent, le point est l'approximation trouvée du point minimum local, et la valeur est l'approximation trouvée de la valeur f(x*) =0 . Notez que la condition H > 0 , il existe en même temps une condition de stricte convexité de la fonction . Par conséquent, on trouve des approximations du point minimum global f(x) et sa valeur minimale à R2 . ■

Exemple 2

Trouver le minimum local d'une fonction

I. Définition d'un point xk, dans lequel au moins un des critères pour effectuer les calculs est rempli.

1. Posons .

Trouvons le gradient de la fonction en un point arbitraire

2. Mettons k = 0 .

trente . Calculons

4 0 . Calculons . Passons à l'étape 5.

50 . Vérifions l'état . Passons à l'étape 6.

6° Le point suivant est trouvé par la formule

Remplaçons les expressions résultantes pour les coordonnées dans

Trouvons le minimum de la fonction f(t 0) Par t 0 en utilisant les conditions nécessaires pour un extremum inconditionnel :

D'ici t 0 =0,24 . Parce que , la valeur de pas trouvée fournit le minimum de la fonction f(t 0) Par t 0 .

Définissons

7 0 . Nous trouverons

8°. Calculons

Conclusion : nous croyons k = 1 et passez à l'étape 3.

3 1. Calculons

4 1. Calculons

5 1. Vérifions l'état k ≥ 1 : k = 1< 10 = М.

6 1. Définissons

7 1. Nous trouverons :

8 1. Calculons

Nous croyons k = 2 et passez à l'étape 3.

3 2. Calculons

4 2 . Calculons

5 2. Vérifions l'état k ≥ M : k = 2< 10 = M .

6 2. Définissons

7 2. Nous trouverons

8 2. Calculons

Nous croyons k =3 et passez à l'étape 3.

3 3 . Calculons

4 3 . Calculons.

Le calcul est terminé. Point trouvé

II. Analyse des points x3 .

Dans l'exemple 1.1 (Chapitre 2 §1) il a été montré que la fonction f(x) est strictement convexe et, par conséquent, aux points 3 est l'approximation trouvée du point minimum global X* .

Exemple 3.

Trouver le minimum local d'une fonction

I. Définition d'un point xjk , dans lequel au moins un des critères pour effectuer les calculs est rempli.

1. Posons

Trouvons le gradient de la fonction en un point arbitraire

2. Posons j = 0.

trente . Vérifions si la condition est remplie

4 0 . Mettons k = 0.

50 . Vérifions si la condition est remplie

6 0 . Calculons

7 0 . Vérifions l'état

8 0 . Mettons

9 0 . Calculons , Où

100 . Vérifions l'état

Conclusion : on suppose et on passe à l'étape 9.

9 01. Calculons x01 par étapes

10 01. Vérifions l'état

11 0 . Vérifions les conditions

Nous croyons k =1 et passez à l'étape 5.

5 1. Vérifions l'état

6 1. Calculons

7 1. Vérifions l'état

8 1. Mettons

9 1. Calculons

10 1. Vérifions l'état :

11 1. Vérifions les conditions

Nous croyons k = 2 , passez à l'étape 5.

5 2. Vérifions l'état. C'est parti, passez à l'étape 3.

3 1. Vérifions l'état

4 1. Mettons k = 0.

5 2. Vérifions l'état

6 2. Calculons

7 2. Vérifions l'état

8 2. Mettons

9 2. Calculons

10 2. Vérifions l'état

11 2. Vérifions les conditions

Nous croyons k =1 et passez à l'étape 5.

5 3. Vérifions l'état

6 3. Calculons

7 3. Vérifions les conditions

8 3. Mettons

9 3. Calculons

10 3. Vérifions l'état

11 3. Vérifions les conditions

Mettons k = 2 et passez à l'étape 5.

5 4 . Vérifions l'état

Nous croyons j = 2, x 20 = x 12 et passez à l'étape 3.

3 2. Vérifions l'état

4 2 . Mettons k =0 .

5 4 . Vérifions l'état

6 4. Calculons

7 4. Vérifions l'état

8 4 . Mettons

9 4. Calculons

10 4. Vérifions la condition et passons à l'étape 11.

11 4. Vérifions les conditions

Les conditions sont remplies en deux cycles consécutifs avec des chiffres j=2 Et j -1= 1 . Le calcul est terminé, le point a été trouvé

En figue. Les 6 points résultants sont reliés par une ligne pointillée.

Dans la méthode de descente de coordonnées, nous descendons le long d'une ligne brisée constituée de segments droits parallèles aux axes de coordonnées.

II. Analyse du point x21.

Dans l'exemple 1.1, il a été montré que la fonction f(x) est strictement convexe, a un minimum unique et donc un point est l'approximation trouvée du point minimum global.

Dans toutes les méthodes de gradient évoquées ci-dessus, la séquence de points (xk) converge vers le point stationnaire de la fonction f(x) avec des propositions assez générales concernant les propriétés de cette fonction. En particulier, le théorème est vrai :

Théorème. Si la fonction f(x) est bornée en dessous, son gradient satisfait la condition de Lipschitz () et le choix de valeur tn produit par l'une des méthodes décrites ci-dessus, alors quel que soit le point de départ x0 :

à .

Dans la mise en œuvre pratique du programme

k =1, 2, … n.

les itérations s'arrêtent si pour tout je, je = 1, 2, ..., n , des conditions comme

où est un nombre donné caractérisant l'exactitude de la recherche du minimum.

Dans les conditions du théorème, la méthode du gradient assure la convergence dans la fonction ou vers la borne inférieure exacte (si la fonction f(x) n'a pas de minimum ; riz. 7), ou à la valeur de la fonction en un point stationnaire, qui est la limite de la séquence (xk). Il n'est pas difficile de trouver des exemples lorsqu'une selle est réalisée à ce stade, et pas un minimum. En pratique, les méthodes de descente de gradient contournent en toute confiance les points selle et trouvent les minima de la fonction objectif (dans le cas général, locaux).

CONCLUSION

Des exemples de méthodes d’optimisation de gradient sans contrainte ont été discutés ci-dessus. À la suite des travaux effectués, les conclusions suivantes peuvent être tirées :

1. Les problèmes plus ou moins complexes de recherche d'un extremum en présence de restrictions nécessitent des approches et des méthodes particulières.

2. De nombreux algorithmes pour résoudre des problèmes contraints incluent la minimisation sans contrainte comme étape.

3. Les différentes méthodes de descente diffèrent les unes des autres par la manière dont elles sélectionnent la direction de descente et la longueur de la marche dans cette direction.

4. Il n'existe pas encore de théorie qui prendrait en compte les caractéristiques des fonctions qui décrivent la formulation du problème. La préférence doit être donnée aux méthodes plus faciles à gérer dans le processus de résolution d'un problème.

Les vrais problèmes d’optimisation appliquée sont très complexes. Les méthodes d'optimisation modernes ne permettent pas toujours de résoudre des problèmes réels sans aide humaine.

BIBLIOGRAPHIE

1. Kosoroukov O.A. Recherche opérationnelle : un manuel. 2003

2. Pantleev A.V. Méthodes d'optimisation en exemples et problèmes : manuel. Avantage. 2005

3. Chichkine E.V. Recherche opérationnelle : manuel. 2006

4. Akulich I.L. Programmation mathématique en exemples et problèmes. 1986

5. Ventzel E.S. Recherche opérationnelle. 1980

6. Ventzel E.S., Ovcharov L.A. Théorie des probabilités et ses applications techniques. 1988

©2015-2019site
Tous les droits appartiennent à leurs auteurs. Ce site ne revendique pas la paternité, mais propose une utilisation gratuite.
Date de création de la page : 2017-07-02

Le gradient de la fonction différentiable f(x) au point X appelé n vecteur dimensionnel f(x) , dont les composantes sont des dérivées partielles de la fonction f(x), calculé au point X, c'est à dire.

f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T .

Ce vecteur est perpendiculaire au plan passant par le point X, et tangent à la surface plane de la fonction f(x), passant par un point X.En chaque point d’une telle surface la fonction f(x) prend la même valeur. En assimilant la fonction à différentes valeurs constantes C 0 , C 1 , ..., on obtient une série de surfaces caractérisant sa topologie (Fig. 2.8).

Riz. 2.8. Pente

Le vecteur gradient est dirigé dans la direction de l'augmentation la plus rapide de la fonction en un point donné. Vecteur opposé au dégradé (-f'(x)) , appelé anti-dégradé et est orienté vers la diminution la plus rapide de la fonction. Au point minimum, le gradient de la fonction est nul. Les méthodes du premier ordre, également appelées méthodes de gradient et de minimisation, sont basées sur les propriétés des gradients. L'utilisation de ces méthodes dans le cas général permet de déterminer le point minimum local d'une fonction.

Évidemment, s'il n'y a pas d'informations supplémentaires, alors dès le point de départ X il est sage d'aller à l'essentiel X, se trouvant dans la direction de l'antigradient - la diminution la plus rapide de la fonction. Choisir comme direction de descente R.[k] anti-dégradé - f'(x[k] ) à ce point X[k], on obtient un processus itératif de la forme

X[ k+ 1] = X[k]-a k f"(x[k] ) , et k > 0; k=0, 1, 2, ...

Sous forme de coordonnées, ce processus s'écrit comme suit :

x je [ k+1]=x je[k] - un kf(x[k] ) /x je

je = 1, ..., n; k= 0, 1, 2,...

Comme critère d'arrêt du processus itératif, soit la réalisation de la condition de petit incrément de l'argument || X[k+l] -X[k] || <= e , либо выполнение условия малости градиента

|| f'(x[k+l] ) || <= g ,

Ici, e et g reçoivent de petites quantités.

Un critère combiné est également possible, consistant en la réalisation simultanée des conditions spécifiées. Les méthodes de dégradé diffèrent les unes des autres dans la manière dont elles choisissent la taille du pas et k.

Dans la méthode à pas constant, une certaine valeur de pas constant est sélectionnée pour toutes les itérations. Un tout petit pas et k garantira que la fonction diminue, c'est-à-dire que l'inégalité

f(x[ k+1]) = f(x[k] – a k f'(x[k] )) < f(x[k] ) .

Cependant, cela peut conduire à devoir effectuer un nombre inacceptable d’itérations pour atteindre le point minimum. En revanche, un pas trop grand peut provoquer une augmentation inattendue de la fonction ou conduire à des oscillations autour du point minimum (cyclage). En raison de la difficulté d'obtenir les informations nécessaires pour sélectionner la taille du pas, les méthodes à pas constants sont rarement utilisées dans la pratique.

Ceux à gradient sont plus économiques en termes de nombre d'itérations et de fiabilité méthodes à pas variables, lorsque, en fonction des résultats des calculs, la taille du pas change d'une manière ou d'une autre. Considérons les variantes de telles méthodes utilisées dans la pratique.

Lorsque vous utilisez la méthode de descente la plus raide à chaque itération, la taille du pas et 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]–ak f’(x[k])) = f(x[k] – unf"(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 dégradé 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]= xi[k]– a k f'i (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.

DJ (a)/da = -f’(x[k+ 1]f'(x[k]) = 0.

Riz. 2.9. Interprétation géométrique de la méthode de descente la plus raide

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 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

Riz. 2.10. Fonction ravin

Les méthodes de gradient discutées ci-dessus ne trouvent le point minimum d'une fonction dans le cas général que dans un nombre infini d'itérations. La méthode du gradient conjugué génère des directions de recherche plus cohérentes avec la géométrie de la fonction minimisée. Cela augmente considérablement la vitesse de leur convergence et permet, par exemple, de minimiser la fonction quadratique

f(x) = (x, Hx) + (b, x) + une

avec une matrice définie positive symétrique N en un nombre fini d'étapes P,égal au nombre de variables de fonction. Toute fonction lisse située à proximité du point minimum peut être bien approchée par une fonction quadratique, c'est pourquoi les méthodes de gradient conjugué sont utilisées avec succès pour minimiser les fonctions non quadratiques. Dans ce cas, ils cessent d’être finis et deviennent itératifs.

Par définition, deux n vecteur dimensionnel X Et à appelé conjugué par rapport à la matrice H(ou H-conjugué), si le produit scalaire (X, Eh bien) = 0. Ici N- matrice de taille définie positive symétrique P. X P.

L’un des problèmes les plus importants des méthodes de gradient conjugué est celui de la construction efficace de directions. La méthode Fletcher-Reeves résout ce problème en transformant l'antigradient à chaque étape -f(x[k]) dans la direction p[k], H-conjuguer avec les directions trouvées précédemment R., R., ..., R.[k-1]. Considérons d'abord cette méthode en relation avec le problème de la minimisation d'une fonction quadratique.

Directions R.[k] est calculé à l'aide des formules :

p[ k] = -f'(x[k]) +bk-1 p[k-l], k>= 1;

p = - F’(X) .

valeurs b k-1 sont choisis pour que les directions p[k], R.[k-1] étaient H-conjuguer :

(p[k], HP[k- 1])= 0.

En conséquence, pour la fonction quadratique

le processus itératif de minimisation a la forme

X[ k+l] =x[k]+ak k p[k],

Où R.[k] - direction de descente vers k- m pas; et k- taille de pas. Cette dernière est choisie parmi la condition minimale de la fonction Par UN f(x)

f(x[ k] + dans la direction du mouvement, c'est-à-dire suite à la résolution du problème de minimisation unidimensionnelle :[k]) = f(x[k] + un k r [k]) .

Pour une fonction quadratique

L'algorithme de la méthode du gradient conjugué de Fletcher-Reeves est le suivant. X 1. Au point p = -f'(x) .

calculé k- 2. Activé UN m pas, en utilisant les formules ci-dessus, le pas est déterminé . k X[k+ 1].

et période f(x[k+1]) 3. Les valeurs sont calculées f'(x[k+1]) .

Et f'(x) 4. Si X[k= 0, alors pointez +1] est le point minimum de la fonction f(x). p[k Sinon, une nouvelle direction est déterminée

+l] de la relation P. et le passage à l'itération suivante est effectué. Cette procédure trouvera le minimum d'une fonction quadratique en pas plus de pas. Lors de la minimisation de fonctions non quadratiques, la méthode Fletcher-Reeves devient itérative à partir de finie. Dans ce cas, après X(p+ X[P. 1) la ème itération de la procédure 1 à 4 est répétée cycliquement avec remplacement

X[ k+l] =x[k]+ak k p[k],

p[ k] sur[k])+ +1] , et les calculs se terminent à , où est un nombre donné. Dans ce cas, la modification suivante de la méthode est utilisée : k- 1 p[k-l], k>= 1;

= -f'(x X);

f(x[ k] + b[k]) = f(x[k] p = -f'([k];

un kp +ap Ici +ap je - de nombreux index := (0, n, 2 P. p, salaire, ...)

, c'est-à-dire que la méthode est mise à jour tous les X pas. R. = La signification géométrique de la méthode du gradient conjugué est la suivante (Fig. 2.11). A partir d'un point de départ donné la descente s'effectue dans le sens X-f"(x f"(x). À ce point X est le point minimum de la fonction dans la direction R., Que f'(x) orthogonal au vecteur R.. On trouve alors le vecteur R. , H-conjugué à R.. Ensuite, on trouve le minimum de la fonction dans la direction R. etc.

Riz. 2.11 . Trajectoire de descente dans la méthode du gradient conjugué

Les méthodes de direction conjuguée sont parmi les plus efficaces pour résoudre les problèmes de minimisation. Il convient toutefois de noter qu’ils sont sensibles aux erreurs qui surviennent lors du processus de comptage. Avec un grand nombre de variables, l'erreur peut tellement augmenter que le processus devra être répété même pour une fonction quadratique, c'est-à-dire le processus correspondant ne rentre pas toujours dans P. p, salaire, ...)

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, 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.

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.