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

привет.

требуется реализовать сабж для отыскания min/max заданной функции. хотелось бы почитать наиболее понятные статьи на эту тему и посмотреть (не сочтите за наглость) сорцы на каком-нить ЯВУ.

заранее пасиба,

/varnie

 

Блин, че там реализовывать, все банально:



find_min:



x_n+1 = find_min_linear(x_n, grad(F(x_n)))

while(norm(grad(F(x_n))) > eps)



find_min_linear:

1. Локализация минимума.

2. Поиск минимума по одному параметру. Самое простое: дихотомия или золотое сечение. После почву можно сдобрить кубической интерполяцией.

 

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

 

varnie



Подробнее не успеваю, т.к. убегаю с работы домой Из дома вылезу, постараюсь подробнее написать. Жди через 3 - 4 часа

 

Итак, у нас есть скалярная N-мерная функция F (N взять по вкусу )



Задача состоит из двух функций.



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



linear_min(F, a0, a)



Тоесть берем точку a0 и вектор a. На полученой прямой ищем минимум функции F. google: Дихотомия или золотое чесение.



2. Итеративный спуск по градиенту.



Берем точку a0. Считаем градиент функции F в этой точке. Градиент это вектор из частных производных.

Т.е. grad(F) = [dF / dx1, df / dx2, ..., dF / dxn]



Итак, у нас есть a0, за a принимаем градиент в точке a0 и решаем задачу № 1. Получаем новую точку. Безем ее за a0 и решаем задачу № 2 заново с новыми условиями. И так до тех пор пока не найдем минимум с заданой точностью. Обычно критерий окончания поиска - длина градиента в точке a0 меньше eps.

 

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

вопрос - как реализовать подсчет частных производных?

 

как реализовать? согласно определению

dF/dx = lim_{\delta x->0} \delta F/ \delta x.

если нет возможности записать в явном виде частную производную -- то появляются проблемы, но google: численное+дифференцирование эти проблемы поможет решить.

 

varnie

Ты немного не понимаешь. Алгоритм градиентного спуска это многомерный метод. В его реализации надо юзать один из одномерных методов, например дихотомию. Можно и другой, но пойми, что сабж и дихотомия это не аналоги, а дополнения.

Т.е. Суть сабжа в том, что мы спускаемся по градиенту. А дихотомия это лишь способ по нему спускаться. Понимаешь?



Градиент для 3D:

Код (Text):

1. gx = ( F(x + eps, y, z) - F(x, y, z) ) / eps
2. gy = ( F(x, y + eps, z) - F(x, y, z) ) / eps
3. gz = ( F(x, y, z + eps) - F(x, y, z) ) / eps

 

если ещё нужно:

http://alglib.sources.ru/



самое главное - не слушать, про:

dF/dx = lim_{\delta x->0} \delta F/ \delta x. -

это провокация)

 

извиняюсь, провокация это:

 

antifatum

Ты че гонишь? Где тут провокация?

 

срочно!! помогите понять, как можно посчитать grad Ф(Q), где Q - приближенное значение функции Ф=Ф(x,y); у меня что-то ум за разум заходит, когда я пытаюсь представить, как это можно вычислить градиент ака вектор в конкретной точке.

или я путаю с самим понятием что-то?

 

вообще то я математику пересдавал постоянно

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

 

varnie



Градиент функции по ее единственному приближенному значению посчитать нельзя. Повторяю 10-й раз, градиент считается:



Gradient.X = (Ф(x + eps, y) - Ф(x, y)) / eps;

Gradient.Y = (Ф(x, y + eps) - Ф(x, y)) / eps;



На математике надо препода слушать, а не баб разглядывать.

 

_DEN_, я это понимаю все..



короче, вот алгоритм мой...

вот теория, кот-ю я пытаюсь счас реализовать на ЯП:

пусть E - некоторая постоянная (малое число) и Q_нулевое - начальное приближение. Положим i=0 и перейдем к основному этапу.

есть алгроитм:

1. если || grad A( Q_i-того ) || < E, то прерываемся; иначе же за направление движения выбираем вектор P_i-тое = - grad Ф( Q_i-тое ) и решается задача линейного поиска точки минимума функции, равного Ф( Q_i-тое - p*grad Ф ( Q-i-тое ) ))

2. следующее приближение определяем по формуле:

Q( i-тое+1 ) = Q( i-тое ) - p*grad Ф(Q-i-тое);

, где

i=0,1,2...

