методы решения задач безусловной оптимизации (1006295), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

5. Конец алгоритма.

Рассмотрим геометрическую интерпретацию метода наискорейшего спуска.

Из точки идем в направлении антиградиента в случае поиска минимума или градиента при максимуме до точки , в которой достигается минимальное значение функции в данном направлении. Это направление перпендикулярно касательной к поверхности (линии при n=2) постоянного уровня функции в точке , а также оно само является касательной к поверхности (линии) постоянного уровня функции в точке . Поэтому перпендикуляр к касательной из точки проводим до тех пор, пока он сам не станет касательной к другой линии уровня ( в точке )

Геометрическая интерпретация метода наискорейшего спуска причем и полученные в соответствии с данным методом точки , (к=1..3) при поиске минимума f(x). Для наглядности сравнения градиентных методов на рисунке показаны также полученные по методу градиентного спуска точки , (к=1..3). Кроме того на рисунке представлена геометрическая интерпретация данного метода. В данном методе по сравнению с методом наискорейшего спуска траектория поиска экстремума, проходящая последовательно через точки (к=0,1,2…), сглаживается. Точка находится между и . Отметим, что в связи с выражением , выбором одной и той же начальной точки для трех градиентных методов и совпадением формул для и при к=0 в методах наискорейшего спуска и сопряженных градиентов, получаем совпадение в обоих методах точек на первой итерации .

Методы случайного поиска

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

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

Рассмотрим особенности нахождения и Х^(к+1) в трех основных методах случайного поиска.

1. Метод с возвратом на неудачном шаге

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем.

1. Генерируем случайное направление в n-мерном пространстве, т.е. случайный вектор , где - случайная величина с известным законом распределения (для простоты, как правило, используют равномерное распределение на отрезке [-1;1]).

2. Примем и вычислим

3. Если в случае поиска минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х

4. Конец алгоритма.

2. Метод наилучшей пробы

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем.

1. Генерируем s случайных направлений , находим соответствующие им s значений векторов и s значений f(X_v) функции f(X) в этих точках X_v.

2. В случае поиска минимума функции f(X) выберем то , которое соответствует минимальному значению среди значений f(X_v), т.е. при примем и ; В случае поиска максимума функции f(X) при примем и .

3. Если при поиске минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х.

4. Конец алгоритма.

3. Метод с обучением

В отличие от первых двух методов без обучения в данном методе учитывается опыт выбора удачного направления поиска экстремума на двух предыдущих итерациях.

Алгоритм нахождения и Х^(к+1) на каждой итерации к состоит в следующем:

1. Вычисляем , где - случайный вектор с известной функцией распределения (часто используют равномерное распределение на отрезке от -1 до 1): - детерминированный вектор, определяемый по формуле

с использованием знака «+» при в случае поиска максимума функции f(X) и «-» при минимуме f(X);

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

1. Находим .

2. Если в случае поиска минимума f(X) (или при максимуме), то переходим к п.1, иначе Х^(к+1) =Х

3. Конец алгоритма.

8

Характеристики

Список файлов ответов (шпаргалок)