Итерационные методы поиска экстремума

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

Сначала делают выбор какой-либо точки Л'⁰) в качестве нулевого приближения. Для этой точки определяют значение целевой функции I^=fyXj. При поиске минимума из точки Х° ищут направление при движении, по которому происходит уменьшение значения функции, по крайней мере, в малой окрестности точки /₀. Вдоль этого направления выбирают следующую точку X^х =(х, jcJ) и определяют значение целевой функции I_{=fX^x. При /|</<sub>0 процедура поиска повторяется. При повторении процедуры поиска получается последовательность Х°, XХ … точек. Такая последовательность называется изображающими точками процесса поиска.

Аналитический переход от точки X^j к точке А^гу+| записывается в виде:

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

и неуспешным в случае:

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

где 8 — некоторое малое положительное число.

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

Ранее уже отмечалось, что целевую функцию /(ЛГ) можно рассматривать как функцию, определенную в «-мерном пространстве переменных (/=1,2,…,»). Так как «-мерное пространство не имеет наглядного графического представления, то применяют следующий способ изображения функции /(Л') на плоскости.

Пусть при Х = Х^от «-мерного пространства целевая функция получает оптимальное значение, это значение соответствует экстремуму функции цели, для определенности — минимуму. Проведем через точку.

Х^от двухмерную плоскость Z. При движении по плоскости Z с удалением от точки Л⁰¹" в любом направлении значение функции цели /(Л') будет увеличиваться. Если в рассматриваемой области /(Л') является.

Рис. 1.7. Линии равного уровня функции цели.

непрерывной функцией, то вокруг точки Х°^пт в плоскости Z всегда можно провести замкнутую линию, вдоль которой значение 1{Х) постоянно. Такую замкнутую линию называют линией равного уровня (изолинией) функции цели. Семейство линий равного уровня (рис. 1.7), определенных для различных значений функции цели 1{Х) = с_к, дает наглядное представление о свойствах этой функции. Следует отметить, что форма линий равного уровня для различных значений с_к может существенно отличаться и что каждая линия равного уровня (в случае минимума функции цели в рассматриваемой области) будет целиком охватывать любую линию равного уровня, для которой значение функции 1{Х) меньше. На рис. 1.7 цифры указывают значение функции цели 1{Х) на соответствующей линии.

Конечно, приведенный способ изображения функции /(А') на плоскости не является однозначным, вследствие того что форма линий равного уровня функции 1{Х) может значительно изменяться в зависимости от ориентации плоскости Z в /г-мерном пространстве. Однако, рассмотренный способ позволяет во многих случаях дать наглядную иллюстрацию работы итерационных поисковых методов.

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

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

Рис. 1.8. Гиперповерхиость (а) и линии равного уровня (б) функции цели вида 1(Х) = 3 • cos {yjxf + х* j.