Créer une fonction pour implémenter l'algorithme de descente la plus raide

Question

J'essaie d'implémenter l'algorithme de descente le plus raide pour la minimisation de la fonction 2D. Laissez-moi vous expliquer avec un exemple. J'ai la fonction f1(x1,x2) = 2*x1^2 + x2^2 - 5*x1*x2 et en commençant par le point de départ p0 = [1,0].

Etape 1: estimation Point initial p0 = [1,0], paramètre de convergence e=0.1

Etape 2: Calcul de gradient c1 de f1 à p0. c1=[4,-5] J'utilise la méthode de différence centrale pour cela.

Étape 3: Si norme de c1>e, passez à l'étape 4, sinon, arrêtez.

Étape 4: Notre direction de recherche est d1 = - c1. Donc, d1 = [-4,5].

Étape 5: Trouver pas de progression a pour minimiser f1(a) = f1(p0 + a*d1) = f1(1-4a,5a)

Étape 6: Mise à jour p0 à p1 comme p1 = p0 + a * d1 et à l'étape 2.

Je suis en train de mettre en œuvre cet exemple dans Matlab et ne sais pas comment mettre en œuvre l'étape 5. Je sais que l'algorithme de recherche ant 1D, comme la méthode de bissection peut fonctionner. Mais, le problème est de «convertir» f1(1-4a,5a) en une fonction, c'est-à-substituer (1-4a,5a) en f1. Je rencontre ici la constante symbolique a, que je ne sais pas comment traiter. Si j'écris une fonction de minimisation, je peux lui transmettre des valeurs, mais je ne suis pas sûr de la variable symbolique a. Je ne veux pas utiliser les fonctions spéciales de matlab, telles que les symboles, et essayer de garder le code au niveau général, donc je peux le convertir dans d'autres langages de programmation sans aucun problème. Vos suggestions sont les bienvenues.

Answer 1

Vous souhaitez probablement utiliser fminbnd pour placer des limites sur la recherche de ligne (-1 à 1 ci-dessous), car la recherche de toute la ligne est une tâche mal définie. Il n'y a pas besoin d'une variable symbolique. la taille de l'étape est déterminée en minimisant une fonction anonyme ci-dessous:

a = fminbnd(@(a) f1(p(1) + a*d(1), p(2) + a*d(2)), -1, 1); 

ici p est le point courant et d est la direction de la recherche. (Je ne voudrais pas les appeler p1 et d1 comme dans votre description, comme s'ils étaient utilisés pour la première étape seulement.)

L'exemple permet le négatif a, que je trouve utile en pratique; il est parfois préférable d'aller dans la direction opposée à celle suggérée par le dégradé. Pour interdire cela, changez les limites à 0, 1 (ou 0, 10 pour une recherche plus agressive dans la direction avant).