Реферат: Оптимизация. Методы многомерного поиска
Будем считать, что нам известна функция
minf (j (q)), которая вычисляется qmin : j (qmin ) =minj (q)
r: =f (x0 ); r1: =r+2*e; x: =x0 ;
пока abs (r1-r) >= e
нц
r1: =r; x1: =x;
Для i от 1 до n
нц
l [i]: = random;
x [i]: =x [i] +q*R [i] ;
кц
j (q): =f (x);
qmin : = minf (j (q));
x: =x1;
для i от 1до n
нц
x [i]: =x [i] + qmin* l [i] ;
кц
r: =f (x);
кц
6. Градиентные методы
Во многих алгоритмах многомерной оптимизации так или иначе используется информация о градиентах. Проиллюстрируем это положение следующим простым примером.
Представим себе, что альпинисту завязали глаза и сказали, что он должен добраться до вершины "унимодальной" горы. Даже ничего не видя, он может это сделать, если все время будет двигаться вверх. Хотя любая ведущая вверх тропа в конечном счете приведет его к вершине, кратчайшей из них будет самая крутая, если, правда, альпинист не натолкнется на вертикальный обрыв, который придется обходить. (Математическим эквивалентом обрыва на поверхности, образуемой целевой функцией, являются те ее места, где поставлены условные ограничения) Предположим пока, что задача оптимизации не содержит ограничений.
Позднее мы включим их в схему поиска.
Метод оптимизации, в основу которого положена идея движения по самой крутой тропе, называется методом наискорейшего подъема или наискорейшего спуска. Вектор градиента перпендикулярен линии уровня и указывает направление к новой точке в пространстве проектирования.
Отметим, что градиентный метод в отличие от метода касательной к линии уровня можно использовать применительно к любой унимодальной функции, а не только тех, у которых это свойство явно выражено. Чтобы лучше понять идею градиентных методов, подробнее остановимся на свойствах градиентов. Рассмотрим систему независимых единичных векторов e
,e
,e
,…,e
, направленных вдоль осей координат x,x,x,…,x, являющихся в то же время проектными параметрами.
Вектор градиента произвольной целевой функции F (x,x,x,…,x) имеет вид:
(¶F/¶x) e+ (¶F/¶x) e+…. + (¶F/ ¶x) e,
где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде ve+ve+ve+…+ve, где
v
=
.