Описание метода поиска экстремума

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

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

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

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

На рисунке 5 показаны возможная траектория движения к оптимуму при применении метода наискорейшего спуска и траектория движения к оптимуму при использовании метода градиента.

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

Это объясняется тем, что движение в одном направлении производится до тех пор, пока направление движения не окажется касательным к какой-либо линии постоянного уровня. Тем самым метод наискорейшего спуска имеет сходство с методом релаксации, для которого новое направление также ортогонально предшествующему; однако в отличие от метода релаксации скорость сходимости к оптимуму не зависит от ориентации системы координат.

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

, (36)

причем  и -координаты начальной и конечной точек последнего отрезка спуска.

Этот же критерий может использоваться в сочетании с контролем значений целевой функции в точках  и :

, (37)

Совместное применение условий (36) и (37) оправдано в тех случаях, когда оптимизируемая функция имеет резко выраженный минимум.

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

При движении по заданному направлению целевая функция может считаться функцией переменного параметра h, характеризующего положение точки х на заданной прямой. Рассмотрим значения целевой функции при трех последовательных значениях h: h₁, h₂ и h₃ (рис.5).

Через точки R (h₁), R (h₂) и R (h₃) можно провести параболу

, (38)

коэффициенты а, Ь, с которой определяются решением системы уравнений

 (39) и равны

. (40)

равнение (38) позволяет найти значение h_min, при котором достигается минимум R' (h):

. (41)

Полученное таким образом значение h_min применяется в качестве задаваемого следующего значения h₄ Так как минимум R' (h), вообще говоря, не совпадает с минимумом R (h), при определении следующего значения h₅ используется новая аппроксимация для точек h₂, h₃, h₄ и т.д.

Рис.5. Определение оптимального шага с использованием аппроксимации

Изложенный метод расчета величины шага в некоторых случаях значительно ускоряет поиск оптимума. Его можно также применять и вметоде релаксации при поиске минимума для осевого направления [11].