Читайте также:
|
В двумерном случае это будет окружностью радиуса R вокруг точки X0.
Алгоритм:
1. В начальной точке Х0 случайным образом выбираются направления и для всех выбранных направлений на расстоянии R вычисляются значения из всех точек выбирается точка с наименьшим значением целевой функции. Пусть будет х1.
2. Производится поиск по образцу: вдоль прямой х1 происходит поиск точки х2.
3. Все процедуры повторяются для новой точки х2.
Методы случайного поиска целесообразно использовать в задачах большой размерности или как минимум для определения начальных точек для более сложных методов. Методы случайного поиска повышают возможность обнаружения окрестностей глобального минимума.
Билет 8.
Безусловная многомерная минимизация первого порядка решения задач НЛП.
Метод градиентного спуска.
Градиент - это вектор, направленный по нормали к поверхности уровня в заданной точке в сторону возрастания функции.
В точке максимума градиент равен 0. Данное свойство используется в этом методе. Берется противоположное градиенту направление для поиска минимума целевой функции. Берется шаг h>0 и начальная точка х0, итерационный процесс строится по одной формуле:
Xk+1=xk-h*grad(Ф(xk))
На каждой итерации значение целевой функции должно уменьшаться, процесс повторяется до тех пор, пока на каком-то этапе не будет выполнено условие |gradФ|<E.
Для произвольной функции Ф рассчитывать производную по какому-либо направлению надо по формуле:
dF(x)/dxj=(Ф(x+hej)-Ф(x-hej))/2h
Безусловная многомерная минимизация первого порядка решения задач НЛП. Метод наискорейшего градиентного спуска.
В данном методе на каждом этапе находится шаг h, такой, что значения целевой функции на каждом этапе максимально уменьшаются. Для этого используется формула градиентного спуска и к правой и левой частям применяется та же самая целевая функция. Глядя на правую часть можно сказать, что если рассматривать это выражение как аргумент функции, то получаем функцию ф(h), как функцию одного аргумента h поскольку значения хk нам известны. И для каждого этапа, для поиска максимального значения шага h можно найти минимум этой функции ф. Минимум находится при min(ф(h))= dф(h)/dh. Получается, что на каждом этапе метода составляется и решается дополнительное уравнение, решением которого будет максимальное значение шага h для данного этапа, при котором целевая функция максимально уменьшается.
Безусловная многомерная минимизация первого порядка решения задач НЛП. Аппроксимация квадратичной функцией, понятие сопряженных направлений.
Дата добавления: 2015-02-16; просмотров: 97 | Поможем написать вашу работу | Нарушение авторских прав |