Оптимальная система автоматического управления (стр. 2 из 7)
С другой стороны, если исследующий поиск неудачен, то необходимо вернуться в точку xk и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете, возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и продолжить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой.
Рис. 1.1 - Метод поиска Хука-Дживса
Преимущества метода:
· несложная стратегия поиска;
· невысокий уровень требований к ЭВМ;
· широкое применение в инженерных приложениях.
Недостатки:
· при значительных нелинейных эффектах алгоритм вырождается в последовательность исследующих поисков без переходов к ускоряющему поиску по образцу.
1.2 Градиентные методы.
Важность прямых методов неоспорима, т.к. в практических задачах информация о значениях целевой функции является единственно надежной информацией, которой располагает инженер. Однако, если существует и непрерывны целевая функция f(x) и ее первые производные, aтакже они могут быть записаны в аналитическом виде (или с достаточно высокой точностью вычислены при помощи численных методов), то целесообразно использовать методы, основанные на использовании градиента целевой функции.
Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой
xk+1 = xk + ks(xk),
где xk - текущее приближение к решению x*;
k - параметр, характеризующий длину шага,
s(xk) - направление поиска в N - мерном пространстве управляемых переменных xi, i = 1, 2,..., N.
Способ определения k и s(xk) на каждой итерации связан с особенностями применяемого метода. Обычно выбор k осуществляется путем решения задачи минимизации f(x) в направлении s(xk). Поэтому при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.
В основе метода лежит следующая итерационная модификация формулы
xk+1 = xk + ks(xk),
xk+1 = xk - k f(xk),
где - заданный положительный коэффициент;
f(xk) - градиент целевой функции первого порядка.
Недостатки:
· необходимость выбора подходящего значения ;
· медленная сходимость к точке минимума ввиду малости f(xk) в окрестности этой точки.
Свободен от первого недостатка простейшего градиентного метода, т.к. k вычисляется путем решения задачи минимизации f(xk) вдоль направления f(xk) с помощью одного из методов одномерной оптимизации
xk+1 = xk - k f(xk).
Данный метод иногда называют методом Коши.
Алгоритм характеризуется низкой скоростью сходимости при решении практических задач. Это объясняется тем, что изменения переменных непосредственно зависит от величины градиента, которая стремится к нулю в окрестности точки минимума и отсутствует механизм ускорения на последних итерациях. Поэтому, учитывая устойчивость алгоритма, методнаискорейшего спуска часто используется как начальная процедура поиска решения (из точек, расположенных на значительных расстояниях от точки минимума).
Метод сопряженных направлений
Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), xÎEn, где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением Ñf(x*)=0.
Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), xÎEn, где f(x) является целевой функцией n независимых переменных.
Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.
Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений
1.3 Методы второго порядка
Метод Ньютона
Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле
xk+1 = xk - 2 f(xk-1) f(xk).
Недостатком метода Ньютона является его недостаточная надежность при оптимизации не квадратичных целевых функций. Поэтому его часто модифицируют:
xk+1 = xk - k 2 f(xk-1) f(xk),
где k - параметр, выбираемый таким образом, чтобы f(xk+1) ® min.
2. Нахождение экстремума функции без ограничения
2.1 Метод наискорейшего спуска
Алгоритм данного метода отражается поисковой формулой:
(2.1)где k – номер итерации, S – направление, в котором делается следующая итерации,
- величина шага в этом направлении. Знак « - » берется при поиске минимума. Если двигаться не в произвольном направлении S, а по градиенту, то формула выглядит так: 
(2.2)где
- градиент функции.Градиент функции в некоторой точке – вектор, показывающий направление наибольшей скорости увеличения функции
.Дана функция:
с начальной точкой
.Воспользуемся теоремой Ферма для определения экстремума:
(2.3)Решим полученную систему:
=> 
, точка 
- точка безусловного экстремума.1) Найдем градиент функции в точке
: 
Оптимальную величину шага можно найти по формуле:
, (2.4) где Н – матрица Гессе.Матрицу Гессе определяется по формуле:
(2.5)Тогда получаем:
.Найдем величину оптимального шага:
Подставим все найденные значения в формулу (2.2) и найдем координаты точки
: 
Получили новую точку с координатами
Проверка:
2) Точку
примем за начальную: 
Найдем оптимальную величину шага:
Находим
с помощью величины шага: 
Получили новую точку с координатами
Проверка:
3) Точку
примем за начальную: 
Определяем величину шага:
Находим
: 
Получили новую точку с координатами
Проверка:
И так далее до выполнения условий точности вычисления экстремума функции:
2.2 Метод сопряженных направлений
Рассматриваемый метод является градиентным методом второго порядка. Назовем некоторые направления
. Эти направления называются сопряженными по отношению к некоторой положительно определенной матрице Гессе (Н), если выполняется соотношение: