Файл: Методы оптимизации в статистических задачах управления..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