|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Обсуждены характерные постановки некоторых задач оптимального оценивания и способы их решения.
ЗАДАЧИОПТИМАЛЬНОГО ОЦЕНИВАНИЯ
В. Б. КОЛМАНОВСКИЙ
Московский государственный институт электроники
и математики (технический университет)
ВВЕДЕНИЕ
Одна из основных форм бытия состоит в проведении наблюдений за тем или иным явлением, в обработке их результатов и прогнозировании будущего развития рассматриваемого явления.
Именно поэтому на протяжении многих столетий проблема оценивания была и остается предметом исследований многих ученых (К.Ф. Гаусс, Н. Винер, А.Н. Колмогоров и др.). Примечательно в этом отношении, что характерные постановки математических задач теории оценивания были продиктованы запросами реальной жизни. При этом меняющиеся возможности реализации процедур оценивания приводили к значительному усовершенствованию и их алгоритмов.
В этой связи замечательным событием было открытие в 60-е годы алгоритма оценивания Калмана-Бьюси, в котором в значительной мере консолидированы многие ранее предложенные процедуры оценивания. Существенной особенностью алгоритма оценивания Калмана-Бьюси, чрезвычайно важной с практической точки зрения, является то, что в отличие от предшествующих процедур нет необходимости помнить всю предшествующую информацию. Будущее состояние системы определяется только ее текущей оценкой и вновь поступившей информацией.
Указанная процедура столь проста и эффективна, что сразу же нашла многочисленные применения в практических задачах, связанных с оцениванием состояний объектов. Более того, в настоящее время трудно представить себе сколько-нибудь реальную динамическую систему, в которой бы не использовался алгоритм оценивания Калмана-Бьюси.
Настоящей статьей автор преследовал цель простым языком и несложными математическими средствами проиллюстрировать современное состояние теории оценивания, а также наметить дальнейшие направления исследований.
Эволюция во времени некоторой системы может быть определена, если задана ее математическая модель и, кроме того, известны входные воздействия и состояние системы (фазовый вектор) в некоторый момент времени. При этом знание фазового вектора существенно не только для определения изменения состояния системы, но и для построения управляющего воздействия на нее, которое осуществляется по принципу обратной связи.
В некоторых ситуациях фазовый вектор недоступен точному измерению либо по техническим причинам, либо вследствие чрезмерно большой стоимости проведения процесса наблюдения. В этих ситуациях фазовый вектор должен быть определен на основании результатов измерений выхода системы. При этом если ошибка измерений и возмущения, действующие на систему, не учитываются, то говорят о задачах детерминированного наблюдения. В противном случае возникают различные задачи оценивания при неполной информации. Дальнейшая детализация постановок этих задач зависит от многих факторов, в частности от предположений о возмущениях, действующих на систему, и ошибках измерений, выборе меры близости между фазовым вектором и его оценкой в классе допустимых оценивателей и т.д.
Ниже рассматриваются некоторые практически важные задачи оценивания в предположении, что возмущения, действующие на систему, и ошибки измерений интерпретируются как случайные процессы с заданными статистическими характеристиками.
1. ПОСТАНОВКА ЗАДАЧИ
ОПТИМАЛЬНОГО ОЦЕНИВАНИЯ
Предположим, что состояние системы в момент времени t определяется, вообще говоря, случайным вектором x(t) k Rn, где t $ t0 и t0 - заданный начальный момент времени. При каждом t $ t0 наблюдается другой случайный вектор, y(t) k Rm. Требуется при каждом t построить такую функцию , зависящую от - результатов измерений y(s), t0 # # s # t, которая в некотором смысле наилучшим образом аппроксимировала бы неизвестный фазовый вектор x(t). При этом функция обычно именуется оценкой вектора x(t). Для завершения постановки задачи необходимо разъяснить, что значит "наилучшим образом". Подобно задачам оптимального управления, выбор критерия оптимальности оценки зависит от конкретной рассматриваемой задачи. Вместе с тем в математической теории оптимального управления главным образом изучаются задачи, использующие среднеквадратическое отклонение как меру точности оценивания, которое определяется выражением
Здесь M - знак математического ожидания, | " | - евклидова норма в пространстве Rn.
Среднеквадратическое уклонение (1) иногда называют средней квадратической погрешностью или ошибкой оценки.
Задача оптимального оценивания с критерием (1) состоит в определении такой функции F, что критерий (1) принимает наименьшее возможное значение. Использование среднеквадратического уклонения в задачах оценивания восходит к предложенному К.Ф. Гауссом в 1795 году методу наименьших квадратов, примененному им при решении некоторых конкретных задач. Например, в 1801 году первый открытый астероид Церера скрылся из поля зрения, причем его траектория была измерена лишь на 1/40 части орбиты. Дальнейшие попытки астрономов определить местоположение Цереры были тщетны. И лишь Гаусс, используя метод наименьших квадратов, оценил траекторию астероида настолько точно, что последний был вновь обнаружен.
Отметим, что привлекательность критерия (1) объясняется еще и тем, что многие задачи оценивания с этим критерием допускают аналитическое решение. В частности, предположим, что процессы x(t) и y(t) имеют конечные вторые моменты, и положим
Здесь выражение в правой части представляет собой условное математическое ожидание вектора x(t) при условии, что на отрезке [t0 , t] был измерен процесс . Из (2) вытекает, что m(t) представляет собой наилучшую в среднеквадратическом смысле оптимальную оценку вектора x(t). Действительно,
Отсюда видно, что функция F, минимизирующая ошибку оценки, должна совпадать с m(t).
При этом Mm(t) = Mx(t), то есть оценка m(t) вектора x(t) является несмещенной. Кроме того, M(x(t) - m(t))y(s) = 0, t0 # s # t, то есть величины x(t) - m(t) и y(s) являются некоррелированными. Оптимальная оценка (2) может быть вычислена по формуле Байеса.
Однако реальное использование оптимальной оценки (2) представляется крайне затруднительным из-за трудностей эффективного вычисления выражения (2) в общей ситуации.
Представляются возможными два пути преодоления упомянутых трудностей: во-первых, сузить класс функций F, среди которых ищется оптимальная оценка, и, во-вторых, ограничить класс случайных процессов x(t), y(t). Простейшим и часто используемым способом реализации первого подхода является построение оптимальной оценки в классе линейных функций F. При ряде предположений оптимальная линейная оценка ml(t) удовлетворяет уравнению
M[ml(t)y(s)] = M[x(t)y(s)], t0 # s # t.
Теория линейного оценивания для случая, когда x(t) и y(t) - стационарные и стационарно связанные случайные процессы, развита в работах А.Н. Колмогорова [1] и Н. Винера [2]. Эта теория нашла применение при управлении огнем зенитной артиллерии, в статистических задачах теории связи и теории информации. Описание этих приложений теории линейного оценивания дано в книге [3, гл. 12].
Следует подчеркнуть, что предположение о линейности оценки может оказаться серьезным ограничением в том смысле, что оптимальная линейная оценка ml(t) может давать существенно худшее приближение вектора x(t) по сравнению с другими способами оценивания. Пусть, например, имеется последовательность случайных величин yn = exp (ijn), где n - целое число, j - случайная величина, равномерно распределенная на отрезке [- p, p]; i 2 = -1. Предположим, что наблюдаются (измеряются) все величины yn при всех n ? m и требуется по результатам измерений восстановить величину x = yn . Имея в виду уравнения вида (2') для оптимальной линейной оценки, заключаем, что она должна равняться нулю вне зависимости от конкретных результатов наблюдений. В то же время величина x восстанавливается точно по измерениям yn и yn + 1 при любых n, поскольку x = (yn + 1)m - n(yn)n - myn .
В связи с этим примером возникает вопрос о том, при каких дополнительных ограничениях оптимальная линейная оценка совпадает с оптимальной в среднеквадратическом смысле оценкой. Указанное совпадение имеет место для гауссовских процессов (x(t), y(t)) (то есть процессов, все конечномерные распределения вероятностей которых гауссовские) с нулевым математическим ожиданием. Действительно, в этом случае из отмеченной выше некоррелированности величин x(t) - m(t) и y(s) вытекает их независимость. Поэтому
2. ФИЛЬТР КАЛМАНА-БЬЮСИ
С прикладной точки зрения желательно, чтобы оптимальная оценка имела рекуррентный характер. Это требование означает, что при любом D $ 0 оценка m(t + D) должна полностью определяться значением оценки m(t) в предшествующий момент времени t и новыми наблюдениями y(s), t # s # t + D. Иными словами, ранее вычисленная оценка m(t) корректируется только на основе вновь поступивших измерений y(s), t # s # t + D, без необходимости повторять все предшествующие вычисления. Первый вариант рекуррентной процедуры оценивания метода наименьших квадратов был предложен Гауссом в 1821 году. Для случая, когда процессы x(t) и y(t) описываются стохастическими уравнениями, указанная процедура была предложена Р. Калманом и Р. Бьюси [4]. Обычно она называется фильтром Калмана-Бьюси. Дальнейшему развитию и многочисленным приложениям фильтра Калмана-Бьюси посвящена обширная литература (см., например, [5]).
2.1. Дискретное время
Рассмотрим задачу фильтрации для случая, когда эволюция системы x(ti) и процесс наблюдения y(ti) за этой системой удовлетворяют соотношениям
x(ti + 1) = Aix(ti) + z(ti),
y(ti) = Qi x(ti) + h(ti), ti < ti + 1 .
Здесь x(ti) k Rn, y(ti) k Rm, случайные возмущения z(ti) k Rn и h(ti) k Rm имеют нормальное распределение с нулевым математическим ожиданием и матрицами ковариации Gi (размерности n i n) и si (размерности m i m), причем матрицы si положительно определены. Априорное распределение вектора x(t0 - 0) непосредственно перед началом процесса наблюдения считается известным. Оно является гауссовским с заданным математическим ожиданием m0 и матрицей ковариации D0 > 0. Случайные векторы x(t0 - 0), z(ti), h(ti) при всех i взаимно независимы.
Система (3) может быть использована как для моделирования дискретного процесса наблюдения, так и в качестве аппроксимации задачи фильтрации с непрерывным временем.
При сделанных предположениях условное распределение вероятностей x(ti) при условии, что заданы y(tj), 0 # j # i, является нормальным, то есть характеризуется условным математическим ожиданием m(ti) и матрицей ковариации D(ti). Указанные характеристики m(ti) и D(ti) изменяются на интервале между наблюдениями в силу уравнений (3), а в момент наблюдений ti пересчитываются в соответствии с формулой Байеса.
Обозначим m(ti - 0), D(ti - 0) значения функций m и D непосредственно перед i-м измерением, а m(ti + 0) и D(ti + 0) - сразу после i-го измерения. В силу (3)
m(ti + 1 - 0) = Aim(ti + 0),
D(ti + 1 - 0) = AiD(ti + 0)
где штрих - знак транспонирования.
Далее, используя теорему о нормальной корреляции [6], имеем
где D-1 - матрица, обратная к D.
Уравнения (4) и (5) описывают эволюции оптимальной оценки m и матрицы ковариации D, происходящие вследствие движения системы и проведения наблюдений за ней.
2.2. Непрерывное время
Рассмотрим задачу фильтрации в предположении, что движение системы x(t) и процесс наблюдения за ним y(t) описываются системой линейных стохастических уравнений Ито, имеющей вид
dx(t) = A(t)x(t)dt + s(t)dx(t), x(0) = x0 , 0 # t,
dy(t) = Q(t)x(t)dt + s0(t)dx0(t), y(0) = 0.
Здесь векторы x(t) k Rn, y(t) k Rm, матрицы A, s, Q, s0 заданы и имеют измеримые ограниченные элементы. Через x и x0 обозначены стандартные винеровские процессы произвольных размерностей, а через x0 - гауссовский случайный вектор, параметры распределения вероятностей которого Mx0 = 0, Считается, что случайные величины x(t), x0(t), x0 взаимно независимы, а матрица ковариации D0 положительно определена. Матрица невырождена при всех t.
Задача фильтрации состоит в построении наилучшей в среднеквадратическом смысле оценки вектора x(t) по результатам наблюдений y на отрезке [0, t].
Обозначим через m(t) и D(t) соответственно условное математическое ожидание и матрицу ковариации вектора x(t) при условии
В силу результатов раздела 1 вектор m(t) представляет собой наилучшую в среднеквадратическом смысле оценку x(t), а D(t) есть матрица ковариации разности x(t) - m(t). Из сделанных предположений о параметрах систем (2.1), (2.2) вытекает, что совместное распределение вероятностей процесса (x(t), y(t)) гауссовское. Поэтому оптимальная оценка m(t) является линейным функционалом от результатов наблюдений, то есть
Здесь матрица u(s, t) размера n i m (ядро оценки) подлежит определению из условия минимума по u выражения M | x(t) - m(t) | 2 = J.
Дальнейшее исследование может быть осуществлено двумя независимыми путями. Во-первых, систему уравнений (6) можно аппроксимировать разностной системой (3) и затем перейти к пределу в уравнениях (4), (5) (см., например, [7]). В результате для оптимальной оценки m(t) и матрицы ковариации D(t) получаем уравнения
Уравнение (8) не зависит от результатов наблюдений yt . Поэтому ошибка оценивания в момент времени t, равная TrD(t), может быть вычислена заранее, до начала процесса измерения. Уравнение (8) представляет собой матричное дифференциальное уравнение Риккати, напоминающее аналогичное уравнение в теории линейно-квадратичных детерминированных задач оптимального управления [8]. Эта аналогия не случайна. Она является следствием принципа двойственности между задачами оптимального управления и наблюдения. Использование этого принципа в рассматриваемом случае представляет собой второй способ получения уравнений (8), (9). Точнее говоря, из уравнений (6) вытекает, что ядро u(s, t) оптимальной оценки (7) удовлетворяет равенству
Здесь Tr - след матрицы, а детерминированная функция a(s) при 0 # s # t удовлетворяет уравнениям
0 # s # t, a(s) = I,
где I - единичная матрица.
Соотношение (10) показывает, что функция u(s, t), минимизирующая ошибку оценивания, одновременно доставляет минимум квадратичному функционалу J1 на траекториях линейной системы (12). Используя теперь явное решение линейно-квадратичной задачи (11), (12), приходим к уравнениям (8), (9) для D(t) и m(t). Если относительно x0 выполнены ранее сделанные предположения, но Mx0 = = m0 , то меняется лишь начальное условие для уравнения (9), принимающее вид m(0) = m0 , при этом остальные соотношения фильтра Калмана-Бьюси остаются без изменения.
Фильтр Калмана-Бьюси обобщался в различных направлениях, например для систем, описываемых уравнениями в частных производных, интегральными уравнениями, уравнениями с последействием, уравнениями с вырожденными шумами, нелинейными уравнениями и т.д.
3. ОПТИМИЗАЦИЯ ПРОЦЕССА НАБЛЮДЕНИЯ
При рассмотрении задач оптимального оценивания состояния x(t) системы (6) по результатам измерений предполагалось, что матрица состава измерений Q(t) и их точности s0(t) заданы и фиксированы. Однако в некоторых реальных ситуациях в процессе измерений можно варьировать как комбинации наблюдаемых координат системы, так и точность их измерений. Это приводит к различным задачам управления процессом наблюдения (иначе называемым задачами оптимизации процесса наблюдения [7]). Такие задачи стали особенно актуальны в последнее время в связи с разработкой и совершенствованием датчиков систем управления, а также широким внедрением ЭВМ, что привело к совершенствованию функционирования систем управления и одновременно их к удорожанию. Усложнение используемых измерительных приборов и алгоритмов обработки наблюдений приводит также к существенному запаздыванию при применении результатов измерений. При этом точность определения координат характеризуется матрицей D(t), а управление наблюдением - матрицей которые связаны уравнением фильтра (8).
Обычно наблюдения проводят с целью оптимизировать точность определения величины q'x(T ), где q - заданный вектор из Rn. Если, например, i-я компонента вектора q равна единице, а все остальные равны нулю, то q'x(T ) = xi(T ) и задача сводится к оптимизации точности определения xi(T ). При этом указанная точность может быть охарактеризована дисперсией величины q'x(T ). Таким образом, критерий качества J в задачах оптимизации процесса наблюдения можно задать в форме
J = q'D(T )q.
Управление u(t) наблюдениями может быть подчинено некоторым ограничениям. Приведем в качестве иллюстрации некоторые из них, имеющие вид
Здесь U(t) - заданное множество матриц, определяемое возможностями управления наблюдениями, Fi - заданные скалярные функции, а Ci - заданные постоянные. С помощью функционалов типа Ji могут быть учтены имеющие место в задаче ограничения на стоимость проведения измерений или их длительность. Соотношения (8), (13), (14) показывают, что задачи оптимизации процесса наблюдения являются обычными задачами оптимального управления детерминированными системами (8) для матрицы ковариации.
Отмеченная аналогия позволяет также сформулировать и иные постановки задач управления наблюдениями. Можно, например, ставить задачи, в которых минимизируется один из функционалов Ji и выполнено ограничение J # c0 , что соответствует ситуациям, в которых требуется минимизировать стоимость или длительность наблюдений и обеспечить точность определения величины q'x(T ) не ниже заданной.
Кроме того, из-за указанной аналогии для решения задач оптимизации процесса наблюдения могут быть использованы методы решения задач оптимального управления детерминированными системами (например, принцип максимума или метод динамического программирования [8]).
Пример. Пусть уравнения движения системы и наблюдения (6) скалярные и имеют вид
Здесь a и s0 ? 0 - заданные постоянные, x0 - гауссовская случайная величина.
Управление наблюдениями y(t) осуществляется скалярной измеримой функцией Q(t), которая при каждом t может быть равна либо нулю, либо единице, причем суммарное время наблюдений T0 (0 # # T0 # T ) задано. Вследствие независимости случайных величин x0 и x0(t) равенство Q(t) = 0 в некоторый момент времени означает, что в этот момент времени наблюдения не производят. Ограничение на суммарную длительность процесса наблюдения эквивалентно изопериметрическому условию
Цель управления наблюдением - выбрать такую функцию Q(t), удовлетворяющую перечисленным условиям, чтобы минимизировать дисперсию D(T ).
Ввиду (8) уравнение для D(t) имеет вид
Нелинейное уравнение (16) именуется уравнением Бернулли и является частным случаем уравнения Риккати.
Удобно ввести новую неизвестную функцию a(t) = = D -1(t), которая ввиду (16) удовлетворяет линейному уравнению. В терминах функции a(t) задача управления состоит в выборе управления u(t) такого, что
В силу (15), (18) гамильтониан H имеет вид
Здесь y0 - постоянная, а сопряженная переменная y(t) определяется соотношениями
Из условия максимальности гамильтониана H по u вытекает, что
где положено
Из уравнения и граничного условия для y(t) следует, что y(t) = D 2(T ) exp [2a(t - T )]. Так как D(T ) > 0, то y(t) монотонно возрастает при a > 0 и монотонно убывает при a < 0.
Отсюда и из (19) вытекает, что если a > 0, то
если же a < 0, то
Здесь через t0 обозначен единственный момент переключения управления u(t), равный единственному корню монотонной функции при a ? 0. При этом постоянная y0 выбирается так, чтобы удовлетворялось изопериметрическое ограничение (15). Следовательно, t0 = T - T0 при a > 0 и t0 = T0 при a < 0. Если, наконец, a = 0, то критерий качества D(T ) не зависит от конкретного вида функции Q(T ), удовлетворяющей условию (15), и для любой из них равен Выпишем еще выражения для минимального значения D(T ) при a ? 0 и оптимальном законе наблюдения. Имеем
Полученное решение допускает наглядную интерпретацию. При a > 0 энергия сигнала x возрастает с ростом времени t и поэтому наблюдения выгодно производить в конце. Если же a < 0, то энергия сигнала, напротив, убывает с ростом t и наблюдения целесообразно проводить вначале. Наконец, при a = 0 энергия сигнала постоянна, то есть конкретный выбор моментов проведения наблюдений несуществен.
ЗАКЛЮЧЕНИЕ
В статье даны постановки некоторых задач теории оптимального оценивания и методы их решения.
Многочисленным практическим приложениям этой теории посвящены многие работы, обзоры и книги, библиография которых частично отражена в [1-7].
ЛИТЕРАТУРА
1. Колмогоров А.Н. Интерполирование и экстраполирование стационарных случайных последовательностей // Изв. АН СССР. Сер. мат. 1941. Т. 5, ╧ 1. С. 3-14.
2. Wiener N. Extrapolation, Interpolation and Smoothing of Stationary Time Series. N.Y.: Wiley, 1949.
3. Винер Н. Я - математик. М.: Наука, 1964.
4. Калман Р., Бьюси Р. Новые результаты в линейной фильтрации и теории предсказания // Техн. механика. Сер. Д. 1961. Т. 83, ╧ 1.
5. Браммер К., Зиффлинг Г. Фильтр Калмана-Бьюси. М.: Наука, 1982.
6. Липцер Р.Ш., Ширяев А.Н. Статистика случайных процессов. М.: Наука, 1974.
7. Черноусько Ф.Л., Колмановский В.Б. Оптимальное управление при случайных возмущениях. М.: Наука, 1978.
8. Колмановский В. Б. Задачи оптимального управления // Соросовский Образовательный Журнал. 1997. ╧ 6. С. 121-127.
* * *
Владимир Борисович Колмановский, доктор физико-математических наук, профессор Московского института электроники и математики. Область научных интересов - функционально-дифференциальные уравнения, теория устойчивости и управления. Автор более 100 научных статей и десяти монографий.
