Алгоритм градиентного метода спуска

varnie



Еще раз, внимательно все проверь.



1. Берем начальную точку. (Q.x, Q.y)

2. Считаем в ней градиент. (G.x, G.y)

3. Выполняем поиск минимума из Q по направлению G.

4. Полученную точку минимума принимаем за новое значение Q.

5. Проверяем критерий окончания поиска. Если не выполняется - переходим в п.2.



Поиск минимума по направлению.



f(t) = Ф(Q + t * G);



Ищем минимум функции f. Пусть это некоторая точка t_min.



1. Локазизуем минимум. Необходимо найти такие t1 и t2, чтобы выполнялось все вот это:

1.1. t1 <= t_min <= t2

1.2. df/dt(t1) <= 0

1.3. df/dt(t2) >= 0

2. Ищем минимум. Критерием минимума можно взять:

t = t_min <=> abs(df/dt(t)) < eps



Как искать минимум f(t)? Например половинным делением.

 

_DEN_, половинным делением не получиься искать, т.к. этот метод катит только для ф-ций одной переменной. мне препод так сказал.

 

varnie



Препод тебе все правильно сказал. Мы и ищим минимум функции одной переменной. Он же минимум по направлению.



f(t) = Ф(Q + t * G)



Q - константа, G - константа. t - единственная переменная.

 

в общем, вот мое положение на данный момент:



смысл этого алгоритма в том, что мы ищем такую стационарную точку, в которой бы градиент функции равнялся нулю.



1. Берем начальную точку. (Q.x, Q.y), шаг 0<step<=1, эпсилон EPS>0

2. Считаем в ней градиент, и берем его со знаком минус - это будет новый вектор направления:

P = -grad[ ф(Q) ],

т.е. P.x = -1*Df/Dx(Q.x, Q.y)

P.y = -1*Df/Dx(Q.x, Q.y)

3. подбираем шаг, чтобы удовлетворял неравенству

Ф[ Q-grad( Ф(Q) ) ] - Ф(Q) <= EPS*step* [ || grad( Ф(Q) ) || ]^2

,где [ || grad( Ф(Q) ) || ]^2 - это квадрат меры от градиента функции в точке приближения

,а пока шаг не удовлетворяет неравенству делаем step /= 2



4. Определяем следующее приближение значения функции Q:

tempQ = Q - step*grad( Ф(Q) );

5. Полученную точку минимума принимаем за новое значение Q.

Q = tempQ

6. result = Ф[ grad( Ф(Q) ) ] = Ф[Q]

т.е. мы находим точку, в которой grad( Ф(Q) ) = 0;

7. Проверяем критерий окончания поиска. Если не выполняется - переходим в п.2.

т.е. если || G(Q) || >= EPS, то идет на п.2



только у меня почему-то в п.3 неравенство всегда получается верное, и поэтому никакого деления шага никогда (!) не происходит.

сейчас алгоритм у меня работает и выдает верные результаты (максимально приближенные к настоящему решению, проверенному в матем. пакете) только в тех случаях, когда "удачно" задано начальное (Q.x,Q.y). Если же (Q.x,Q.y), скажем так - "левые", То цикл очень долго крутится и вылетает с "floating point overflow".

действительно, при работе алгоритма вектор градиента получается почти что равный точке 0, например, (0.26, 0.01), (0.27, 0.01), (-0.26, 0.01). Эти примеры подтверждают, что алгоритм уже правильно работает, что радует. Вот только как быть с вышеописанной проблемкой с бесконечным циклом и всегда верным неравенством?



_DEN_, препод еще сказал, что метод половинного деления ака дихотомии не подойдет к ф-ции 2х переменных, т.к. в этом случае могут быть всякие разрывы и прочие неприятности.

я не пойму, у нас же исходная ф-ция Ф=Ф(x,y), т.е. ф-ция 2х переменных. а ты говоришь, что получается что ф-ция как бы от одной переменной.

какие-то недопонимания и/или неточности.

в общем, как бы там ни было, мне медот половинного деления не пойдет, т.к. в этой лабе преподу нужно сделать тем алгоритмом, который я здесь привел.

 

varnie



Сейчас пятница, вечер, и я уже нифига не соображаю. Мозгов хватит только прокоментировать твое нипонимание. Остальное завтра:

Вот, пример, надеюсь поймешь.

Код (Text):

1. float Func2 (float x, float y) // 2 переменные
2. {
3.   return x*x + y*y*y + 4;
4. }
5.  
6. float Func1 (float t) // 1 переменная
7. {
8.   return Func2 (3 + 2*t, 8 - 6*t);
9. }

Теперь ясно надеюсь?..

 

Привет! Никто не подскажет, алгоритм нахождения последовательности шага в наискорейшем градиентном спуске?

 

Привет всем , кто меня слышит.

poipo, я сейчас работаю над курсовой по такой же теме. В градиентном мтоде наискорейшего спуска я разобрался. Мне сейчас нужно в универ идти, так что алгоритм распишу подробнейшим образом , но ближе к вечеру.
+ poipo , на чем тебе нужно написать программу??


Но у меня возникли трудности с реализацией этого метода в Visual Basic _ е. До этого момента я с ним никогда не работал. Поэтому у меня в ходе обдумывания моей програаммы возникает много вопросов. Буду очень благодарен, если мне кто-нибудь поможет !

1. Каким образом лучше организовать ввод искомой функции

2. как подстроить программу не для определенного числа переменных, а для произвольного

3. возможно ли будет после всех вычеслений построить график функции

 

Приве pol1234!
Я тоже разобрался с градиентными методами!
Программу есть на С++, на Visual я не работаю, но смогу поинтерисоваться насчёт твоих вопросов.
Ты можешь поделиться информацией которая у тебя по методу наискореёшего градиентного спуска?
Если да то отписывай на gsh-18@rambler.ru