p - величина шага.

3. переходим с этим приближением на шаг 1.





---



вот.

допустим, взял я в кач-ве исходной ф-цию func = x^3+6y(y-x), вручную нашел ее частные производные, и мой основной код по поиску минимума этой ф-ции имеет след. вид:

поясняю свои переменные:



//от балды взял нач. приближение

Q := 0.1;

E := 0.000000001;

//шаг

step := 0.45;

//минимум нашей ф-ции

min := 0;



//ниже идет гл. код

var res: double;



//перовоначальное значение..

res := sqrt( sqr( dfDx(Q) )+sqr( dfDy(Q) ) );



while ( res >= E ) do

begin

//1. берем новый вектор за направление

P.x := -1 * dfDx(Q);

P.y := -1 * dfDy(Q);



//2. считаем т. минимума

min := func( Q - step*dFdx(Q), Q - step*dFdy(Q) );



//3. определяем след. приближение значение функции Q

Q := func( Q - P.x*dfDx(Q), Q - P.y*dfDy(Q) );



//4. получаем новое значение res на с равнение с E в след. итерации цикла

res := sqrt( sqr( dfDx(Q) )+sqr( dfDy(Q) ) );

end;



где функция func имеет след. вид:

//возвращает само значение ф-ции по x и y

function func(x: double; y: double): double;

begin

func := x*x*x+6*y*(y-x);

end;



//и

//процедуры, отвечающие за вычисление частных производных для текущих x и y

function dfDx(x: double; y: double): double;

begin

dfDx := 3*x*x-6*y;

end;



function dfDy(x: double; y: double): double;

begin

dfDy := 12*y-6*x;

end;



--

теперь я не пойму никак, что мне передавать в строчку, где я высчитываю переменную res.

по алгоритму, надо бы передавать ей начальное приближение ф-ции..но ведь эта частная производная высчитывает значение по х и y! нафик ему Q-начальное то сувать?

и далее та же вата - не могу разобраться, как считать все эти мои dFdx() и dFdy(): то передается само значение ф-ции, а то только х, хотя по-идее нужно ВСЕГДА передавать туда только x и y.

где я не прав?

Ps: или же Q - это начальное приближение ТОЧЕК функции, т.е. x и y, а не самой функции Ф???

 

Ps: или же Q - это начальное приближение ТОЧЕК функции, т.е. x и y, а не самой функции Ф???



Конечно, Q - это аргумент фукнции (точка (x,y)).

У тебя ведь написано:

Q( i-тое+1 ) = Q( i-тое ) - p*grad Ф(Q-i-тое);

 

1. Почему Q инитишь одним числом? Это же вектор.



2.

Это что такое? Поиск минимума это итерационный процесс. Почему у тебя сразу же что-то считается? если step это число с минимом по направлению p, то Q - step*dFdx(Q), Q - step*dFdy(Q) это и есть следующий шаг, а не то, что у тебя в п. 3 написано.



3. EPS возьми побольше. Напр. 0.0001. Мантисса не резиновая



4. В теории у тебя все правильно. С кодом лажа какая-то.



5. Минимум может быть и не найден. Например в такой ситуации: (* - начало поиска)

Код (Text):

1.  
2.        ______
3.       /      \        _
4.      /        \      / \
5.     /          _min_/   \
6.    /                     \
7.   *                       \
8.  /                         \
9. /                           \
10.  

Потому что алгоритм так и покатится вниз с горки.

 

угу,

1. я уже увидел и сам.

сделал ща:

//от балды

Q.x := 1;

Q.y := 2;



2. сейчас сделал вот как:

min := func( Q.x - P.x*dFdx(Q.x, Q.y), Q.y - P.y*dFdy(Q.x, Q.y) );



3. тоже уже учел.



5. контр-пример понял. спорить не будуЖ)



теперь у меня код вылетает с ошибкой переполнения float.

вот с этим не пойму как бороться. уже и всякие там double, и extended пробовал... по идее, мне офигенная точность то и не нужна. может быть просто округлять ч/з round() какой-нить? (это я про делфи есессно.)

 

Если у тебя переполнение флоата - однозначно ты скатываешся с горки. Если конечно линейный поиск по направлению правильно работает. Совет такой: после каждой итерации выводи промежуточный результат и смотри что происходит.

 

поройся в настройках компилятора/компоновщика, чтобы программа не вылетала, а возвращала в качестве результата одно из значений: inf, +inf, -inf.