Диссертация (1150919), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Далее рассмотрим один из возможных способовнахождения матрицы Gt , минимизирующей функционал (2.16).522.2Оптимизация распределения объектовмежду наблюдателями на основерешения системы линейных матричныхнеравенствДля нахождения решения функционала качества вида (2.16) воспользуемся техникой линейных матричных неравенств. В [45] рассматривается субоптимальный метод нахождения минимального по объему эллипсоида E i , аппроксимирующего множество пересечения эллипсоидовE i,1 , . . . , E i,n , основанный на идее нахождения аналитического центра.Предположим, что эллипсоиды {E i,j }j∈N представлены в форме (2.14)и матрица Ri,j = (Ri,j )T , тогда линейное матричное неравенство будетвыглядитеть следующим образом"F i (x) = diag"(2.17)...,I(x − xi,1 )T (Ri,1 )−1I(x − xi,n )T (Ri,n )−1#(R ) (x − x ),...1i,1 −1i,1#!(R ) (x − x )> 0.1i,n −1i,nПредполагается, что для любого i множество пересеченияnTE i,j неj=1iпусто и не является точкой.

Обозначим через x̃ аналитический центрмножества пересечения(2.18)x̃i = argmin log det F i (x)−1F i (x)>0и через H i гессиан функции log det F i (x)−1 в точке x̃i . Тогда эллипсоид,53аппроксимирующий множество пересечения, примет вид:(2.19)iνi TiiE = {x ∈ R : (x − x̃ ) H (x − x̃ ) ≤ 1} ⊆n\E i,j .j=1В [45] также приводится оценка того, насколько плохо эллипсоид E iаппроксимирует пересечение, а именно(2.20)νi Tii2{x ∈ R : (x − x̃ ) H (x − x̃ ) ≤ (3n + 1) } ⊇n\E i,j .j=1Приведенная оценка означает, что в том случае, когда эллипсоид E i увеличен в 3n + 1 раз, он полностью покрывает множество пересеченияnTE i,j .j=1Решение проблемы (2.18) при LMI-ограничениях вида (2.17) дает эллипсоид, аппроксимирующий множество пересечений всех n эллипсоидов.

