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

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

Затем следует определить новое направление градиента и т.д. Схематически движение по градиенту для целевой функции показано на рис. 4.21.2.

Алгоритм движения по градиенту состоит в следующем:

1. вычисление градиента в k-той точке

2. выбор шагового параметра t_k и движение по градиенту до точки

Выбор шага t_k производится неалгоритмически. С ростом k значение t_k надо уменьшать. Критерием правильного выбора величин является увеличение значений целевой функции в последовательно рассматриваемых точках. Начальная точка берется произвольно.

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

4.21.3. Метод крутого восхождения (наискорейшего спуска)

Э тот метод соединяет черты релаксационного и градиентного методов- рис. 4.21.3.

Запишем алгоритм этого метода для функции n переменных

1) вычисление градиента в k-той точке

(на рис. 4.21.3 это точки 1 = 2 = 3 =

2) выбор шагового параметра t_k и движение по направлению градиента от точки k до точки k +1, в которой значение целевой функции максимально.

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

причем движение продолжается до получения наибольшего значения

f ( ) < f ( ) < f ( ) < f ( ) < f ( ) > f ( ).

Для отыскания минимума функции идут в направлении (–grad u) (почему?).

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

В тех случаях, когда аналитическое выражение целевой функции неизвестно, градиент можно вычислять, измерив значения функции в нескольких точках, взятых вблизи k-той точки. Такая модификация метода крутого восхождения была предложена американскими математиками Боксом и Уилсоном и носит их имя.

4.21.4. Метод последовательного поворота симплекса

В пространстве Rⁿ можно ввести понятие симплекса – правильного (n+1) – гранника. Например, в R² симплекс представляет собой правильный треугольник, в R ³ – тетраэдр.

Алгоритм метода очень прост и состоит в том, что зная значения целевой функции в вершинах симплекса, переходят к новому симплексу, который получается из предыдущего симметричным отображением относительно грани, противолежащей по отношению к вершине с наименьшим значением целевой функции. Схема метода для R² показана на рис.4.21.4. Формулы для «переворота» симплекса приведены в книге: Винарский М.С., Лурье М.В. Планирование эксперимента в технологических исследованиях, Киев, «Техника», 1975.

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

Большое число других методов оптимизации рассмотрено в книге: Кузин Т.Л. Основы кибернетики. Т.1, Математические основы кибернетики. М., “Энергия”, 1973г.