автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмы оценивания моделей нестационарных сигналов при наличии ограничений

ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Красоткина Ольга Вячеславовна

АЛГОРИТМЫ ОЦЕНИВАНИЯ МОДЕЛЕЙ НЕСТАЦИОНАРНЫХ СИГНАЛОВ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

Специальность 05.13.17 -Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Тула 2003

Работа выполнена в Тульском государственном университете на кафедре автоматики и телемеханики

Научный руководитель

доктор технических наук, профессор В.В. Мотгль

(Научный совет по комплексной проблеме кибернетики)

Официальные оппоненты

доктор технических наук, профессор Л.М. Местецкий кандидат физико-математических наук К.В. Воронцов

Ведущая организация

Институт проблем управления РАН

2003 г. в ^ У

Защита диссертации состоится <</•<>> _ _ 2003 г. в ' ч. на заседании

диссертационного совета Д 002.017.02 в Вычислительном центре им. A.A. Дородницына РАН по адресу; 119991, г. Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

н

Автореферат разослан як 7» \s ° 2003 г.

Ученый секретарь

диссертационного совета

доктор физико-математических наук

Л

' В-В- Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ ктуальность работы. Для практики технических и естественно-научных иссле-аний типична необходимость обработки массивов данных, упорядоченных вдоль одного дискретного ар1-умента - времени, частоты, пространственной координа-В качестве обобщающего назвапия для данных такого вида обычно используется чин «сигналы» в несколько более расширительном смысле, нежели его изна-ьное значение в теории связи, подразумевающее лишь функции времени, адачу анализа предъявленного массива данных, в данном случае сигнала, прак-ески всегда можно понимать как задачу выбора его модели из некоторого класса ;елей. Универсальный подход к оцениванию моделей массивов данных, в частно-модслей сигналов, дает вариационный принцип, заключающийся в поиске моде-лз заданного семейства путем минимизации подходящего критерия несоответст-между массивом и моделью, причем большинству прикладных задач адекватен :с квадратичных целевых функций.