Для решения задачи в виде (2.14) необходимо добавить возможностьоптимизации распределения объектов слежения между наблюдателями.Для этого рассмотрим вектор-строку gti = (gti,1 , . . . , gti,n ) и матрицу Gt ,состоящую из множества векторов {gti }i∈M . Напомним, что в соответствии с поставленной задачей (2.14) необходимо отыскать матрицу Gt .TПусть x̃t = (x1t , . . .

, xmt ) , тогда задача (2.18) примет вид(2.21)x̃t =argminδFt1 (x1t )>0,...,Ftm (xmt )>0, Gtпри LMI-ограничениях∀i gti,1 ≥ 0, . . . , qti,n ≥ 0,"∀i Fti (xit ) = diag gti,1#I(Rti,1 )−1 (x − xi,1)t,...i,1 Ti,1 −1(x − xt ) (Rt )154"(2.22). . . , gti,nXi∈M(Rti,n )−1 (xI(x −i,n −1Txi,nt ) (Rt )log det Fti (xit )−1 + αXkGi,·t k1 + βi∈M−1X#!xi,nt )> 0,kG·,jt k1 ≤ δ,j∈Nгде α, β — коэффициенты допустимых потерь.С учетом вышеизложенного, сформулируем следующую теорему. Обозначим увеличенные в kti раз эллипсоиды через Ēti , а также отметим, чтопараметры используемых эллипсоидов при решении задачи зависят отмомента времени t.Т е о р е м а 2.

Пусть проблема (2.21) при LMI-ограничениях вида(2.22) разрешима, функционал (2.14) принимает оптимальное значениепри G∗t и количество наблюдателей, назначенных для объекта i, равноnit = kGi,·t k0 .Если матрица G∗t удовлетворяет ограничениям (2.8)-(2.9), тогда векторы истинных значений параметров rti с вероятностью не менее 1 −(nit + 1)p принадлежат эллипсоидaм Ēti , получающееся при этом значение функционала Φ(G∗t ) не более чем в γt раз превышает минимальновозможное значение, т. е. субоптимально с уровнем субоптимальности γt .Доказательство.

Наряду с матрицей G∗t решением проблемы (2.21) является множество эллипсоидов {Eti }i∈M вида (2.19), т. е. вписанных вiмножества пересечений эллипсоидов Eti,1 , . . . , Eti,n и при этом обладающих наибольшим объемом. По введенному ранее определению доверительного эллипсоида, векторы истинных параметров rti с вероятностьюне менее чем 1 − (nit + 1)p принадлежат множествам пересечений элi,niлипсоидов Eti,1 , . . .

, Et t . Так как эллипсоиды {Eti }i∈M и параметры rtiпринадлежат одному и тому же множеству, то параметры rti принадлежат эллипсоидам {Eti }i∈M с вероятностью не менее чем 1 − (nit + 1)p, аследовательно и их увеличенным в k i раз аналогам.55Рассмотрим подробнее функционал (2.14). Второе и третье слагаемое ввиду разрешимости проблемы (2.21) при LMI-ограничениях вида(2.22) имеют минимально возможное значение, следовательно на увеличение значения функционала Φ(G∗t ) влияет только увеличение объемов эллипсоидов.

Объем увеличенного эллипсоида вида (2.20) равенpcν det(kti )2 Hti , Hti ∈ Rν×ν . По свойству определителя матрицы det λH =λν det H для H ∈ Rν×ν , получаем, что γti = (kti )ν , γt = maxi γti .2.3Оценивание состояний движущихсяобъектовРассмотрим гибридную сеть наблюдателей, состоящую из централизованного узла, на котором производится процедура оптимизации распределения объектов между наблюдателями, и распределенных в пространстве наблюдателей (сенсоров), осуществляющих мультиагентное оценивание траекторий. Предположим, что субоптимальное решение задачиоптимизации распределения объектов между наблюдателями не меняется на некотором (не очень малом) интервале времени, т. е.

достаточнодолго субоптимальная структура матрицы G∗t остается неизменной. Если решение удовлетворяет ограничениям (2.8)-(2.9), то для оцениваниясостояний движущихся объектов можно воспользоваться процедурой поисковой стохастической аппроксимации, рассмотренной в [38]. В противном случае, для удовлетворяния ограничений предлагается использование циклического алгоритма поисковой стохастической аппроксимации,описанного далее.2.3.1Циклический подходРазобьем временнýю ось на последовательность циклов длиной 2k:2(T − 1)k + 1, 2(T − 1)k + 2, .

. . , 2T k, и на каждом из циклов разобьеммножество индексов D = {1, . . . , d} на k непересекающихся подмножеств56Iu , u = 1, . . . , k, выделяющих набор активных параметров в моментывремени t = 2(T − 1)k + 2u − 1 и t = 2(T − 1)k + 2u, u = 1, . . . , k, иудовлетворяющих условиям(2.23)k[Iu = D,Iu0\Iu00 = ∅ при u0 6= u00 .u=1При каждом t = 1, 2, . . . определим диагональные матрицы At , формирующие по вектору xt разреженный вектор At xt с нулями на тех местах,индексы которых не принадлежат I(t mod (2k))÷2 , где mod — операция взятия остатка от деления, ÷ — операция деления нацело. По циклическойпоследовательности матриц {At } определим многочленA(λ) =kXA2kT +2u λu ,u=1которым в дальнейшем будет удобно пользоваться вместе с операциейсдвига индекса λθ t = θ t−2k+2 .С учетом введенных обозначений получаемые наблюдения y1 , y2 ,y3 , .

. . можно представить в видеyt = fwt (At xt ) + vt .Для отслеживания изменений θ t воспользуемся рандомизированнымалгоритмом стохастической аппроксимации из [38] и модифицируем егоb0 ∈ Rd — неслучайный начальна основе циклического подхода. Пусть θный вектор, ∆T , T = 0, 1, . . . , — наблюдаемая последовательность бернуллиевских случайных векторов из Rd−l , принимающих значения ±1 сравными вероятностями 21 , называемых рандомизирующими пробнымивозмущениями.bt } рассмотримДля построения точек наблюдений {xt } и оценок {θциклический поисковой алгоритм стохастической аппроксимации с дву-57мя наблюдениями и линейными ограничениями:bt−1 ) − β − ∆t÷2 )),x2((t−1)÷2)+1 = g2((t−1)÷2)+1 (At (h(θx+b2(t÷2) = g2(t÷2) (At (h(θ t−1 ) + β ∆t÷2 )),(2.24)b2((t−1)÷2)+1 = g2((t−1)÷2)+1 (h(θb2((t−1)÷2) )),θθb2(t÷2) = g2(t÷2) (h(θb2((t−1)÷2)+1 ) − αAt ∆T y2T −y2T −1 ),βгде α > 0 — постоянный размер шага, β + ≥ 0 и β − ≥ 0 такие, чтоβ = β + + β − > 0.2.3.2Верхняя граница среднеквадратическойошибки оценивания по циклическомуалгоритмуСформулируем основные предположения о возмущениях и функцияхf¯w (x), F̄t (x).П р е д п о л о ж е н и е 1.

Для точек минимума θ t функций F̄t (·)и векторов-градиентов функций f˜(At x) = f¯wt (gt (At x)) выполняютсянеравенства2˜∀x ∈ Rd (x − h(θ t ))T ATt EFt−1 ∇fwt (At x) ≥ µkAt (x − h(θ t ))kс некоторой постоянной µ > 0.П р е д п о л о ж е н и е 2. ∀w ∈ W градиент ∇f˜wt (At x) удовлетворяет условию Липшица: ∀x0 , x00 ∈ Rdk∇f˜wt (At x0 ) − f˜wt (At x00 )k ≤ M kAt (x0 − x00 )kс константой M ≥ µ.П р е д п о л о ж е н и е 3. Вектор-градиент ∇f˜wt (At x) равномерноограничен в точках минимума θ t : kE∇f¯wt (At h(θ t ))k ≤ c1 ,58Ek∇f¯wt (At h(θ t ))k2 ≤ c2 , E(∇f¯wt (At h(θ t )))T ∇f¯wt−1 (At h(θ t−1 )) ≤ c2 (c1 =c2 = 0, если последовательность wt неслучайная, т.е.

f¯wt (x) = F̄t (x)).П р е д п о л о ж е н и е 4. Дрейф ограниченный: для η t = At (h(θ t −θ t−1 )) выполняется kη t k ≤ δθ < ∞ или Ekη t k2 ≤ δθ2 и Ekη t kkη t−1 k ≤ δθ2 ,если последовательность {wt } случайная.П р е д п о л о ж е н и е 5. Скорость дрейфа ограничена такимобразом, что ∀x ∈ Rd : EFt−2 (f˜wt (At θ t ) − f˜wt−1 (At θ t−1 ))2 ≤ c3 kAt (x −h(θ t−2 ))k + c4 .П р е д п о л о ж е н и е 6. Последовательные разности помехнаблюдения ограничены: |v2t − v2t−1 | ≤ cv < ∞ или E(v2t − v2t−1 )2 ≤ c2v ,если последовательность {vt } случайная.П р е д п о л о ж е н и е 7.

Для T = 0, 1, . . ., если vt случайные, тогдавектор ∆T и разности помех v2kT +2 − v2kT +1 , . . . , v2k(T +1) − v2k(T +1)−1независимые; если wt случайные, тогда вектор ∆T и w2kT +1 , . . . ,w2k(T +1) независимы.Распространим результат Теоремы 1 из [38] на рассматриваемый случай и сформулируем теорему для оценок, формируемых каждым сенсором.Т е о р е м а 3. Если выполнены предположения 1–7 и2 (0; если µ > 2γ; µ/γ),√ 2 √ 2α∈ 0; µ− 2γµ −2γ ∪ µ+ 2γµ −2γ ; µ/γ , в противном случае,b2kT }∞ , построенная по алгориттогда последовательность оценок {θT =0му (2.24), при разбиении временной оси по (2.23) дает асимптотическую верхнюю границу среднеквадратической невязки: ∀ε > 0 ∃ t̄ : ∀t > t̄(2.25)√√q2 + mlkb+bbt − A(λ)θ t )k2 ≤Ekh(θ+ ε,m59√m = 2(µ − αγ), b = 2βM d d(1 + 6αM d) +√ 2 c22 224δθ (M + 2µ + 6αM d ), ¯l = 2αd cv + 3( β + d(c2 + M (δθ + 2β d) )) +√√22δθ (4βM d d + M δθ + c1 + 3µδθ2 ), l = ¯l + 2bk kδθ + 1−αmα δθ .где: γ = 3d(M 2 d +c3β ),Доказательство.

Рассмотрим следующую вспомогательную лемму из [56].Л е м м а 3. Если en > 0, α, m > 0, αm < 1, b, ¯l ≥ 0 и√en ≤ (1 − α m) en−1 + 2α b en−1 + α ¯l, n = 1, 2, . . . ,тогда для любого ε > 0 существует такое N , что ∀n > Nen ≤b+√b2!2¯+ mlm+ ε.Доказательство Леммы 3 представлено в [8].Пусть T = 0, 1, . .

Характеристики

Список файлов диссертации