Файл: Методы оптимизации в статистических задачах управления..pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 100
Скачиваний: 0
Г Л А В А I I I
ПАРАМЕТРИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ СИСТЕМ УПРАВЛЕНИЯ
1. Градиентные методы
При проектировании систем автоматического управления часто приходится сталкиваться с задачей выбора некоторых параме тров х+ из условия минимума некоторого критерия качества функ ционирования системы F. В соответствии с этим рассмотрим задачу
нахождения вектора х+ = (xt, xt, ■. ., xt) из условия
F (х+) = min F (у),
у
где F (у) — F (уг, у 2, . . уп) — функция векторного перемен ного у, определяющая связь минимизируемого критерия F с управ ляемыми параметрами у = (ylt у 2, . . ., у„).
Исторически первым подходом к решению этой задачи является аналитический подход, основанный на использовании необходимых условий минимума. Как известно, эти условия
(217)
сводят исходную задачу к решению системы п нелинейных уравне
ний относительно п компонент вектора х+ = (х^, xt, . . ., х+). Эти уравнения могут иметь сложный вид и допускать не единствен ное решение. После нахождения корней уравнения (217) необ ходимо исследовать характер поверхности функции в окрестности точки х+, чтобы выделить локальные точки минимума. Аналитиче ский метод минимизации оказывается эффективным обычно только в тех случаях, когда известно аналитическое выражение миними зируемой функции F (у). Практически при оптимизации систем автоматического управления более целесообразно применять чис ленные методы минимизации.
Старейшим численным методом решения этой задачи является градиентный метод, алгоритм которого имеет вид
(218)
где at — значение шага на і-й итерации.
Точка х° называется начальным приближением метода. Градиентный метод является типичным представителем ли
нейных методов. Как следует из равенства (218), очередное
89
приближение хі+х получается из предыдущего х1путем движения в направлении антиградиента. Это направление наиболее быстрого
убывания функции в окрестности точки х ‘, если предположить, что здесь функция достаточно точно аппроксимируется линейной функцией.
Одним из недостатков всех линейных методов, в том числе и градиентных, является зависимость итерационной последователь ности от выбранной системы координат и, в частности, от масшта бов переменных функции. Пусть, например, при использовании формулы градиентного метода (218) была получена итерационная
последовательность \х1}. Затем была введена новая система коор динат, причем координаты новой системы у и старой системы х связаны соотношением
Ау = X,
где А — неособенная матрица размерности [п, п]. В пространстве переменных у градиентный метод минимизации функции
F(x) = F (Ау) = Ф (у)
будет иметь вид
(219)
Предположим, что в пространстве у градиентный метод осуще ствляется с теми же значениями шага а (., что и в пространстве х, причем начальное приближение у0 естественным образом согла суется с приближением х°:
х° = А у0.
Произведем пересчет последовательности точек \у‘\ в про
странство параметров х. Соответствующие точки обозначим х1:
X1 = Ау1. |
(220) |
Подставляя в равенство (219) выражение для производной функции Ф (у):
дФ (У) _ л* dF (Ау)
ду дх
и учитывая формулу (220), получим рекуррентное соотношение для последовательности \х1\ в следующем виде:
кі+1 = х‘ - щАА' |
, і = 0, 1, 2, |
|
(221) |
где знак * означает операцию транспонирования матрицы. Сравнивая формулы (218) и (221), получаем, что в общем слу
чае изменение системы координат изменяет итерационную после
90
довательность, получаемую в процессе применения градиентного метода. В частности, из соотношения (221) видно существенное влияние масштабов для оптимизируемых параметров. Итерацион
ная последовательность {х 1) будет полностью совпадать с после довательностью {*‘} только в том случае, если
А А* = Е, |
(222) |
где Е — единичная матрица. Как известно из линейной алгебры [98], матрица А, удовлетворяющая условию (222), называется ортогональной, а соответствующее преобразование — ортого нальным. Геометрически ортогональное преобразование соответ ствует повороту системы координат в пространстве.
Из равенства (222) видно, что процедура вычисления обратной матрицы для ортогональной матрицы сводится просто к операции транспонирования:
А - 1 = А*.
Из формулы (221) следует, что применение градиентного ме тода имеет столько же оснований, что и использование метода, основанного на соотношении
* '+1 = |
- atB |
, (і = 0, 1, 2, . . .), |
(223) |
где В — произвольная симметричная положительно определенная матрица. Действительно, так как для такой матрицы всегда можно найти [98] неособенную матрицу С, удовлетворяющую условию
СС* = В,
то итерационную процедуру (223) можно рассматривать как обыч ный градиентный метод в пространстве параметров г, связанных
спараметрами х посредством соотношения
х= Cz.
Наиболее широко распространены две модификации градиент ного метода:
1. Простой градиентный метод, или метод простой итерации, где размер шага остается постоянным в течение всей итерационной
процедуры: |
|
аі = а = const. |
(224) |
2. Метод наискорейшего спуска, в котором на каждой итера ции размер шага выбирается из условия минимума функции в на правлении антиградиента. Иначе говоря, at выбирается из условия
dF (х1) |
= min F |
■а |
dF(xl) |
\ |
' |
і = 0, 1, 2, ... |
дх |
а>0 |
|
дх |
) |
|
Существует обширная литература, посвященная исследованию условий и скорости сходимости градиентных методов [43, 79,
91
80]. Для простоты изложения проанализируем скорость сходи мости градиентных методов на примере квадратичной функции. Этот анализ имеет практический интерес, так как функции в окрест ности точки экстремума с достаточной точностью обычно могут быть аппроксимированы квадратичной функцией. Рассмотрим вначале скорость сходимости простого градиентного метода. Пусть минимизируемая функция имеет вид
F (x) = 4 - X*QX = |
4~ S |
2 xixjqlh |
(225) |
z |
z /=1 |
/=i |
|
где Q — симметричная положительно определенная матрица. Введем новую систему переменных у = (уг, у 2, . . ., уп), свя
занных с исходными переменными х посредством ортогонального преобразования А:
X = Ау; АА* = Е.
В новой системе координат функция F (х), выраженная через переменные у, имеет вид
a>(y) = F(Ay) = ±-y*A*QAy.
Выберем ортогональное преобразование А из условия приве дения матрицы A*QA к диагональному виду. В линейной алгебре доказывается возможность и предлагаются методы решения по добной задачи. Полученную таким образом диагональную матрицу обозначим Л. Диагональные элементы матрицы Л будем обозна чать А,2, . . Хп. Как известно, эти параметры называются собственными значениями матрицы Q.
Особый интерес представляют минимальное собственное зна чение т = min {Alt Х2, . . . , Хп) и максимальное собственное зна чение М = max {Ац Х2, . . ., Хп\ [98]. Вследствие положитель ной определенности матрицы Q значения т и М должны быть поло жительными:
A*QA = Л.
В этом случае функция Ф (у) имеет существенно более простой
вид
Ф ( у ) = ~ ^ У А у = ^ - ^ Х Л
В соответствии с этим простой градиентный метод примени тельно к этой функции Ф (у) определит следующую итерационную
последовательность точек {у1}:
у‘+г = У І - а Х кУІ, і = 0, 1, 2, . . . ; £ = 1 , 2 , . . . , « . (226)
Как было показано выше, если матрица А ортогональная и имеет место равенство х° = Ау°, то точки итерационной последо
вательности {у‘) находятся в простом соответствии с точками ите-
92
рационной |
последовательности |
{х c}t |
полученной |
применением |
простого градиентного метода к функции (225): |
|
|||
|
X1 = |
Ау1. |
|
|
Отсюда |
следует, что модуль |
вектора х! совпадает с модулем |
||
вектора у 1: |
|
|
|
|
|
х**х‘ == у1*А*Ау1 = |
t/ У . |
(227) |
Из равенства (226) легко получить выражение компонент век тора у1+1 через компоненты у0:
Ук+1 = УІ( 1— аЛ*),+1; f = 0, 1, 2, |
6 = 1 , 2 , . . . , л. (228) |
Анализируя равенство (228), можно заключить, что когда о зна чении начального приближения у° ничего неизвестно, естественно выбирать значение шага градиентного метода из условия
max I 1 •—a°Kk | = |
min max | 1 — a Xk |. |
k |
a k |
Решая это уравнение, получим
m in {X,-} + |
m ax {Xj} |
m + M ’ |
' ' |
i |
i |
|
|
max |
II |
m i |
= |
A4 — от |
1 |
— a°Xk |
— . |
||
k |
1 |
* 1 |
M + m |
Используя равенства (227), (228) и решение (229), нетрудно получить оценки скорости сходимости:X
X1 |
|
|
М — т \ |
і . |
|
|
|
Ж +т ) |
' |
||
|
|
|
|||
П |
М — от |
21 І y f h |
= F(x°)( М — от \ 2» |
||
k=\ |
|||||
ÄT+OT |
k=i |
\ A4 -f от / |
Заметим, что так как для рассматриваемого случая функция F (х) достигает своего минимума в точке х+ — 0 и минимальное значение F (0) = 0, то окончательные оценки скорости сходимости простого градиентного метода при оптимальном способе выбора шага имеют следующий вид:
Y + I^ ( М -j- от )
(230)
F (х1) — F (*+) ^ [F (х°) — F (*+)] ( М — от \ 2 І
М - \ - т У
Нетрудно показать, что оценки скорости сходимости, получен ные для квадратичной функции специального вида (295), справед ливы и для произвольной квадратичной функции. В этом случае т и М имеют смысл минимального и максимального собственных
93
значений для матрицы вторых производных минимизируемой ква дратичной функции.
Из оценок (230) следует, что для квадратичной функции F (х), определяемой формулой (225), итерационная последовательность
[х1], построенная на основе простого градиентного метода с опти мальным значением величины шага, сходится к истинной точке минимума х+ = 0 по закону геометрической прогрессии с знамена
телем k — -д ~ га., Соответствующее значение функции при этом
убывает также по закону геометрической прогрессии с знаменате-
лем (^ і_ р -- у . Это означает, что простои градиентный метод
сходится тем быстрее, чем меньше отличаются величины макси мального и минимального собственных значений.
Отношение р = М/т называют коэффициентом обусловлен ности матрицы Q. Если значение р велико, то матрица считается плохо обусловленной, если р ^ 1, матрица хорошо обусловлена. Подставляя выражение для р в формулу для знаменателя геоме трической прогрессии k, получим связь k и р:
k = 1 - 1 /Р
1 + 1/Р '
Отсюда для плохо обусловленных матриц имеет место прибли женное равенство
k1 — 2_
Р‘
Сравнивая алгоритмы простого градиентного метода и метода наискорейшего спуска, можно увидеть, что реализация первого метода проще, так как в процессе реализации метода наискорей шего спуска на каждой итерации необходимо решать задачу мини мизации функции в направлении антиградиента. Однако, как показывает теоретическое исследование, скорость сходимости ме тода наискорейшего спуска оказывается приблизительно такой же, как и простого градиентного метода. В частности, были получены следующие оценки для метода наискорейшего спуска примени тельно к квадратичной функции [43]:
\уі |
Ѵ+І „ л Г |
2 (F(x°)-F{x+)) |
( M - m \ . |
|
Iх - x К у |
--------- й |
--------- \ Ж Т ^ ) ' |
||
F (Х{) - |
F (х+) ^ |
(F ( х °) - |
F ( х +)) |
. |
Сравнение формул (230) и (231) показывает, что оценка скорости сходимости обоих методов практически совпадает. Наблюдается полное совпадение по скорости убывания значения функции, а ско
рость убывания модуля вектора ошибки ] х1— х+ j в простом гра-
94