Метод статистических испытаний

Методы выбора возможного направления движения можно разделить на случайные (статистических испытаний) и аналитические. В первом случае выполняются расчеты целевой функции Ф для некоторого множества точек, выбранных в окрестности . Выполняется сравнение значений функций и выбирается наиболее благоприятное направление.

Выбор направления по одному испытанию

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

т.е. если

, иначе .

Выбор направления по совокупности испытаний.

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

.

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

В аналитических методах определяется по некоторым детерминированным закономерностям. При повторных расчетах тем же методом и при том же исходном приближении получается та же траектория спуска.

Покоординатный спуск

Покоординатный спуск обеспечивает наиболее простой по реализации алгоритм. В качестве возможных направлений рассматриваются орты исходной системы координат:

На первом итерационном шаге целевая функция минимизируется при изменении только первой переменной, а все остальные переменные остаются неизменными (внутренний цикл):

На втором шаге процедура повторяется для второй переменной:

.

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

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

Градиентный метод

Движение осуществляется в направлении антиградиента - наибольшего убывания целевой функции:

где .

9.7. Способы задания длины шага

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

При первой стратегии (постоянный шаг), , где a - вводимая на конечном этапе константа, как правило, меньшая единицы, чаще всего a = 0,5. Для обеспечения сходимости процесса вычислений, чтобы выполнялся критерий , необходим контроль правильного задания длины шага. При нарушении критерия (см. выше) длину шага необходимо уменьшить. Уменьшение шага выполняется до тех пор пока не выполнится критерий или до выполнения критериев окончания расчетов.

Достоинство метода – малый объем вычислений на итерации (шаге). Недостаток – при неудачно выбранных и a количество шагов может быть достаточно велико и в целом объем и время расчетов недопустимо большие.

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

Зависимость Ф(l) может быть сложной, нелинейной и многоэкстремальной и находить ее глобальный минимум неприемлемо, поэтому оптимальный шаг вычислить практически невозможно. Для оценки оптимального шага зависимость Ф(l) аппроксимируют, например, полиномом второй степени

.

Псевдооптимальная длина шага определяется из условия:

.

Параметры a,b,c параболы Ф(l) можно найти по трем точкам l=0,1,2 (рис. 9.8). В качестве узлов аппроксимации принимаются значения , , в точках . Подстановка в позволяет получить СЛУ, из которой нетрудно определить искомые параметры

(9.23)

Значения l=1,2 не всегда обеспечивают корректные результаты. Величина из-за большого градиента может быть настолько большой, что новый вектор выйдет за пределы ОДЗ. В этом случае шаг необходимо масштабировать, например , k<1.

Не нашли, что искали? Воспользуйтесь поиском по сайту: