Автоматика и телемеханика, № 5, 2015
© 2015 г. П.А. АКИМОВ, канд. физ.-мат. наук (akmpavel@rambler.ru), А.И. МАТАСОВ, д-р физ.-мат. наук (alexander.matasov@gmail.com) (Московский государственный университет им. М.В. Ломоносова)
ИТЕРАЦИОННЫЙ АЛГОРИТМ ДЛЯ ^-АППРОКСИМАЦИИ В ДИНАМИЧЕСКИХ ЗАДАЧАХ ОЦЕНИВАНИЯ1
Рассматривается подход к оцениванию векторов состояния динамических систем, состоящий в решении проблемы ¿1-аппроксимации. Предложен алгоритм решения данной задачи - метод весовой и временной рекурсий, который сочетает в себе идеи вариационно-взвешенных квадрати-ческих приближений и сглаживающего фильтра Калмана. Для итераций метода построены оценки уровней неоптимальности, что является развитием предыдущих результатов, полученных авторами для классического метода наименьших модулей.
1. Введение
Известно, что ¿1-аппроксимация [1, 2] оказывается весьма эффективным и методически ясным подходом к обработке измерительной информации с аномально большими ошибками (сбоями), а также в случае, когда некоторые компоненты вектора состояния динамической системы могут меняться скачкообразно [2-5]. В статье предлагается метод численного решения задач
¿1-аппроксимации для динамических систем при длительных интервалах из-
« 2
мерений .
В предыдущих работах авторов для решения таких проблем использовались методы, состоящие в сведении динамических задач оценивания к статическим с вектором неизвестных параметров большой размерности [5, 7]. Представленный ниже алгоритм существенно использует динамическую структуру задач оценивания, что позволяет избежать критической зависимости от длительности процесса измерений. Метод основан на последовательном решении квадратичных проблем оптимизации со специальным подбором весовых коэффициентов. Применительно к статическим задачам оценивания аналогичный подход давно используется на практике, его называют алгоритмом вариационно-взвешенных квадратических приближений (алгоритмом Вейс-фельда) [8, 9]. Однако для динамических задач он может быть усовершенствован путем использования рекуррентных соотношений между оценками фазовых векторов системы в различные моменты времени, что позволяет существенно повысить вычислительную эффективность процедур.
Важный аспект, связанный с итерационными алгоритмами решения, состоит в необходимости оценки качества получаемого на текущей итерации
1 Работа выполнена при финансовой поддержке Российского Фонда Фундаментальных Исследований (проект № 11-08-00004a).
2 Данная статья является переработанной и расширенной версией доклада [6].
приближенного решения исходной задачи. Ниже будет получена оценка уровня неоптимальности текущей итерации соответствующего алгоритма, также учитывающая динамический характер проблемы.
2. Задачи аппроксимации
2.1. Проблема 1\-аппроксимации в динамическом случае
Рассмотрим динамическую систему, описывающуюся дискретной моделью
х(к + 1) = ^ж(к) + С д(Л) + #(к), к = 0,..., К - 1,
где ж(к) € Кп - неизвестный вектор состояния системы в момент времени к, д(к) € К1 - неизвестный вектор погрешностей, ^ € Кгахга, С € Кпх1 - заданные матрицы, д(к) € Кп - известный вектор, отвечающий неоднородностям данной системы. Здесь для простоты будем полагать, что матрицы ^ и С постоянны. Все описываемые далее методы применимы и для случая переменных ^ и С.
Пусть также имеется априорная информация Х(0) о начальном состоянии системы:
Х(0) = х(0) + Г(0), Х(0),Г(0) € Кп.
В каждый момент времени производятся измерения, линейно связанные с компонентами вектора состояния системы:
г(к) = Нх(к) + т(к), к = 0, ...,К.
Здесь ¿(к) € Кт — вектор измерений, соответствующий моменту к, Н € € ктхп — заданная матрица, т(к) € Кт — погрешность измерений.
Характерные значения шумов в измерениях, погрешностей в динамике и априорной информации считаются известными и задаются положительными величинами К, Qj,Ц соответственно:
т, (к) ~ Кj, з = 1,..., т, к = 0, ...,К;
qj (к) ~ Qj, з = 1,...,1, к = 0, ...,К - 1; Г (0) - Ц, з = 1,...,п.
Кроме того, будем полагать, что в редкие моменты времени погрешности измерений могут допускать аномально большие значения, превышающие Ц, К , Qj, а погрешности в динамике могут приводить к скачкообразным изменениям компонент фазового вектора. При этом каких-либо предположений о вероятностных свойствах шумов делать не будем.
Необходимо оценить значения векторов состояния ж(к) на всем интервале времени к = 0, . . . , К. По аналогии с применяемым в статических проблемах методом наименьших модулей [2, 8] эти оценки будем искать как решение
вариационной задачи 11-аппроксимации3 :
I(x,q) = |n-1(X(Q) - x(Q))|^ +
(1) K—1 K
+ J2 I|Q—1q(k)|1 + ^ ||R—1(z(k) - Hx(fc))|1 ^ inf k=0 k=0
при ограничениях
(2) x(k + 1) - Fx(k) - Gq(k) - g(k) = 0, k = Q,...,K - 1.
Здесь введены краткие обозначения для неизвестных векторов в описанной системе
(x, q) = (x(0),..., x(K ), q(Q), ...,q(K - 1)), и для весовых матриц
П-1 = diag (П—1,..., П—1) , Q—1 = diag (Q—1,..., Q—1) , R—1 = diag (R—1,...,Rm1) •
Таким образом, необходимо минимизировать сумму ¿1-норм векторов невязок, соответствующих погрешностям начальной информации, динамической модели и измерений. Ясно, что проблему (1), (2) можно трактовать как задачу метода наименьших модулей в динамическом случае. С математической точки зрения, эта задача состоит в поиске минимума негладкой функции при линейных ограничениях — равенствах.
Наиболее простые методы решения задач вида (1), (2) состоят в сведении к эквивалентным проблемам линейного программирования (ЛП) с дополнительными к (2) ограничениями-неравенствами [3]. Недостаток такого подхода заключается в том, что он требует больших вычислительных ресурсов при обработке результатов длительных измерений, поскольку в этом случае матрица, задающая ограничения-неравенства, достигает большой размерности, пропорциональной количеству негладких слагаемых в функционале исходной задачи
Существенным шагом вперед в решении проблем оптимизации большой размерности является так называемый ADMM — Alternating Direction Method of Multipliers [10]. Этот метод представляет собой итерационный поиск минимума функции Лагранжа для исходной проблемы, при котором параллельно решаются задачи с переменными меньшей размерности. Применительно к динамическим проблемам оценивания ADMM позволяет по отдельности оценивать фазовые векторы в разные моменты времени. Однако один из шагов ADMM все равно требует решения вспомогательных квадратичных задач, по количеству переменных сопоставимых с исходной проблемой. Для некоторых простых случаев это препятствие можно преодолеть, однако для линейных динамических систем общей структуры использование ADMM напрямую не позволяет произвести декомпозицию исходной негладкой проблемы.
3 Здесь и далее, как обычно, ||x||i = |xi|, ||x||œ = ma xi {|xi|}, ||x||2 = ®2)1/2-
В связи с этим, возникает необходимость в разработке простых по структуре методов, существенно использующих динамический характер проблем оценивания и позволяющих избежать сведения их к статическим проблемам.
2.2. Необходимые сведения из теории квадратичных .задач сглаживания
Предлагаемый в разделе 3 алгоритм решения проблемы (1), (2) опирается на более распространенную квадратическую задачу сглаживания [11]:
/ к-1
з (ж^) = ||п-1(х(0) - ®(0))||2 + ^ 1ЮЛ(к)||2 + V к=0
(3)
К \ 2
+ £ ||К-1(г(к) - Нж(к))||2) ^ М
к=0
при тех же ограничениях (2).
Напомним рекуррентные соотношения, определяющие решение задачи (3), (2).
Утверждение 1 [11]. Пусть (ж*т(0),..., ж*т(К), q*т(0),..., q*T(K -- 1))т — решение проблемы (3), (2). Тогда оно описывается следующей краевой задачей:
ж* (к + 1) = #к*(к) + GQ2GTAJ (к + 1) + #(к), (4) q*(k) = Q2СTAJ(к + 1), к = 0,...,К - 1,
AJ(к) = ^^(к + 1) + Н^-2^) - Нж*(к)), к = К,..., 0,
при краевых условиях АJ(К + 1) = 0, ж*(0) = ж(0) + П2AJ(0).
Строго говоря, в книге [11] утверждение 1 доказано для случая ж(0) = 0, $(к) = 0. Однако нетрудно убедиться, что утверждение 1 непосредственно следует из результатов [11]. Для этого нужно перейти к центрированному процессу ж(к) = ж(к) - ж(к), где векторы ж(к) известны и описываются рекуррентными формулами ж(к + 1) = ^ж(к) + $(к), к = 0,..., К - 1, с известным начальным условием ж(0).
В силу задания граничных условий на разных концах, формулы (4) не удобны для непосредственного решения проблемы (3), (2). Для преодоления этой трудности можно использовать, например, формулы Брайсона-Фрейзе-ра, которые представлены в следующем утверждении.
Утверждение 2 [11]. Решение проблемы (3), (2) (ж*^),...,ж^К), q*т(0),..., q*T(K -1)^ определяется формулами
ж*(з) = ж-(з) + Р-(j)AJ(з), з = 0,..., К, q*(j) = Q2СT AJ (з + 1), з = 0,...,К -1,
где х (?) — оценки фазовых векторов, доставляемые фильтром Калмана:
х-? +1) = Рх-?) + кРс?) (¿с?) - Ях-?)) + £(,?), х-(о) = х(о),
р-(? +1) = рр- (,?)РТ+сд2сТ -Кр(?)(е2+яр-(?)ЯТ)КРТ(?), р-(0)=п2,
Кр(?) = РР-(?) Ят (Е2 + ЯР-(?)ЯТ)-1, ? = 0,...,К - 1,
а AJ(?) — векторы, вычисляемые из рекуррентных соотношений в "обратном" времени:
А^(?) = (Р - КР(?)Я)т AJ(? + 1) + Ят (Е2 + ЯР-(?)ЯТ)-1 (¿(?) - Ях-(?)),
AJ(К + 1) = 0, ? = К,..., 0.
Формулы Брайсона-Фрейзера позволяют в два прохода по массиву обрабатываемых измерений найти решение квадратичной задачи сглаживания. При первом проходе строятся оценки согласно фильтру Калмана, при втором проходе — слагаемые AJ(?). В итоге результирующая оценка учитывает для каждого момента времени ? информацию, соответствующую всему интервалу времени измерений.
3. Метод весовой и временной рекурсий
Предложим метод численного решения проблемы ^-аппроксимации (1), (2). Речь пойдет о модификации алгоритма Вейсфельда (алгоритма вариационно-взвешенных квадратических приближений), использование которого в методе наименьших модулей описано, например, в [5, 8]. Отличие состоит в том, каким образом на каждой итерации этого алгоритма будут решаться задачи ¿2-аппроксимации.
Пусть (х(0), д(0)) = {х(к, 0), д?, 0)}к=°'"''К-1 — набор векторов, являющийся допустимым для задачи (1), (2), т.е. удовлетворяющий равенствам (2). В этих обозначениях первый аргумент в скобках к — мо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.