Реферат: Оптимизация. Методы многомерного поиска

Здесь D - небольшое смещение в направлении x. Эту формулу часто называют "приближением секущей". Полученную информацию о направлении градиента можно использовать различным образом для построения алгоритма поиска.

Один из возможных примеров алгоритмов.

f (x) - > min, xÎRⁿ

x⁰ -начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf (j (q)), которая вычисляется q_min : j (q_min ) =minj (q)

r: =f (x⁰ ); r1: =r+2*e; x: =x⁰ ;

Пока abs (r-r1) >= e

нц

r1: =r;

x1: =x;

Для i от 1 до n

нц

l [i]: = ¶f (x1) / ¶x [i] ;

x [i]: =x [i] +q*l [i] ;

кц

j (q): =f (x);

q_min : = minf (j (q));

x: =x1;

Для i от 1 до n

x [i]: =x [i] +q_min *l [i] ;

кц

r: =f (x);

кц

6.1 Ступенчатый наискорейший подъем

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

Наискорейший подъем с использованием одномерного поиска

В некоторых методах поиска информация о градиенте используется для ведения одномерного поиска в направлении наискорейшего подъема или спуска, причем используется соотношение

x=x+Sv,