[рнмснитсльно к сигналам, естественно различать стационарные модели, перс->щие общую форму предъявленного сигнала в пределах всей области определе-, и нестационарные модели, призванные отражать изменение некоторого локаль-

0 свойства сигнала вдоль его оси, обычно дискретной. В данной работе исследу-

1 проблема построения именно нестационарных моделей сигналов, которые слег искать в виде последовательности локальных моделей либо значений изме-лцегося параметра некоторой общей локальной модели в каждой точке оси сига.

стественно, что оценить мгновенную локальную модель нестационарного сигна-ю его отдельному значению принципиально невозможно, поэтому оценивание гационарной модели неизбежно должно быть основано на привлечении некото-априорной информации. В качестве такой информации естественно принять дтголожснне, что локальная модель изменяется в основном достаточно плавно, что смежные локальные модели скорее всего близки друг к другу, за исключе-м, быть может, относительно редких скачков.

'роме того; специфика решаемой прикладной задачи, как правило, накладывает ;ствешгые ограничения на искомую последовательность локальных моделей, ко-ые часто имеют вид линейных равенств и неравенств. В результате задача оцени-ия нестационарной модели сигнала естественным образом формализуется как за-а минимизации квадратичной парно-сепарабельной целевой функции, представ->щей собой сумму частных квадратичных целевых функций, каждая из которых юит лишь от двух смежных переменных с линейными шраничениями, наложен-т на каждую локальную переменную в отдельности.

(одобного рода задачу будем называть задачей парно-сепарабельного квадратич-о программирования в отличие от общей классической задачи квадратичного граммирования, в которой все переменные предполагаются связанными друг с гом и входящими в общую систему ограничений.

[роблемная ситуация состоит в том, что все существующие методы решения iч квадратичного программирования имеют полиномиальную вычислительную жность о'гносительно числа векторных переменных, т.е. длины сигнала. Это за-цпяст построение эффективных в вычислительном, отношении алгоритмов ана-з сигналов, как специального вида протяженных массивов данных, имеющих, правило, трудноиредсказуемый размер. Последнее обстоятельство делает крайне

нежелательным превышение вычислительной сложности алгоритмов анализа сигналов над линейной сложностью. '''

Другая проблемная ситуация состоит в том, что классическая процедура решении задачи квадратичного программирования определяет' оптимальные значения всех переменных одновременно. В то же время существует обширный класс вариационных задач анализа сигналов, решение которых связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента мри разных моделях сигнала без пересчета оптимальных значений в других точках. Примерами таких задач являются задачи сглаживания сигналов с сохранением локальных особенностей и верификации нестационарной модели путем последовательного сравнения экспериментального значения каждого элемента сигнала с его предсказанным значением по модели, построенной без участия этого элемента (метод скользящего контроля). Эффективные алгоритмы решения задач такого типа не мемуг быть построены в рамках классической схемы квадратичного программирования.

Для разрешения этого противоречия в данной работе систематически используется тот факт, что адекватным инструментом решения задач оптимизации с парно-сепарабельными целевыми функциями, имеющими последовательную смежность неременных, являйся метод динамического программирования, обладающий линейной вычислительной сложностью относительно числа переменных, т.е. длинны анализируемого сигнала. В то же время трудность реализации этого преимущества заключается в том, что применение метода динамического программирования для минимизации парно-сепарабельных целевых функций с непрерывными переменными при наличии ограничений в виде неравенств приводит к необходимости вычисления и запоминания промежуточных функций (функций Беллмана), не выражаемых через элементарные функции.

Цель работы. Целью диссертационной работы является разработка алгоритмов оценивания моделей нестационарных сигналов путем решения соответствующих задач оптимизации при наличии ограничений на основе метода динамического программирования, обеспечивающих линейную вычислительную сложность и независимое определение оптимальных значений отдельных переменных, а также применение ■ разработанных методов для решения прикладных задач анализа сигналов.

Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:

1 .Формальная постановка класса задач оценивания нестационарной модели сигнала как задач парно-сепарабельного квадратичного программирования., . ■•„

2.Разработка асимптотически точного итерационного алгоритма решения задачи парно-сепарабельного квадратичного программирования, учитывающего специфику целевой функции и обеспечивающего линейную вычислительную сложность алгоритма оценивания нестационарной модели сигнала относительно его длины.1

3.Разработка неитерационного алгоритма решения задачи парно-сепарабельного квадратичного программирования, на основе приближенной реализация процедуры динамического программирования, обеспечивающего неитерационное оценивание нестационарной модели сигнала. ■

4.Создание альтернативной версии приближенной процедуры динамического программирования для оптимизации сепарабельных целевых функций с индивидуальными ограничениями на переменные, обеспечивающей независимое определение оптимальных значений отдельных целевых переменных.

.Создание методов верификации нестационарной модели сигнала на основе принципа скользящего контроля.

.Применение разработанных процедур для решения практических задач анализа данных.

Методы исследования базируются на использовании методов динамического юграммирования и квадратичной оптимизации.

Положения, составляющие научную новизну и выносимые па защиту.

1. Концепция парно-сепарабельной квадратичной целевой функции с последовательной смежностью векторных переменных и индивидуальными линейными ограничениями на переменные как критерия оценивания нестационарной модели сигнала.

2.Асимптотически точный итерационный метод оценивания нестационарной модели сигнала путем решения соответствующей задачи парно-сепарабельного квадратичного программирования, основанный на методе наискорейшего спуска, использующий на каждой итерации метод динамического программирования и имеющий линейную вычислительную сложность относительно числа векторных переменных.

3.Концепция квадратичной аппроксимации неквадратичной функции Беллмана как основного принципа приближенного неитерационного решения задачи пар-но-сепарабельного квадратичного программирования.

Неитерационный алгоритм оценивания нестационарной модели путем приближенного решения соответствующей задачи парно-сепарабельного квадратичного программирования на основе процедуры динамического программирования. 5. Применение приближенной процедуры динамического программирования для оценивания параметров нестационарной модели сигнала с сохранением его локальных особенностей при наличии ограничений в виде неравенств на параметры модели.

5. Применение приближенной процедуры динамического программирования для определения требуемой степени сглаживания при оценивании нестационарной модели сигнала с ограничениями на параметры модели.

Достоверность получепных результатов подтверждается доказанными мате-ггическими утверждениями и модельными экспериментами.

Практическая значимость. Разработанные концепции и методы позволяют роить линейные по вычислительной сложности алгоритмы решения широкого [асса прикладных задач анализа нестационарных сигналов.

Связь с плановыми научными исследованиями. Работа выполнена при гтод-ржке Государственной научно-технической программы РФ «Перспективные ин-)рмационньге технологии», гранта Российского фонда фундаментальных исследо-ний.

Реализация и внедрение результатов работы. Результаты исследования при-;ненЬг дм создання новой методики анализа данных.

Апробация работы. Основные положения и результаты диссертации доклады-лись на V я VI международных конференциях «Распознавание образов и анализ ображений: новые информационные технолог ии» (Самара, 2000 г., Великий Нов-род, 2002 г.). на X всероссийской конференции «Математические методы расно-авания образов» (Москва, 2001 г.) и на Международной конференции «Обработка гналов, распознавание образов и приложения» (Родос, Греция, 2003 г.). •

Публикации. По тематике исследований опубликовано 6 статей из них 3 на русском языке.

Структура и объем работы. Диссертация состоит из введения, шести глав, основных выводов, списка литературы и приложений. Материал изложен на 124 страницах, содержит 10 рисунка, список литературы из 69 наименований. , . •.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приведены примеры прикладных задач анализа сигналов, сформулированы цели и задачи проводимых исследований, положения, выносимые на защиту, приведены сведения о структуре диссертации, ее апробации.

В первой главе рассматривается задача оценивания нестационарной регрессии, адекватная многим приложениям. Предполагается, что подлежащий анализу векторный сигнал У = ((у,0.У,), I = 1.....Ы) состоит из двух частей - векторной последовательности у, е Я" и числовой последовательности у° е В. Основное модельное предположение заключается в том, что векторная компонента у, зарегистрирована как проявление некоторого внешнего процесса, свойства которого не - изучаются, а числовая компонента у° в каждой точке наблюдения получена как зашумленная линейная функция векторной компоненты

.у,°=хГу,+$„ (1)

определяемая последовательностью неизвестных векторных коэффициентов регрессии х, е И". Задача заключается в оценивании последовательности коэффициентов регрессии X = (х,, ! = 1,...,Л0 в предположении, что они изменяются в основном достаточно медленно, 1третерпевая, быть может, относи тельно редкие скачки. Что касается шума наблюдения , то он рассматривается как относящийся к тому типу, который в теории случайных процессов называют белым шумом с неизвестной интенсивностью. Далее в первой главе показано, что во многих задачах анализа нестационарных сигналов возникают ситуации, когда на последовательность искомых параметров модели X =(х,, / = 1,...,//) накладываются некоторые ограничения в виде равенств и неравенств, конкретный вид которых зависит от природы рассматриваемой задачи.

В частности, одной из типовых задач анализа сигналов является задача сглаживания. Исходный сигнал у, рассматривается как сумма у, = х, + !;, скрытого сигнала х,, который необходимо восстановить, и адаптивного шума с нулевым средним. Целью обработки исходного сига ала у, является подавление шума, т.е. восстановление скрытого сигнала х, и, вообще говоря, я-1 его разностей ^'х^—У^'х,. Тогда, если обозначить через х, = (.г',...,.г°)г е й" вектор мгновенных значений искомых переменных, образованных самим подлежащим восстановлению сигналом и его разностями = х,, .г; = Ух, = .*,' -х),, х} =У:дг, = х,2 - х;......х" =У" 'х, =х" ' -х"', и ввести в рассмотрение вектор у, = (1,0,...,0)г е И", то получим модель нестационарной регрессии (1). Очень часто в прикладных задачах имеются априорные предположения о характере изменения скрытого сигнала х,. Например, в финансовых приложениях, искомая переменная имеет смысл некоторого экономического показателя, такого как, например, валовый национальный продукт, уровень безработицы и т.д. и как следствие она должна быть монотонна или (и) неотрицательна. Это приводит к дополнительным ограничениям на вектор мгновенных значений переменных х,:' л-,1 > 0 в случае неотрицательности и х; >0 в случае монотонности.

Модель нестационарной регрессии (1) адекватна также задачам авторегрессион-ого и спектрально-временного анализа сигналов. Пусть анализируемый сигнал у, ассматривается как реализация случайного процесса нестационарной авторегрес-ии, отличающегося от (1) тем, что у, =(>,_,-■• у,понимается как вектор, со-гавленный из прошлых значений сигнала, а векторная последовательность , =(а,г"дт)г 6 есть искомая последовательность изменяющихся во времени ко-ффициентов авторегрессии. Вместе с последовательностью коэффициентов а, те-ущая дисперсия шума , определяет изменяющуюся во времени дисперсию £>, на-людаемого случайного процесса у, в целом, также подлежащую оцениванию. Поскольку последовательность векторов коэффициентов авторегрессии а, и зна-ений текущей дисперсии Д нестационарного случайного процесса полностью оп-сдсляст его изменяющуюся во времени спектральную плотность 5,(/) = 5'(/; а,,£>,) интервале частот Котельникова 0</<1/2, то результат авторегрессионного ана-иза сигнала одновременно дает и результат его спектрально-временного анализа, аким образом, требуется оценить все значения параметров X =(х,',...,х,у), -где , =(а,,Ц), на основе анализа предъявленного сигнала У - (}';,...,}'„) с фрагментом редыстории У' = ...,г0), исходя из предположения, что векторный параметр х, вменяется не слишком быстро вдоль оси аргумента г и удовлетворяет условию гационарности в каждый момент времени г. Последнее утверждение означает, что гловис I г I > 1 должно выполнятся для всех корней «нестационарного» характери-гического полинома £>(г) = 1-а,,г- а, ^ -...-а1пг", коэффициенты которого изме-яюгея во времени. В частности для модели нестационарной авторегрсссии второго орядка п~2 показывается, что условия мгновенной стационарности приводят к «теме линейных уравнений

{X, + х1 < 1, х'^-х, <1, -1 < х2 <1,

эторая представляет собой треугольник на плоскости коэффициентов регрессии , б Я2 (рис. 1) и играет роль ограничсний-неравенств в задаче оценивания неста-ионариой авторегрессии

-1

Рисунок 1. Допустимая область изменения коэффициентов авторегрсссии для случая авторсгрсссионной модели второго порядка

В первой главе показано, что задача оценивания нестационарной регрессии, адек-ггная вышеперечисленным приложениям, естественным образом сводится к задаче щдратичной оптимизации относительно последовательности действительных век-ipnbTX аргументов X = (х, s R", / = ],...,N)

Дх.....,x,,) = £(x,-x;,)7'Qf(x,-x°)+£(x,_,-Ax,)'fU,(x,_l-Ax,)^ min , (2)

/ t T .1 *'.....*Л

при ограничениях в виде равенств и неравенств, наложенных на каждую векторную переменную в отдельности , ,

. С,х, +с, >0,. ; ' ."' (3)

В,х,+Г, =0. (4)

Эта задача является частным случаем задачи минимизации парно-сепарабелыюй целевой функции

с зависящими от данных квадратичными узловыми функциями л\/, (х,), оценивающими степень несогласованности значения каждого локального параметра модели х, с формой сишала в некоторой малой окрестности текущей точки г, и квадратичными функциями связи %(*, ].*,)> выражающими несогласованность значений каждой пары соседних локальных параметров с априорными представлениями об искомой нестационарной модели. ,..,'. 7

Далее в первой главе исследована алгоритмическая сложность решения Задачи квадратичного программирования общего вида с линейными ограничениями в виде равенств и неравенств. Показано, что наличие ограничений в виде равенств не выводит задачу оценивания нестационарной модели сигнала из класса линейных по вычислительной сложности и даже более того, приводит к некоторому снижению вычислительной сложности за счет того, что часть компонент векторных переменных зафиксировано ограничениями в виде равенс тв и не участвует в процедуре рп-. тимизации. В противоположность ограничениям в виде равенств, при наличии ограничений в виде неравенств задача оценивания нестационарной модели сигнала приобретает полиномиальную вычислительную сложность относительно числа векторных переменных. 'Дан подробный обзор методов решения задачи квадратичного программирования (2) с ограничениями (3)-(4). Во-первых, это прямое решение задачи квадратичного про1раммирования с помощью метода наискорейшего спуска, симплекс метода, метода внутренней точки, метода штрафных функций. Все методы этой 1руппы обладают одним сухцественным недостатком - они не учитывают важного модельного предположения о линейной упорядоченности последовательности коэффициентов регрессии, то есть парной сепарабельности задачи, и имеют полиномиальную вычислительную сложность относительно числа векторных переменных!

Ко второй 1руппе методов относятся методы, ориентированные именно на парную сепарабельность целевой функции и активно использующие в своей основе алгоритм динамического программирования Беллмана. Этот алгоритм позволяет заменить исходную задачу последовательностью существенно более простых задач минимизации промежуточных функций одного аргумента, называемых функциями Беллмана. Хотя классическая процедура динамического программирования принципиально основана на предположении, что аргументы целевой функции принимают лишь конечное множество значений, в предыдущих исследованиях метод динамического программирования был распространен на случай непрерывных переменных для квадратичных целевых функций путем введения понятия параметрического семейства квадратичных функций Беллмана. Однако численная реализация такой процедуры в задаче оценивания нестационарной регрессии (2), (3) и (4) оказывается затруднительной, поскольку наличие неравенств в ограничениях выводит очередную функцию Беллмана из конечно-параметрического семейства квадратичных функций.

Далее в первой главе показано существование проблемной ситуации, сформулированной выше в данном автореферате в разделе «Актуальность работы», и поставлены основные задачи исследования.

Во второй главе предлагается алгоритм решения задачи парно-сепарабельного квадратичного программирования, построенный по итерационному принципу и реа-

5ующии метод наискореишего спуска, применяемый для решения двойственной 1ачи. Задаче соответствует функция Лагранжа

N

Дх,,...,хл, X.....= +с,) =

,v (6)

' ' £[ (х, -x,YQ,°(x, -xf(Gx, +с,)] +£(А,хм -x,)rU,(A,xM -хД

: X, =; (Х)---Х"У е R™ , X/ >0, j = 1.....т, - векторы, составленные из нсотрицатель-

х множителей Лаграпжа при каждом , векторном ограничении А,х, +с, >0,

1.....N. Решением задачи является седловая точка функции Лагранжа: '

L(x,,...,xw, min ,

«i«R*.....ру

¿(х„...,хл,, X......XJ-» nm

Л.| ¿О,. .,r.pf 2(1

"оберем всс переменные в один общий вектор х = (х[ в R"v, аналогично,

зрмирусм вектор X = ■ ■ ■ X], )Т е R"'A', составленный из векторных множителей ранжа при всех переменных. Пусть х(Х) = arg min L(x,X) = xTQx-gx-xTGTX, да дня решения задачи достаточно будет найти максимум двойственной целевой теции IV(X) = L(x(X),X) при ограничениях Я>0, применяя, например, метод наис-)ейцгего спуска к функции -W(X)..

1сли Я* - очередное приближение к оптимальному вектору множителей Лагран-то. для реализации метода наискорейшего спуска надо прежде всего найти гра-;ит двойственной функции в этой точке u4 =VlH/(X,i). Одним из основных ре-ьтатов данной работы является установление того факта, что в случае парпо-

арабельной целевой функции J(x,.....xv) для вычисления градиента двойствен-

i функции дост аточно решить задачу минимизации функции Лагранжа (6) по не-шнным х,,...,*^ без oipai-шчений при фиксированных Я., = =Х\ , что в си-

квадратичности й парной сепарабельности этой функции легко сделать методом ►гонки, или, что эквивалентно, методом квадратичного динамического програм-зования за число операций, пропорциональное числу переменных N, в отличие ¡адачи квадратичного программирования общего вида, в которой для вычисления циента на каждом шаге итерационного процесса потребуется выполнить число раций, пропорциональное N'. )вое из условий дает

V,£(x, А,) = Qx - g - GTA. = 0,

уда получим

x(Ä,) = Q'(g + GTA,). (8)

ктановка этого выражения во второе условие (7) превращает его в двойственную евую функцию, аргументами которой является вектор множителей Лагранжа:

vva)=-^(g+Grx)rxa)-c4. . (9)

аким образом, мы приходим к формулировке задачи парно-сепарабельного цратичного программирования (2), (3)-(4) в виде другой задачи квадратичного граммирования, называемой двойственной по Вульфу или по Лагранжу nö • отгнию к исходной задаче:

„ -\V(?.) = i(g + Gr?.)'Q"'(g + G7X)-c'X-^min. (10)

задача уже не является парно-сепарабельной.

Построим алгоритм решения двойственной задачи методом наискорейшего спуска. Пусть на к-й итерации получен допустимый вектор множителей Лагранжа Хк е В"'л, X1 > 0. Найдем вектор градиента двойственной функции в этой точке

Ь* =( (Ь?)г-(<)г)7, ^ У^О,') = -вСТ' (8+) - с = -(Сх(А/)+с)=Ь'. (11)

Вектор х(Х,*) определим как результат минимизации функции Лагранжа (6) по х,,..„х„ без ограничений при фиксированном значении Х = Х1с помощью алгоритма квадратичного динамического программирования, имеющей линейную вычислительную сложность относительно числа переменных N. После этого допустимое

направление спуска Ь* = ( (й? ?' • ■ ■ (Ь^, )г) , Ь' = (/!' • • ■ )г, находится по правилу ь если X/ >0 иди /г/" >0,

«Ч* „/ ' ? = 1.....N. ;=1,...,т. (12)

(0, если XJ. =0 и h' <0,

Если 1И =0, то Хк >0 есть решение двойственной задачи, а х(Я') - решение исходной задачи квадратичного программирования (2)-(4), в противном случае вектор h* определяет допустимое направление спуска. Минимизируя из точки

X* вдоль направления Ь* так, чтобы не нарушить неотрицательности множителей Лагранжа, приходим к новой точке = + ah', где a > 0 - параметр, определяющий длину шага в допустимом направлении. Если параметр a = const, то мы получаем метод градиента. Метод наискорейшего спуска заключается в рассмотрении параметра а как переменной, тогда.+ah') = -VV*(a) будет функцией переменной а. Это квадратичная функция одного аргумента -VV* (а) = (}' + pf а + (}'а', точка минимума которой

a* =argmin(-Vf(a» = -(Pi/2pi)

а

указывает очередное значение вектора множителей Лагранжа Xl+l + alhl.

Для вычисления оптимального значения длины шага сс1 необходимо определить значения параметров (3j, fif и pj квадратичной функции W(a). Для этого достаточно вычислить по формуле (9) три значения функции W4 (a) = W{X* + a hf) для трех разных значений длины шага a = 0,ot',a", после чего искомые параметры легко мо-iyr быть найдены из решения соответствующей системы трех линейных уравнений.

Однако в процессе анализа сигналов часто приходится решать смежные задачи, например задачу обнаружения нарушений гладкости изменения оцениваемого параметра, задачу оценивания дисперсии шума наблюдения в модели нестационарной регрессии, задачу подбора класса нестационарной модем и т.д. Алгоритмическое решение этих задач связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента прр разных моделях сигнала без пересчета оптимальных значений в других точках. Таким образом, объем вычислений при применении метода наискорейшего спуска возрастает пропорционально квадрату длины сигнала TV2, в то время как оценивание последовательности векторов коэффициентов регрессии требует объема вычисле ний, пропорционального лишь длине сигааДа /V.

Поэтому требуется разработка другой процедуры решения задачи парно сепарабельного квадратичного программрования, обеспечивающей поиск всех оце нок с выколотой точкой за два прохода сигнала с числом операций, пропорциональ ным N.

В третьей главе рассматривается другой алгоритм, не являющийся итсрацион-ым и по своей вычислительной сложное™ эквивалентный 1гримерно одной итера-,ии алгоритма наискорейшего спуска, но не гарантирующий нахождения,точного ешения задачи нарно-сепарабельного квадратичного программирования в силу на-ичия в его структуре некоторых эвристических шагов.

Ограничения (3), наложенные на каждую переменную х, в отдельности, опреде-яют множество ее допустимых значений X, ={ х, € Я*: С,х, + с, > 0} с Н" или, в квивалентной форме,

■. ъ?х,+с1 >0, 7 = 1.....т}сЯ", (13)

де каждое из т неравенств определяется соответствующей строкой й' е И" матри-;ы С,(тх>|) и соответствующим элементом г/ е Я вектора с,. Если абстрагировать-я от специфики квадратичной целевой функции (2), то с общих позиций задача за-лючается в минимизации некоторой парно-сепарабельной целевой функции общего ида (5) в заданных областях варьирования переменных х, е X,, г = 1.....N. Естественным средством оптимизации для целевых функций такого вида является метод [инамического программирования, выражаемый, например, процедурой «вперед и [австречу», изложенной в предыдущем разделе. Соответствующий алгоритм, если го удастся построить, будет иметь линейную вычислительную сложность относи-ельно числа неременных N, поскольку будет сводиться к рекуррентному пересчету пункций Беллмана вдоль последовательности упорядоченных переменных в двух [ротивоположных направлениях.

Центральная идея метода динамического программирования как средства мини-ппации парпо-сепарабельных целевых фупкций вида (5) в пределах некоторых до-

густимых множеств значений переменных х, е X,, I = 1.....N, заключается в понятии

юследовательности функций Беллмана /,"(х,) = тш1|1Х.....Х1 ^ ^ J~(■x1,...,x¡), связан-

(ых с частичными критериями УДх,.....х,) = ^ , Ч', (х,)^ (х>х.,) • Функции

>еллмана вычисляются последовательно слева направо по легко доказываемому ре-гуррентному соотношению

I (х,) = V, (х,) + ш [У, (х, ,, х,) + , (х, ,)], Г = 1.....N, (14)

¡ачиная с очевидной первой функции Беллмана 7~(х,) = (х,).

Фундаментальное свойство функции Беллмана

„, .7;(Х,) = Ч',(Х,) + ГТ1'П [ + (15)

5удем называть прямым рекуррентным соотношением, а функцию

= (х,) = аггпнп [ 7,(х,.,,х,) + 7,;1(х,_1)], хмеХм, (16)

5удем называть обратным рекуррентным соотношением.

Процедура динамического программирования заключается в последовательном >екуррентном пересчете функций Беллмана, начиная с первой переменной г = 1, и «поминании обратных рекуррен тных соотношений для всех переменных, начиная ;о второй ? = 2....,А^, с последующим использованием их для определения оптимальных значений всех целевых переменных х, в обратном порядке, начиная с по-;лсдней t—N,...,]. В силу такой структуры, свойственной классической схеме ди-тмичеекого 1ф01раммир0вания, мы будем называл, эту процедуру процедурой ти-1а «вперед и обратно».

Ниже в разделе. 4 мы рассмотрим задачу оценивания дисперсии аддитивного шу-ла в модели нестационарной регрессии, для которой классическая схема динамиче-

ского программирования «вперед и обратно» оказывается недостаточной. В данном разделе предлагается другая схема динамического программирования, которую мы будем называть схемой «вперед и навстречу», опирающаяся не на один, а на два вида функций Беллмана, рассчитываемых навстречу друг другу с двух разных концов сигнала. Именно эта схема будет использована затем в разделе 4 для автоматического выбора степени сглаживания последовательности параметров нестационарной модели сигнала.

Наряду с частичными критериями У~(х,,...,х,), которые определяются слева направо, начиная с первого отсчета сигнала, и которые мы будем называть левыми, вполне естественно рассматривать симметричные по отношению к ним правые частичные критерии, определяемые с конца сигнала J*(x,,...,xN) = ^|"|\^!l(x:l) + • Соответственно, в дополнение к левым функциям Беллмана

У,"(х,)'=чтп д ¿'(х......х,), введем в рассмотрение их правые аналоги

7,Чх,) = ш1п, 1еХ _ У,'(х,,...,х„), рекуррентно вычисляемые в противоположном направлении

+ + ' = лг.....ь 07)

начиная,с очевидной последней правой функции Беллмана 7^(хЛ1) =

Для построения процедуры динамического программирования «вперед и обратно» важное значение имеет следующая теорема, доказанная в диссертации:

Теорема 1. Для любого момента времени г = 2,..., N -1 произвольная парно-сепарабельная целевая функция вида (5) допускает представление

V. (*1) + Уг (*| • х2) + К (х2), У«_1<*1.....

Введем понятие маргинальных функций /,(х,)

— 1П!п^ у 3(х1 ,...,хк), каждая из которых выражает зависимость целевой функции от значения одной отдельно взятой переменной при условии, что другие переменные принимают условно оптимальные значения в соответствии с х,. Очевидно, что минимум маргинальной функции непосредственно указывает оптимальное значение соответствующей целе-: вой переменной х, = аг§гтп1б)С J,(xl). Следующая теорема показывает, что встреча левой и правой функций Беллмана в некоторой точке г определяет маргинальную функцию в этой точке и, следовательно, оптимальное значение'соответствующей целевой переменной:

Теорема 2. Каждая маргинальная функция допускает представление 3,(х,) = 3, (х,) + 1/.(х,)-¥,(*,)■ ; . .

Целью новой процедуры динамического программирования, альтернативной по. . отношению к процедуре «вперед и обратно», является вычислительно? Удобство, рн-!. ределения оптимального значения одной переменной х, в заданной точке I реи ар-. гумента сигнала для разных вариантов узловой функции уДх,) в этой ¡ точке и раз- : ных вариантов пары смежных с.ней функций связи уДх/./.х,) и "у,,.,(*:,', х,.,) независимо от оптимальных значений других переменных. ■г 1

Единственным, но очень существенным препятствием для реализаций такой идей является необходимость наличия достаточно компактного' конечно- •

эамегрического представления функций Беллмана. В случае квадратичной целе-\ функции (2) и отсутствии ограничений функции Беллмана являются квадратич-ми и полностью определяются своими немногочисленными параметрами. Одна-при наличии ограничений в виде неравенств (3) функции Беллмана уже не будут щратичными, и их параметрическое представление становится проблематичным. Алгоритм, рассматриваемый в данном разделе, основан на эвристической замене квадратичной функции Беллмана, возникающей на каждом очередном шаге ре-эрентного пересчета, подходящей квадратичной функцией, сохраняющей некото-е наиболее существенные свойства исходной функции.

Пусть функции /;;.,(х,_,) й рассматриваются как левая и правая функции

илмана, соответственно, непосредственно предыдущей и непосредственно сле-ющей переменной в упорядоченной совокупности переменных целевой функции отношению к некоторой переменной х,. Тогда согласно и (17) в качество левой и авой функций Беллмана этой переменной должны быть приняты функции

7,-(х,) = у,(х,)~/Пх,), .7;Чх,) = у,(х,) + ^-(*Л (18)

F, (х,) = min [y,(xM,x,) + J,_,(xM)],

_ (19)

F; (xf) = min Iу„, (х„х,+))+J,\t (х,+1)],

I качестве функций v,(x,) и у,(х, ,,х,) выступают квадратичные узловые функции функции связи. Даже если предположить, что предыдущие функции Беллмана ., (хм) и /*,(х,+1) квадратичны, функции F~(x,) и F^(xr) (19) уже не будут квад-гичными, поскольку в их формировании участвует операция минимизации при раничениях тиаа_ неравенств. Как следствие, неквадратичны и новые функции ллмана в целом J~(xt) и J*(х,).

Предлагаемая здесь идея приближенной реализации процедуры динамического ограммирования заключается в замене функций F, (х,) и F/(x,) (19) подходящи-[ квадратичными функциями

/=)'(х,)=Ь,'+(х,-x;fQ,'(x, -<) = F-(x,),

F; (Х,)=Ь;+(Х,-Х;)ГО;(Х, -*;)=F/(X,).

п-да квадратичными будут и следующие аппроксимации функций Беллмана:

+(х, -х°)го°(х, -х°)+ь;+(х, -x;)tq;(x, -о = $-+(*, ~%;f q;(x, -хд J,+ (x,) = V,(x,)+f,tx,) =

г>,°+(x, -x°)rQf(x( -х|')+г>,'+(х, -x^'q^x, -x,o= S;+(%, -х,+)г<э;(х, -x,+). Параметры квадратичной аппроксимации функций Беллмана (&,", х,", Q") и . 5Г. Q,') полностью определяются параметрами (h°, х", Q") квадратичной узло-й функции V, (х,) вместе с параметрами (b', х', Q') и (b", х' Q,*) квадратичной [проксимации /-¡tx,) и /•',' (х,) функций /•'," (х,) и /'Г(х,) соответственно:

q; =Q"+Q'. х, = (Q,)1 (QУ, + QX), Б, = ь,°+ь;, Q; = Q? + Q' 5; = (Q;У 1 (ОУ + QX). b, = + ь;.

1чальные функции Беллмана J~ (x,) = у,(x,) = ¿1° + (x,-xf)'Q"(x,-x") и J*(xN) = + (% v -x° )7 Q° (x jV xд,) имеют очевидные параметры

Qr=Q ?,ír=*?,¿f=if.

Таким образом, квадратичная аппроксимация очередных функций Беллмана сводится к подбору подходящих значений параметров (/>,', х', QÍ) и ф", xf, Q') квадратичных функций F,'(x,) и F" (х,) (20), которые обеспечивали бы сохранение основных особенностей исходных функций F~ (х,) и F/(x,) (19) и, следовательно, исходных функций Беллмана (18). Такими особенностями являются, в первую очередь, положение точек минимума этих функций arg min F~(x,), arg min F' (x,), и значения в

точках минимума min Ft (x,), min f]1 (x,). Представляется предпочтительным передать эти параметры в точности, выбрав

х' = arg min F/(x,) = arg min F¡~ (x,), b¡ = min Fi (x,) = min >7 (x,),

x" = arg min F* (x,) = arg min F* (x,), b"= nún F" (x,) = min F* (x,), (24)

Выбор параметров (b't, Q,') и (fc,*, х', Qf) квадратичных аппроксимирующих функций для приближенного представления левой и правой функций Беллмана определяется следующими двумя теоремами: ' v

Теорема За. Пусть предыдущая функция Беллмана ./,"-1 (х,ч) и функция связи 7, (х,_,,х;) являются квадратичными ...■,.■>

-/,_,(Х,_,) =ÄH + (*,., -xw)rQ,_,(x,_, -Х,1,), уДх,(А,х,., -x,)7U,(A,x,_, ~х,). Тогда параметры х', Q') квадратичной аппроксимации Ff'(x,) функции F,"(x,), удовлетворяющие условиям (24), имеют вид

Q;=иГА, dC)r 0Г-,н,">[и,+(H;ÜA[U,-D7U,(H;Í;A:U, -и.

где х'_, есть решение задачи квадратичного программирования

х'_, = arg min (x,_1-x,"_,)rQ7.,(x-x7_1), (25)

j ni

а квадратная матрица H''¡ есть левый верхний блок (пхп) матрицы

н;,=

(К\ /

HS H;:íj V

(Q;, + AíutA,) -g;:

V1

о

где, в свою очередь, матрица Сг1 (к' х п) есть матрица, составленная из строк ё/!, , соответствующих активным ограничениям задачи квадратичного программирования (25).

Теорема. 36. Пусть предыдущая функция Беллмана 7,,,(х,(1) и функция связи 7,(хг>х„,) являются квадратичными

У/,,(х,(1) = Ьы + (х„, -х„,)гд,,,(х,-х,,,),,7,(х,,х,) = (А,+1х, -х,„)ти„дСА,„х,-х,^). Тогда параметры (Ь", х", О') квадратичной аппроксимации ^Тх,) функции ), удовлетворяющие условиям (24), имеют вид

хХА^ил;,,)^ АГ„и,0х;ч1., ь"= ь;„+«., -^„/О;,,«,, -*:.,)>

де х*, есть решение задачи квадратичного программирования

К, = агЯшш - (26)

8,'Т,20

квадратная матрица сеть левый верхний блок ) матрицы

Н,,, =

Ч0;+,+и;+|) Г н:1,1 н:12

вг о

(е, в свою очередь, матрица С",,(к'у:п) есть матрица, составленная из строк й/^, ютветствующчх активным ограничениям задачи квадратичного программирования ■6). ;;

Пятая глава начинается с изложения задачи оценивания постоянной дисперсии | аддитивного шума наблюдения в модели нестационарной регрессии (1). Сред-

1Й остаточный квадрат ошибки предсказания дает занит

енную оценку дисперсии шума. Дело в том, что при вычислении ошибки в каждой гаке г используется оценка текущего вектора коэффициентов регрессии , полу-,, :нная вместе с оценками векторов коэффициентов в других точках -как результат янимизации критерия (2), требующего минимизации остаточных квадратов ан-юксимации всех наблюдений, в том числе и текущего наблюдения у,. Иными сломи, при вычислении ошибки в очередной точке г нельзя пользоваться оценкой, в армировании которой участвовало данное наблюдение у,.

Для получения корректной оценки дисперсии шума наблюдения предложено ис-шьзовать идею процедуры скользящего контроля, широко применяемой в распо-авании образов. Пусть наблюдение у, пропущено, что легко имитируется примем в критерии (2). Тогда оценка вектора коэффициентов рсгрсссии в ой точке х,, полученная ггри минимизации критерия, будет определяться интерпо-цией, между соседними оценками в силу эффекта сглаживания. Именно такая [енка, для которой в диссертации принято обозначение , используется для 1числения ошибки в данной точке.

Квадрат остатка ()'" -(х^УуУ в «выколотой» точке г дает корректную оценку шбки предсказания в этой точке, поскольку он вычислен по неполной последова-

иьности наблюдений (>'°,...,у,°1, .....у°„), не содержащей наблюдения у,.

1енку дисперсии шума в целом предложено определять как среднее значение адратов ошибок по всем точкам сигнала:

¿0,= ()/Д Г)£» (уО _ (-<„у у у (2?)

Вычисление но этой формуле опирается на последовательность оценок векторов

эффициентов регрессии Х{1..........Я^'), каждая из которых найдена без

ста текущего наблюдения у,. Для того, чтобы найти одну такую оценку &,"1 для которой точки с, необходимо вычислить всю последовательность оценок векто-в коэффициентов регрессии X"' = (х!0,...,^) для последовательности наблюде-й, в которой эта точка пропущена (у.,...,>',_,, а затем уже использовать

этой последовательности одно значение Если применять процедуру «вперед >братио»; то ее придется запускать отдельно для вычисления ошибот в каждом от-

N

счете сигнала = у,0 -(х(/|)ту|, поскольку всякий раз. должна обнуляться матрица О" в другой узловой функции \у,(х,) = (х, -х°)тО°(х, -х°).

В результате объем вычислений, необходимых для оценивания дисперсии шума наблюдения с применением метода наискорейшего спуска возрастает пропорционально квадрату длины сигнала Л'1, в то время как оценивание последовательности векторов коэффициентов регрессии требует объема вычислений, пропорционального лишь длине сигнала N. Поэтому для решения этой задачи требуется ггрименение придлиженоой процедуры динамического программирования «вперед и навстречу», обеспечивающей поиск всех оценок с выколотой точкой за два прохода сигнала с числом операций, пропорциональным N.

Параметрическая процедура динамического программирования «вперед и на- ■ встречу» позволяет вычислить последовательность оценок векторов коэффициентов .

регрессии Х°.....без учета текущих наблюдений у,, входящих в.

оценку дисперсии аддитивного шума, за число операций, пропорциональное длине

сигнала N. Для этого нужно последовательно вычислить в каждой точке 1 =!.....N

параметры левых и, независимо в обратном порядке г = Л',...,!, параметры правых функций Беллмана. После этого остается в каждой точке вычислить вектор х|° по.,

правилу х, = аг^тп!п\3;(х,) + (х,) - (х,)] .

В задаче нестационарного регрессионного анализа (1), включающей в себя также задачи сглаживания и спектрально-временного анализа сигналов, степень сглаживания искомого параметра х, между каждыми двумя соседними точками оси аргумента сигнала 7-1 и г.. определяется квадратной матрицей и, в составе функции связи. Матрица и, построена так, что она определяется одним скалярным параметром и, >0, задающим тем ббльшую локальную степень сглаживания, чем больше его значение.

Стецень .сглаживания ы1 представляет собой параметр, характеризующий класс моделей, в предела* которого выбор конкретной модели осуществляется путем минимизации соответствующей целевой функции. В диссертации предложено интерпретировать задачу выбора степени сглаживания как задачу выбора класса моделей, наиболее адекватного анализируемому сигналу. Степень адекватности класса моделей оценивается минимальной достижимой дисперсией £> аддитивного шума , оценка которой £>".....л) (27) получается с помощью процедуры скользящего контроля.

В основе вариационного подхода к анализу сигаалов лежит априорное предположение, что искомая последовательность значений скрытого параметра нестационарного сигнала X =(х1,...,хл,) является достаточно гладкой, и умеренная степень сглаживания в процессе оценивания не может ее существенно исказить. Однако при обработке сигналов часто возникает ситуация, когда такое априорное предположение не является вполне адекватном природе анализируемого сигнала, и' необходимо допустить наличие явных разрывов в подлежащей восстановлению скрытой последот вательности параметров нестационарной модели, замаскированных шумом в анализируемом сигнале.

Каждая из основанных на модельных представлениях функций связи у,(хн,х,) в составе критерия (2) необходима для наложения индивидуального штрафа на несглаженность полученного массива на паре соседних узлов цепи (/-1, г), поэтому У,(х,_,,х,)=0 если =х,. Чем быстрее возрастает функция связи, рассматриваемая' как несоответствие между х,_, и х(, тем более сглаженным будет результат обработки сигнала х, в соседиих точках (г-1,0- В частности, если у,(х,-1>х,) ~ ^. ™ "1Т0

мет что соответствующий скачок разрешен, т.е. узаконен в модели, и будет остыо сохранен в ходе обработки данных. Если положение скачков в последо-шности значений оцениваемого параметра известно, то эти скачки могут быть анены путем замены основной достаточно «жесткой» функции штрафа не некость у,(х,н, хг) на соответствующих парах соседних точек более «мягкой» сцисй у*(х,_,, х,), но для этого надо прежде обнаружить скачки, м любой пары смежных точек области определения сигнала (г—1, г) минималь-значение целевой функции (2) может быть представлено в виде

,,..........*»)=mifl1 1хеВЛЛ11(х,_1)+у((х,.1,х,)+7,+(х()}. Чем «мягче» функция

и, то есть чем меньше она отличается от иуда с увеличением разности (хм—х,), меньше будет это минимальное значение. Правдоподобность гипотезы о нали-скачка на данной паре точек естественно измерять величиной отношения

= min { 7, Дх, i) + r,(x, pX^ + J/Cx,)}/ min { 7M(x, 1) + r;(x,.1,xl) + 7;(x,)} .

х, [.s.eR / 1С, 1 1

и это отношение превосходит заранее установленный порог z, > й , то исследуе-нара переменных должна рассматриваться как потенциальное место возможного 1ка. Этот факт может быть встроен в модель нугем принятия более «мягкой» кции связи на данной Паре смежных точек Y*(xi-i>x<) взамен у, (х^.х,). После эй замены значения критерия г,, вообще говоря, изменятся, и могут проявиться та других скачков, ранее замаскированные шумом и соседними скачками. Га основе этой идеи в диссертации построен итерационный алгоритм сглажива-сигналов с сохранением локальных особенностей, использующий на каждой рации процедуру динамического программирования «вперед и навстречу» для шеления последовательности значений критерия г,. В ходе итерационного проса обнаруживаются все новые и новые неоднородности, вначале замаскирован; шумом, подобно тому, как перегруженный эластичный прут ограниченной >чности переламывается и разрывается скачками, всякий раз в самой иерегружеп-i точке, по мере того, как новые изломы уменьшают прежние концентрации на-шения, создавая их тем самым в новых точках.

? шестой главе диссертации проводится экспериментальное исследование нред-кенных в третьей и четвертой главах алгоритмов оценивания модели нестацио-1ной регрессии.

3 отличие от асимптотически точного алгоритма наискорейшего спуска, прибли-нный алгоритм динамического программирования, основанный на эвристической (ене истинных функций Беллмана их квадратичными аппроксимациями, не жнтирует, вообще говоря, нахождения точного решения задачи парно-тарабельного квадратичного программирования. В данной диссертационной ооте не проводится аналитического исследования погрешности метода, поэтому пичипа отклонения от точного решения нуждается в экспериментальной оценке на которой типовой задаче.

Порядок зависимости времени, необходимого для реализации приближенного ал-ритма динамического программирования, от числа переменных парно-парабельной целевой функции проверять экспериментально нет надобности, по-ольку из структуры алгоритма непосредственно следует, что его вычислительная ожность является линейной относительно числа переменных. Такую же вычислили гую сложность имеет и одна итерация алгоритма наискорейшего спуска, однако (ело итераций, необходимое для достижения заданного приближения к стационар-ш точке, можно оценить лишь экспериментально.

В качестве тестовой задачи для экспериментального исследования алгоритмов лла принята задача оценивания коэффициентов нестационарной регрессии (1) при

размерности заданной базисной последовательности у, и, соответственно, оцениваемого вектора коэффициентов регрессии х, равной п = 4.

Были использованы три алгоритма решения задачи квадратичного программирования - алгоритм общего вида Мозек (http:Wwww.mosek.com), реализующий метод внутренней точки и не учитывающий парно-сепарабельный характер задачи, асимптотически точпьтй итерационный алгоритм наискорейшего спуска (глава 3) и приближенный алгоритм квадратичного динамического программирования (глава 4). Относительное отклонение полученной оценки последовательности коэффициентов регрессии X =(х,, г =1,...,Л0 от истинной последовательности Х=(х„<= 1,...,Л0

оценивалось показателем й = • полУчснныс результаты

приведены на рис. 3:

Можно сделать вывод, что Мояек и алгоритм наискорейшего спуска дают практически совпадающие решения, от которых очень мало отличается решение, даваемое алгоритмом динамического программирования.

Проверка быстродействия алгоритмов проводилась путем оценивания последовательности коэффициентов ре1рессии по наблюдаемому сигналу возрастающей длины до N = 2000. Полученные результаты показаны на рис. 2. Проследить полиномиальную зависимость времени работы общего алгоритма от числа переменных удалось только до длины сигнала N = 500, поскольку при большем числе векторных переменных программа Мояек потеряла работоспособность. Преимущество асимптотически точного алгоритма наискорейшего спуска перед также асимптотически точным алгоритмом внутренней точки, реализуемым программой Мовек, проявляется, начиная с длины сигнала N = 250, в то время как приближенный алгоритм динамического программирования имеет более высокое быстродействие при любом N. Быстродействие итерационного алгоритма наискорейшего спуска примерно в пять раз ниже, чем у приближенного алгоритма, что примерно соответствует числу требуемых итераций.

I с

модифицированный метод

наискорейшего спуска

приближенная реализация процедуры __II__\У ' «вперед и навстречу»

классическая процедура квадратичного программирования

0 1000 2000 Рисунок 2. Зависимость времени г (с), затраченного на решение задачи восстановления коэффициентов нестационарной регрессии, от длины анализируемых сигналов N при использовании классической процедуры квадратичного программирования, модифицированного метода "наискорейшего спуска и приближенной реализации процедуры динамического программирования.

классическая процедура квадратичного программирования

истинная

последовательность коэффициентов регресии

= J.J4-Î0"6

приближенная реализация процедуры «вперед и навстречу»

модифицированный метод наискорейшего спуска

Рисунок 3. Сравнение последовательностей коэффициентов х,, ? = регрессии,

полученных с помощью классической процедуры квадратичного программирования, модифицированного метода наискорейшего спуска и приближенной реализации процедуры динамического про1раммиропания, с истинной, априорно заданной, последовательностью коэффициентов регрессии х,, 1=1,...,N.

. Предложена вариационная постановка достаточно широкого класса задач анализа нестационарных сигналов при наличии отраничений на параметры модели сигнала в каждый момент времени как задач парно-сепарабелыгого квадратичного программирования.

. Предложен асимптотически точный итерационный метод решения задачи парно-сепарабельного квадратичного программирования, учитывающий парную сепарабельность задачи и имеющий линейную вычислительную сложность относительно числа векторных переменных.

. Разработан неитерационный алгоритм решения задачи парно-сепарабельного квадратичного программирования, представляющий собой приближенную реализацию процедуры динамического программирования. Алгоритм разработан в двух вариантах на основе классической процедуры динамического программирования «вперед и обратно» и специально разработанной процедуры «вперед и навстречу».

t. Сформулирован класс новых задач анализа нестационарных сигналов при наличии ограничений па значения параметров их нестационарных моделей, которые не могут быть алгоритмически решены классической процедурой динамического программирования и методом наискорейшего спуска, и разработаны принципы их решения на основе предложенной процедуры динамического программирования «вперед и навстречу».

5. Разработан алгоритм автоматического выбора степени сглаживания параметров нестационарной модели сигнала на основе метода скользящего контроля.

6. Разработаны алгоритмы сглаживания сигналов с сохранением границ и спектрально-временного анализа сигналов с сохранением скачкообразных изменений спектра колебаний.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

[. Моттль В.В., Копылов A.B., Костин A.A. Красоткина О.В. Алгоритмы динамического программирования для оценивания моделей нестационарных сигналов. Доклады X Всероссийской конференции ММРО-Ю, Вычислительный центр РАН. Москва, 2001г, -С. 345-349.

I. Красоткина О.В. Алгоритмы ларноселарабельного -программирования в задачах анализа нестационарных сигналов. Доклады X Всероссийской конференции ММРО-Ю, Вычислительный центр РАН, Москва, 2001 г.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

3. Mottl V.V., Kopylov A.V., Krasotkina O.V. A quadratic programming problem foi elastic image matching. Proceedings of IASTED International Conference "Automation, Control and Information Technology", June 10-13, 2002, Novosibirsk.

4. Красоткина O.B., Моттль В.В., Копылов A.B. Алгоритмы оценивания нестационарной регрессии в задачах анализа сигналов. Труды б-ой Международной конференции «Распознавание образов и анализ изображений: Новые информационные технологии». Великий Новгород, октябрь 2002 г. Т. 1, С. 325-329.

5. Mottl V.V., Kopylov А.V., Krasotkina O.V. Algorithms of nonstationary regression estimation in signals processing. Proceedings of 6th International Conference "Patterr Recognition and Image Analysis" (PRIA 6), Velikiy Novgorod, Russian Federation, Ok tober 21-26, 2002.

6. Krasotkina О. V., Mottl V. V., and Kopylov A. V. Algorithms of Estimation of Nonsta tionary Regression in Signal Analysis. Pattern Recognition and Image Analysis, Vol. 13 No. 1,2003, pp. 127-131.

7. Mottl V., Krasotkina O., Muchnik 1. Constrained nonstationary signal processing b\ pair-wise separable quadratic programming. Proceedings of the LASTED Internationa Conference "Signal Processing, Pattern Recognition, and Applications". June 30 - Jul) 2, 2003, Rhodes, Greece. Pp. 205-208.

Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать Формат бумаги 60x84 '/,6. Бумага офсетная. Усл-печ.л. Уч.-изд. л. /,0

Тираж 1АО экз. Заказ 5/3,

Тульский государственный университет. 300600, г.Тула, просп.Ленина, 92.

Отпечатано в редакционно-издагельском центре Тульского государственного университета. 300600, г.Тула, ул.Болдина, 151

Введение.

1 Проблема оценивания нестационарной модели сигнала и основные задачи исследования.

1.1 Задачи оценивания нестационарной модели сигнала с ограничениями на значения параметров.

1.1.1 Задача сглаживания знакопостоянного и монотонного сигнала . I

1.1.2 Задачи авторегрессионного и спектрально-временного анализа .21 ц 1.1.3 Задача оценивания портфеля инвестиционной компании.

1.1.4 Задача оценивания нестационарной регрессии как обобщенная задача оценивания нестационарной модели сигнала.

1.2 Задача оценивания нестационарной регрессии с ограничениями на значения коэффициентов как задача парно-сепарабельного квадратичного программирования.

1.3 Существующие методы оценивания нестационарной регрессии.

1.4 Вычислительная сложность задачи квадратичного программирования.

1.5 Основные задачи исследования.

2 Асимптотически точный итерационный метод наискорейшего спуска для решения задачи парно-сепарабельного квадратичного программирования.

2.1 Двойственная форма задачи парно-сепарабельного квадратичного программирования.

2.2 Градиент двойственной целевой функции по вектору множителей Лагранжа.

2.3 Метод прогонки для вычисления градиента двойственной целевой функции.

2.4 Допустимо^ направление t.i^-ска и выбор тага наискорейшего спу.гка.

2.5 Итерационный алгоритм парно-сепарабельного квадратичного программирования.

3 Безитерационный алгоритм динамического программирования для приближенного решения задачи парно-сепарабельного квадратичного программирования.

3.1 Общая структура процедуры динамического программирования для оптимизации парно-сепарабельной целевой функции.

3.2 Алгоритм динамического программирования «вперед и навстречу».

3.3 Неквадратичность функций Беллмана.

3.4 Квадратичная аппроксимация функций Беллмана.

3.5 Приближенный алгоритм динамического программирования.

4 Алгоритмы оценивания нестационарной регрессии.

4.1 Алгоритм оценивания дисперсии аддитивного шума.

4.2 Выбор скрытой модели динамики последовательности коэффициентов регрессии.

4.3 Сохранение локальных особенностей последовательности коэффициентов регрессии.

5 Экспериментальное исследование алгоритмов парно-сепарабельного -квадратичного программирования.

5.1 Сравнительное исследование точности алгоритмов.

5.2 Сравнение быстродействия алгоритмов.

Сигналы являются, пожалуй, наиболее распространенными видами информации, ставшими в последние два десятилетия типовыми объектами применения компьютеров для анализа данных. Широко известны системы распознавания речевых команд и даже слитной речи, анализа экономических трендов, а что касается программ автоматического чтения печатного текста, то их использование стало массовым.

Особый интерес к компьютерной обработке именно сигналов в значительной мере определяется тем фактом, что это естественные виды организации потоков информации о внешнем мире, получаемой человеком и другими высшими животными через органы чувств, главным образом, посредством осязания, обоняния, слуха и зрения, и играющей фундаментальную роль в формировании их поведения.

Под сигналом принято понимать любую физическую величину, изменение которой во времени несет информацию о мире, внешнем по отношению к тому объекту, который эту информацию воспринимает. С точки зрения организации компьютерной обработки, когда время вынужденно рассматривается как дискретная переменная, сигнал представляет собой упорядоченную последовательность либо чисел, либо символов, если физическая величина, несущая информацию, сама имеет дискретный характер. Впрочем, роль оси, упорядочивающей отдельные единицы информации в массив данных, не обязательно должно играть время, это может быть и любая другая ось, например, пространственная координата.

Конечной целью анализа сигнала или изображения, как правило, является принятие того или иного решения об их источнике, например, какой слово произнесено, если анализируется сигнал речи, либо какое слово написано, если к анализу предъявлено изображение фрагмента рукописного либо печеного текста. Задачи такого рода относятся к области компетенции теории распознавания образов, в свою очередь, входящей в круг проблем, обычно называемых проблемами моделирования интеллектуального поведения. Эти вопросы привлекали основное внимание теоретиков, и в результате именно теория распознавания достигла в последние десятилетия наибольших успехов.

Теория распознавания образов разрабатывает методы построения формальных правил соотнесения поступающего сигнала или изображения с одним из источников. Для того, чтобы можно было применить данную теорию, необходимо прежде указать, какие свойства сигнала или изображения существенны для принятия решения о его источнике и в каких единицах эти свойства должны измеряться. После того, как такие свойства выбраны, каждый конкретный сигнал характеризуется конкретным набором их значений или, как говорят, оказывается представленным в виде точки в пространстве полезных признаков.

Таким образом, прежде чем обратиться к теории построения правил распознавания в некотором уже зафиксированном пространстве признаков, необходимо решить несравненно более сложную проблему их выбора, то есть представления исходного массива данных в виде, удобном для принятия окончательного решения. К тому же, в очень многих прикладных задачах результат предварительной обработки массива данных имеет самостоятельную ценность.

В то же время вопросы предварительной обработки сигналов и изображений теоретически разработаны существенно слабее. Несмотря на тот факт, что разнообразным задачам и алгоритмам первичного анализа посвящена обширная литература [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], каждая из таких задач рассматривалась отдельно от других независимыми исследователями для решения конкретных прикладных задач. Методы обработки сигналов и изображений, разработанные для каждой частной задачи, используют специфические системы понятий и специфический математический аппарат [11, 12, 13, 14. 15, 16]. В публикациях, посвященных этим методам, как базовые теоретические положения, так и результирующие алгоритмы излагаются с использованием специальной терминологии, часто не пересекающейся с терминологией, используемой для изложения подходов к решению других задач.

Понимание аналогичности алгоритмических проблем, всегда или, по крайней мере, очень часто возникающих в самых, казалось бы, разных задачах, и изложение этих проблем в общих терминах некоторого единого формального языка позволило бы объединить разрозненные фрагменты опыта, накопленного при решении каждой из них, и существенно сэкономить усилия при построении алгоритмов решения новых задач.

Тема настоящего диссертационного исследования находится в русле но-^ вого научного направления в методологии анализа данных, ориентированного на преодоление этого противоречия [17, 18, 19, 20, 21, 22].

Необходимость обработки массивов данных У -{у,, / = 1,.,Л0, упорядоченных вдоль оси некоторого дискретного аргумента t - времени, частоты, пространственной координаты, -типична для практики технических и естественно-научных исследований. Мы будем называть такие массивы данных сигналами, несколько расширяя традиционное значение этого термина, изначально ориентированного на обозначение функций времени в теории связи.

В последние годы интенсивно разрабатывается единый подход если не ко всем, то, во всяком случае, к большинству из чрезвычайно широкого разнообразия задач анализа массивов упорядоченных данных, использующий так называемый вариационный принцип, уже давно нашедший широкое применение во многих других областях науки [19, 20, 21]. Данная диссертационная работа представляет собой составную часть этого цикла исследований, направленную на дальнейшее развитие вариационного подхода к построению алгоритмов анализа сигналов. Мы начнем с краткого изложения этой концепции и возникающих в связи с ней алгоритмических проблем, решение которых и составляет цель настоящего диссертационного исследования.

Задачу анализа предъявленного массива данных, в данном случае, сигнала ^t - AO, определенного на оси некоторого дискретного аргумента, практически всегда можно понимать как задачу выбора его модели X из не6 которого класса моделей ХеХ. Применительно к сигналам, естественно различать стационарные модели, передающие общую форму предъявленного сигнала в пределах всей области определения t еТ = {1,., 7V}, и нестационарные модели, призванные отражать изменение некоторого локального свойства сигнала вдоль его дискретной оси. Например, постоянное среднее значение сигнала или его спектр в виде совокупности коэффициентов представления по заданному базису с этой точки зрения следует рассматривать как стационарные модели, в то время как типичными представителями нестационарных моделей являются изменяющееся локальное среднее значение сигнала или последовательность его локальных спектров, полученные путем усреднения соответствующего свойства сигнала в некотором скользящем окне. Нестационарную модель сигнала следует искать в виде последовательности локальных моделей либо значений изменяющегося параметра некоторой общей локальной модели в каждой точке оси сигнала X = (х,, t = 1,.,/V). В качестве априорной информации естественно принять предположение, что локальная модель изменяется, в основном, достаточно плавно, так что смежные локальные модели х;, и х,, скорее всего, близки друг к другу за исключением, быть может, относительно редких скачков, кроме того возможно, что векторные переменные х,, выражающие собой локальные модели, в разных точках оси сигнала могут иметь разную размерность.

Универсальный подход к оцениванию моделей массивов данных, в частности моделей нестационарных сигналов, дает вариационный принцип, заключающийся в поиске модели X из заданного семейства ХеХ путем минимизации подходящего критерия несоответствия между массивом и моделью X = argmin VeX J(X | У). Выбор множества X, возможных значений целевых переменных х; еХ, , вытекающий из их характера, определяет область варьирования обобщенной переменной X в вариационной постановке, конкретной задачи обработки данных.

Использование вариационного принципа позволяет ставить исходные прикладные задачи анализа данных как формальные задачи минимизации вполне определенных целевых функций J(X | У), то есть функций, формально выражающих цель обработки, и переводить, таким образом, проблему эвристического конструирования алгоритмов в точные термины теории оптимизации.

Важно лишь так выбрать класс целевых функций, чтобы было гарантировано существование эффективного достаточно быстрого алгоритма поиска точки минимума X = X(Y), выступающей в качестве результата обработки. Алгоритм минимизации целевых функций из выбранного класса и будет играть роль универсального обобщенного алгоритма обработки массивов данных определенного вида [21, 23].

В данной диссертационной работе рассматривается ряд примеров типовых задач анализа нестационарных сигналов: задача сглаживания сигнала, задача спектрально-временного и авторегрессионого анализа, задача анализа портфеля инвестиционной компании. Показано, что все эти задачи являются частными случаями задачи оценивания нестационарной регрессии, адекватнй многим приложениям [24, 25]. В работах [21, 23, 26,] обнаружено, что задача оценивания нестационарной регрессии естественным образом сводится к задаче квадратичной оптимизации относительно последовательности действительных векторных аргументов Аг = (х( eR", t = \,.,N)

Л .V

7(х,,.,хЛ,)= Y(x, - х")' Q°(x, - х")+ У (А,х,, -х,)7 U,(A,X,, - х,)-> min .

ТТ 71 Vl v являющейся частным случаем задачи минимизации парно-сепарабельной целевой функции

J(xn.,x л. ) = ) + ) с зависящими от данных квадратичными узловыми функциями vj/,(x;), оценивающими степень несогласованности значения каждого локального параметра модели х, с формой сигнала в некоторой малой окрестности текущей точки t, и квадратичными функциями связи уДх,рх,), выражающими несогласованность значений каждой пары соседних локальных параметров с априорными представлениями об искомой нестационарной модели.

Вообще говоря, задача парно-сепарабельной квадратичной оптимизации эквивалентна системе линейных уравнений с блочно-трехдиагональной матрицей коэффициентов при неизвестных х,,.,хл,, которая легко решается методом прогонки за число операций, пропорциональное числу векторных переменных /V . В данном диссертационном исследовании предложена интерпретация метода прогонки, как варианта более общего метода динамического программирования, предложенного около сорока лет назад американским математиком Ричардом Беллманом [27, 28, 48] и заключающегося в замене исходной задачи поиска минимума функции многих аргументов последовательностью существенно более простых задач минимизации промежуточных функций одного аргумента, называемых функциями Беллмана [29, 30]. Хотя основная процедура динамического программирования принципиально основана на предположении, что целевые переменные принимают лишь конечное множество значений, она распространяется в [20, 21] на случай непрерывных переменных для квадратичных парно-сепарабельных целевых функций путем введения понятия параметрического семейства функций Беллмана, которые также оказываются квадратичными. Получающаяся при этом процедура оптимизации, заключающаяся в рекуррентном пересчете и запоминании параметров квадратичных функций Беллмана, есть ни что иное как метод прогонки для решения соответствующей блочно-трехдиагональной системы линейных уравнений.

На основе такой интерпретации метода прогонки в работе [31] предложены алгоритмы решения ряда типовых задач анализа сигналов, сводящихся к задаче оценивания нестационарной регрессии. Разработанные алгоритмы опираются на процедуру динамического программирования «вперед ;и навстречу», основанную на понятиях левой и правой функций Беллмана и альтернативную по отношению к традиционной процедуре «вперед и обратно».

Раздельное вычисление левой и правой функций Беллмана позволило построить эффективную в вычислительном отношении процедуру скользящего контроля для верификации нестационарной модели путем последовательного сравнения экспериментального значения каждого элемента сигнала с его предсказанным значением по модели, построенной без участия этого элемента. Понятие двухсторонних функций Беллмана позволило также построить критерий обнаружения нарушений гладкости изменения оцениваемого параметра нестационарного сигнала.

В данной работе рассматривается задача оценивания нестационарной регрессии в случае, когда по условию решаемой прикладной задачи на искомую последовательность векторных параметров нестационарной модели сигнала X = (х,,( = 1,.,/V) наложены линейные ограничения в виде линейных равенств и неравенств.

Вообще говоря, задача минимизации квадратичной целевой функции с линейными ограничениями, охватывающими сразу все переменные, является классической задачей квадратичного программирования. Для решения общей задачи квадратичного программирования существует множество численных методов - симплекс-метод, метод наискорейшего спуска и др. [32, 33, 34, 47, 52, 53] - имеющих полиномиальную вычислительную сложность относительно числа переменных N.

Заметим, что общая задача квадратичной оптимизации без ограничений также имеет полиномиальную вычислительную сложность относительно числа векторных переменных, которая снижается до линейной в случае парной сепарабельности целевой функции. Однако в обоих случаях наложение линейных ограничений на все переменные в совокупности приводит к задаче квадратичного программирования общего вида, причем нет методов, позволяющих использовать факт парной сепарабельности целевой функции для снижения полиномиальной вычислительной сложности задачи.

В данной работе рассматривается частный случай задачи оценивания' нестационарной регрессии с линейными ограничениями на искомые коэффициенты, характерный для многих приложений, когда ограничения сводятся к последовательности ограничений на отдельные векторные переменные х, eR\ t = 1,.,/V :

A,х, +с, >0,.

B,х,+f,=0

Задачу минимизации квадратичной парно-сепарабельной целевой функции с ограничениями типа в данной работе предлагается называть задачей парно-сепарабельного квадратичного программирования.

Для задач этого типа в диссертации предлагаются два алгоритма решения, обладающие линейной вычислительной сложностью относительно числа векторных переменных N . Оба алгоритма существенно используют процедуру динамического программирования для минимизации парно-сепарабельных квадратичных функций без ограничений, рассмотренную в работах [17, 20, 21, 31] и основанную на рекуррентном пересчете параметров квадратичных функций Беллмана.

Теоретически, линейная вычислительная сложность алгоритма оптимизации по числу переменных квадратичной парно-сепарабельной целевой функции при наличии индивидуальных ограничений на переменные обеспечивается прямым применением процедуры динамического программирования. Однако численная реализация такой процедуры для непрерывных переменных оказывается затруднительной, поскольку, как показано в диссертации наличие неравенств в ограничениях выводит очередную функцию Беллмана из конечно-параметрического семейства квадратичных функций, даже если предположить, что предыдущая функция Беллмана квадратична.

Первый алгоритм, предлагаемый в данной работе, построен по итерационному принципу и реализует метод наискорейшего спуска, применяемый для решения двойственной задачи. Наиболее сложным в вычислительном отношении шагом такого алгоритма является вычисление на каждой итерации очередного градиента двойственной целевой функции. Алгоритм эксплуатирует тот факт, что искомый градиент определяется точкой минимума функции Лагранжа по целевым переменным Х = (хп t = \,.:,N) без ограничений при фиксированных значениях множителей Лагранжа, полученных на предыдущей итерации, причем функция Лагранжа квадратична и парно-сепарабельна. В силу этого обстоятельства точка ее минимума может быть найдена процедурой квадратичного динамического программирования, эквивалентной процедуре прогонки, за число операций, пропорциональное числу переменных А . Таким образом, по своей вычислительной сложности итерационный алгоритм решения задачи минимизации парно-сепарабельной функции с индивидуальными ограничениями на векторные переменные сводится к многократному применению процедуры динамического программирования с линейной вычислительной сложностью для решения аналогичной задачи без ограничений, причем число повторений равно числу итераций.

Однако существует класс вариационных задач анализа нестационарных сигналов, алгоритмическое решение которых связано с необходимостью многократного определения оптимального значения целевой переменной в отдельно взятой точке оси аргумента при разных моделях сигнала без пересчета оптимальных значений в других точках. Это такие задачи, как, например, задача обнаружения нарушений гладкости изменения оцениваемого параметра, задача оценивания дисперсии шума наблюдения в модели нестационарной регрессии, задача подбора класса нестационарной модели и т.д. [35, 36, 37, 38] Таким образом, объем вычислений возрастает пропорционально квадрату длины сигнала /V2, в то время как оценивание последовательности векторов коэффициентов регрессии с помощью метода наискорейшего спуска требует объема вычислений, пропорционального лишь длине сигнала N . Эффективные алгоритмы решения таких задач не могут быть построены в рамках метода наискорейшего спуска.

Второй алгоритм, предлагаемый в данной работе, представляет собой приближенную реализацию процедуры динамического программирования вперед и навстречу» для случая с ограничениями, позволяющую решать обозначенные выше задачи за два прохода сигнала с числом операций, про

12 порциональным его длине N. Этот алгоритм не является итерационным и эквивалентен однократному применению процедуры динамического программирования, имеющей линейную вычислительную сложность, но на каждом шаге рекуррентного пересчета вместо точной функции Беллмана, не являющейся квадратичной, он использует квадратичное приближение к ней в малой окрестности точки ее минимума. В силу такой эвристической замены алгоритм не дает, строго говоря, точного решения задачи парно-сепарабельного квадратичного программирования, но многочисленные эксперименты свидетельствуют о достижении хорошего приближения к точке минимума целевой функции.

Разработанные вариационные алгоритмы восстановления нестационарной регрессии использованы в диссертации для построения программно-алгоритмического комплекса анализа экономических данных восстановления структуры портфеля инвестиционной компании.

Диссертация состоит из шести глав. В первой главе рассмотрены примеры типовых задач анализ сигналов, являющие частными случаями задачи восстановления нестационарной регрессии и приводящие к необходимости решения задачи парно-сепарабельного квадратичного программирования с ограничениями, сформулированы основные задачи исследования. Во второй главе предлагается процедура решения задачи парно-сепарабельного квадратичного программирования, линейная по числу векторных переменных и опирающаяся на известный метод решения задач квадратичного программирования - метод наискорейшего спуска. В третьей главе показывается невозможность непосредственного применения метода прогонки и процедуры динамического программирования для решения задачи парно-сепарабельного квадратичного программирования. Предлагается приближенная реализация процедуры динамического программирования «вперед и навстречу» для случая с ограничениями, основанная на замене в каждый момент времени неквадратичных фикций Беллмана квадратичными. В четвертой главе разработанный. приближенный алгоритм применяется для построения алгоритма сглаживания сигналов с автоматическим подбором степени сглаживания и сохранением локальных особенностей исходного сигнала. В пятой главе проводится экспериментальное исследование предложенных алгоритмов на предмет точности и быстродействия. Показывается, что при применении приближенного метода динамического программирования не происходит сколько-нибудь существенной потери качества. Кроме того, показано, что этот метод обеспечивает более высокое быстродействие по сравнению с методом наискорейшего спуска, т.к. находит решение задачи за один цикл работы процедуры «вперед и навстречу». В то время, как в методе наискорейшего спуска количество применений процедуры «вперед и навстречу» пропорционально числу итераций

6 Основные выводы

1. Дана формальная постановка обобщенной задачи анализа широкого класса нестационарных сигналов как задачи парно-сепарабельного квадратичного программирования.

2. Разработан асимптотически точный итерационный метод решения задачи парно-сепарабельного квадратичного программирования, основанный на методе наискорейшего спуска, использующий на каждой итерации метод прогонки и имеющий линейную вычислительную сложность относительно числа векторных переменных.

3. Разработан неитерационный алгоритм решения задачи парно-сепарабельного квадратичного программирования, на основе приближенной реализации процедуры динамического программирования.

4. Разработан алгоритм оценивания параметров нестационарной модели сигнала с сохранением его локальных особенностей с помощью применение приближенной процедуры динамического программирования.

5. Разработан алгоритм определения требуемой степени сглаживания при оценивании нестационарной модели сигнала на основе метода скользящего контроля с применением приближенной процедуры динамического программирования.

6. Исследована вычислительная сложность предложенных алгоритмов анализа нестационарных сигналов и показана, что она является линейной относительно длины сигнала.

7. Экспериментально исследована точность приближенной реализации метода динамического программирования при оценивании нестационарных моделей сигналов. Показано, что не происходит сколько-нибудь существенной потери точности при применении приближенного метода динамического программирования по сравнению с точными методами квадратичного программирования.

1. Яковлев В.Г. Алгоритм выделения всплесков на физиологических кривых.

2. Автоматика и телемеханика. 1977. №12. С. 94-105

3. Джайн А.К. Успехи в области математических моделей для обработки изображений. // ТИИЭР. 1981. Т.69. №5, С. 9-39.

4. Кокс Дж. Р., Нолл Ф.М., Артур Р.М, Анализ электроэнцефалограмм, кривых кровяного давления и электрокардиограмм на цифровой вычислительной машине.//ТИИЭР. 1972. Т. 60. № 10. С. 36-73.

5. Савараги Е., Соэда Т., Накамизо Т. «Классические» методы и оцениваниевременных рядов. /7 В кн.: Современные методы идентификации систем. / Под ред. П. Эйкхоффа. М.: Мир,1983.

6. Bellman R. On the approximation of curves be line segments using dynamic programming. //Comm. ACM. 1961. V. 4. №6. P.284.

7. Моттль В.В., Яковлев В.Г. Оценивание повторяющихся значений параметров случайного процесса с многократно изменяющимися свойствами. // Статистические проблемы управления. // Вып. 65. Вильнюс: Институт математики и кибернетики АН ЛитССР, 1984. С. 135-145.

8. Rabiner L. Juang D.Y. Fundamentals of Speech Recognition. N. Y. 1993.

9. Hamilton J. Time Series Analysis. // Princeton University Press, 1994.1 1 Дрейпер H.A., Смит Г. Прикладной регрессионный анализ. М.: Статистика, 1973.

10. Моттль В.В., Мучник И.Б. Лингвистический анализ экспериментальных кривых. // ТИИЭР. 1979. Т. 67. № 5. С. 12-39

11. Мучник И.Б., Мучник Р.Б. Алгоритмы формирования языка для описания экспериментальных кривых. // Автоматика и телемеханика. 1973. №3. С 86-96.

12. Рабинер Л. Скрытые марковские модели и их применение в избранных приложениях при распознавании речи: Обзор. // ТИИЭР. 1989. Т. 77. № 2. С. 86-120.

13. Page Е. S. Continuous inspection schemes. // Biometrica, 1954. V. 41. P. 100114.

14. Pavlidis T. Linguistic analysis of waveforms. // In: Software Engineering. /Ed. J.T. Tou. V.2.-NY: Academic Press, 1971. P. 203-225.

15. Mottl V.V., Blinov А.В., Kopylov A.V., Kostin A.A. Computer-aided signal and image processing: A universal variational approach. Journal of Journals: Review of Global Scientific Achievements, 1998, Vol. 2, No. 1, pp. 23-30.

16. Буробин H.B., Моттль В,В, Алгоритмы оптимальной регистрации событий в реальном времени.//Автоматика и телемеханика. 1987. №2, С. 119-128.

17. Mottl V., Blinov A., Kopylov A., Kostin A., Muchnik I. Variational methods in signal and image analysis. Proceedings of the 14th International Conference on Pattern Recognition. Brisbane, Australia, August 16-20, 1998. Volume 1, pp. 525-527.

18. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. Киев: Наукова думка, 1987. 262 С.

19. Немирко А.П. Цифровая обработка биологических сигналов. М.: Наука,1984.- 145С

20. Mottl V., Kopylov A., Kostin A. Edge-preserving in generalized smoothing of signals and images. Proceedings of the 14th International Conference on Pal-tern Recognition. Brisbane, Australia, August 16-20, 1998. Volume Ii, pp. 1579-1581

21. Беллман P., Калаба P. Динамическое программирование и современная теория управления. М.: Наука, 1969, -1 18.

22. Sniedovich М. Dynamic Programming. Marcel Dekker, NY, 1991

23. Коган И.А. Оптимальная сегментация структурных кривых на основе метода динамического профаммирования. // Автоматика и телемеханика, 1988, № 7, с. 146-156.

24. Моттль В.В., Мучник И.Б. Сегментация структурных кривых на основе метода динамического программирования. // Автоматика и телемеханика. 1985, №1, с. 101-108.

25. Моттль В.В., Костин А.А., Красоткина О.В., Копылов А.В. Алгоритмы динамического программирования для оценивания моделей нестационарных сигналов. Доклады X Всероссийской конференции ММРО-Ю, Вычислительный центр РАН, Москва, 2001г.

26. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983

27. Сеа Ж. Оптимизация. Теория и алгоритмы. М.: Мир, 1973.

28. Зангвилл У. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973.

29. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. -М.: Наука,1976.

30. Никифоров И.В. Последовательное обнаружение изменения свойств временных рядов. М: Нука, 1983. 199 с.

31. Basseville V. Espiau В. Edge detection using sequential methods for change in level. Parts I, II. // IEEE Trans, on ASSP 1981 V.ASSP-29 №1

32. Яковлев В.Г. О выборе порогов для разладочного алгоритма сегментации экспериментальных кривых. // Автоматика и телемеханика. 1983. №9, С.95-101.

33. G. Box and G. Jenkins. Time Series Analysis. Forecasting and Control. Hol-den-Day, 1970.

34. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление. Вып. 1,2. М.: Мир, 1974.

35. Harry М. Markowitz, Portfolio Selection, Journal of Finance, 7, no. 1 (March1952), pp. 77-91

36. Уильям Ф. Шарп, Гордон Дж. Александер, Джеффри В. Бейли, Инвестиции: Пер. с ан'л. М.: ИНФРА-М, 2003.

37. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977.

38. R. Fletcher. Practical Methods of Optimizations. John Wiley and Sons Inc. 2nd edition, 1987.

39. Базара M., LLk ти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982

40. Mikael Adlers. Sparse Least Squares Problems with Box Constraints. Division on Numerical Analysis. Department of Mathematics. Linkopings universitet.

41. Численные jui поды условной оптимизации, под ред. Ф Гилл, У. Мюрей, М.: Мир, 1977.

42. R. Bellman. Dynamic Programming. Princeton University Press, Princeton, N.J., 1957.

43. Robert Kalaba, Leigh Tesfatsion. A Multicriteria Approach To Model Specification and Estim. tion. 1SU Economic Report №28. 6 January 1995

44. N.D. Sidiropou'os and R.Bro Mathematical Programming Algorithms for Re-gression-based Nonlinear Filtering in R' .

45. Бахвалов H.C., Жидков Н.П., Кобельков Г.М. Численные методы М.: Лаборатория Разовых Знаний, 2001.

46. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988г.

47. Алексеев О.Г., Алексеев А.О., Киселев В.Д., Мировицкий ГюПю Применение двойст енности для повышения эффективности метода встречного решения фун циональных уравнений динамического программирования. // Кибернетика. 1990. №1.

48. Киселев В.Д., Алексеев А.О. Упорядочение ограничений в методе встречного решенш функциональных уравнений динамического программирования.//Эко! (мико-математические методы. 1994. №4.

49. Киселев В.Д., Сукманов С.А. Применение двойственности для решения задача целочисленного квадратичного программирования о ранце. Журнал вычислительной математики и математической физики. 1993. Т. 33. №2.

50. Pitas I., Venebanopoulos A.N. Nonlinear Digital Filters. Principles and Applications. Boston: Kluwer Academic Publishers, 1990.

51. Niedzwiecki M., Sethares W.A. Smoothing of discontinuous signals: The competitive a' oroach. IEEE Trans, on Signal Processing, Vol. 43, No. 1, January 1995, ,>p. 1-13.

52. Andersen E. L ., Ye Y. A computational study of the homogeneous algorithm for large-scale convex optimization. Computational Optimization and Applications, 10:243-269, 1998.

53. Список публикаций по теме диссертации

54. Моттль В.В., Копылов А.В., Костин А.А. Красоткина О.В. Алгоритмы динамического программирования для оценивания моделей нестационарных сигналов. Доклады X Всероссийской конференции ММРО-Ю. Вычислител чый центр РАН, Москва, 2001 г,-С. 345-349.

55. Красоткина О.В. Алгоритмы парносепарабельного программирования взадачах анализа нестационарных сигналов. Доклады X Всероссийской конференции ММРО-Ю, Вычислительный центр РАН, Москва, 2001 г.

56. Mottl V.V., Kopylov А.V., Krasotkina O.V. A quadratic programming problem for elastic image matching. Proceedings of IASTED international conference Automation, Control and Information Technology, June 10-13, 2002, Novosibirsk.

57. Krasotkina O. 7., Mottl V. V., and Kopylov A. V. Algorithms of Estimation of

58. Nonstationar Regression in Signal Analysis. Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003, pp. 127-131.