g4 (542467), страница 3

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

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

Если же среди последних n итераций не оказалось ни одной удачной, то шаг дробится.

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

Другой вариант метода покоординатного спуска может состоять в получении как решения задачи одномерной минимизации:

.

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

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

На рисунке 4.1 приведена блок-схема метода покоординатного спуска для функции дух переменных с оптимизацией длины шага.

Пример.

Найти минимум

Напомним, что эту задачу мы решали рассмотренными выше методами и встретились с трудностями в силу ее овражности.

Положим, как и раньше, ;

Находим как решение задачи одномерной минимизации, а именно, ищем , обеспечивающее минимум , это будет .

Отсюда

Далее

;

В результате выполнения 2-й итерации получили точное решение.

Рисунок 4.4.7 Блок-схема метода покоординатного спуска.

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

Под методом случайного поиска понимается группы методов, в алгоритмы которых введен элемент случайности.

Расчетной формулой этих методов будет

,

- параметр метода; - какая-либо реализация n - мерного вектора с известным законом распределения.

Очень часто предполагается, что компоненты вектора независимы и распределены равномерно на отрезке .

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

Рассмотрим несколько вариантов алгоритмов случайного поиска.

Алгоритм с возвратом при неудачном шаге.

На каждом шаге с помощью датчика случайного вектора получаем некоторую реализацию вектора .

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

Если уменьшения значения функции не наступает, то шаг признается неудачным и полагается .

Если для достаточно большого окажется, что , то принимается в качестве решения задачи минимизации.

Алгоритм наилучшей пробы.

На каждом шаге берутся s реализаций случайного вектора : и вычисляются значения .

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

Если по всем s направлениям не происходит уменьшения значения , то полагается и делается переход к следующему шагу. Величины являются параметрами алгоритма.

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

Выполним несколько шагов алгоритма наилучшей пробы для нахождения минимума

.

Пусть .

Пусть ;

Из датчика получили

; ; ;

; ;

В точке принимает наименьшее из трех значений, причем , следовательно:

.

Делаем второй шаг:

; ; ;

; ;

Отсюда:

.

Вычислительная процедура чрезвычайно проста.

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

Список файлов книги