13. Итеративные методы. Постановка задачи

Ограниченные возможности симплексного метода привели к широкому распространению градиентных и других итеративных методов, в основе которых лежит понятие градиента целевой функции g(x).

Градиентом функции g(x), обозначаемым grad g(x) и , называют вектор, величина которого определяет скорость изменения функции g(x), и наибольшего возрастания этой функции. Пусть , но . (1)

Условия стационарности точки . (2) Разложим в ряд Тейлора в окрестности точки оптимума , которую считаем стационарной (3), где - отклонение от точки оптимума; (4), т. к. , то

, (5) где элементы матрицы А определяются akj по формуле (4). Разрешая систему уравнений (5) относительно , получаем: . (6) Если заменить неизвестную матрицу А-1 на матрицу Г ([γkj]), то можно надеется, что величина даст значение, более близкое к оптимуму, чем x. При этом открываются возможности многошаговой процедуры поиска.

Обозначим через , значение на n-ом шаге. Тогда процедура поиска запишется в виде .

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

Этот метод представляет собой последовательность шагов, содержащих две операции:

1) Определение направления наибольшей крутизны спуска, т. е направление антиградиента g(x).

2) Перемещение в выбранном направлении на заданное расстояние.

Математически стратегия градиентного метода получается, если перемещение на каждом шаге будет пропорционально составляющей градиента в направлении этой оси: (8) тогда Гn будет диагональной Гn =γI (9) при этом, поправка на n-м шаге равна: . (10) При таком ограничении некоторые шаги могут оказаться мелкими. Это можно исправить, используя стратегию с постоянным шагом γ. (11) где .

Метод наискорейшего спуска (подъема).

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

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

Алгоритм Ньютона.

Этот метод применим, когда поверхность отклика достаточно хорошо описывается уравнением 2-го порядка. Метод позволяет резко уменьшить число шагов. При хорошей поверхности отклика вторые производные: (12) вычисленные в точки будут близкими и элементам akj матрицы А. Используя в качестве Гn матрицу вторых производных в точке , получим вектор поправок для алгоритма Ньютона: . (13) Если разложения (3) является точным, то оптимум достигается за один шаг.

< Предыдущая		Следующая >