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

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

ЛЕ Ньят Зюи

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

05.13.17 - теоретические основы информатики

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

2 6 ДПР Ш

Москва —2012

005019691

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

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

Горелик Виктор Александрович

Цурков Владимир Иванович

доктор физико-математических наук, профессор, заведующий отделом сложных систем Вычислительного центра им. A.A. Дородницына РАН.

Кондратьева Виктория Александровна

кандидат физико-математических наук, доцент кафедры «Информационные системы и дистанционные технологии» факультета «Автоматизация и управление Московского государственного технического университета «МАМИ».

Ведущая организация: Московский государственный университе

им. М.В. Ломоносова.

Защита диссертации состоится «21» мая 2012 г. в 17 часов на заседай диссертационного совета Д 212.154.32 при Московском педагогическо государственном университете по адресу: 107140, г. Москва, ул. Краснопрудна д. 14, математический факультет МПГУ, ауд. 401.

С диссертацией можно ознакомиться в библиотеке Московско! педагогического государственного университета по адресу: 119991, г. Москва, у Малая Пироговская, д. 1.

Автореферат разослан « 13 » апреля 2012 г.

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

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

Ученый секретарь диссертационного совета

Муравьева Ольга Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Традиционно было принято рассматривать только такие задачи, в которых истема соотношений является непротиворечивой. Однако практика решения рикладных задач (экономических, технических и др.) показала, что моделирование ложных процессов и явлений - многошаговая процедура. При этом первоначальное писание (математическая модель) объекта, представляющее собой систему равнений, неравенств и других соотношений, связывающих параметры или арактеристики объекта, может быть противоречивым, т.е. соответствующая истема может не иметь решений, может быть несовместной. Эта несобственность противоречивость) модели может быть вызвана неточностью данных, чрезмерным прощением действительных связей, абсолютизацией некоторых требований и .ругими причинами. Более того, противоречивая модель может быть адекватным тражением действительных противоречий, а способы ее корректировки — ¡тражением действительных процедур разрешения реальных противоречий. В этих лучаях на последующих шагах "отладки" модели предпринимаются те или иные [роцедуры корректировки или уточнения соотношений модели и ее структуры. 1ротиворечивость можно считать одним из факторов плохой формализуемости. Существуют различные причины плохой формализуемости задачи выбора решения I моделях оптимизации, среди которых можно назвать:

— плохую определенность ограничений и критериальных функций;

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

— неточность информации;

— переопределенность требований.

В связи с этим возникла необходимость развития теории таких модели" методов их коррекции, алгоритмического и программного обеспечения.

В 1993 году появилась публикация американского математика профессор Дж.Б. Розена (J.b.Rosen) с учениками, послужившая началом развития новог научного направления - Structured Total Least Norm Approach. В этой работе был впервые поставлена и решена задача структурной коррекции переопределенно системы. Рассматривалась СЛАУ вида Ах = Ъ, в которой вектор правой части Ъ содержит неточные данные (ошибки измерения), левая часть системы - матрица А — задана неточно в силу недостаточной априорной информации. Кроме тоге матрица А обладает определенной структурой.

Параллельно с зарубежными исследованиями аналогичные работы, по с упором н несобственные задачи математического программирования (ЗМП), проводились и России научной школой Института математики и механики УрО РАН под руководство] академика РАН И.И. Еремина (A.A. Ватолин, В.Д. Мазуров, Л.Д. Попов и др.), впоследствии и научной группой Вычислительного центра им. A.A. Дородницына РА] и МПГУ под руководством В.А. Горелика (В.И. Ерохин, ВА. Кондратьева, О.Е Муравьева, P.P. Ибатуллин, Р.В. Печенкин и др.).

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

В работах В.А. Горелика, В.И. Ерохина, Р.В. Печенкина осуществлено развита подхода структурной коррекции к несовместным СЛАУ с матрицами специальноп вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимально]" коррекции по квадратичному и минимаксному критериям. Получен метод решени задачи оптимальной матричной коррекции несовместных систем линейны алгебраических уравнений, обладающих блочной структурой, с использование! квадратичного и минимаксного критериев. Сформулирован критерий оптимально" коррекции несовместной системы с матрицей Теплица и Вандермонда при наличш ошибок только в левой части и предложен метод коррекции с использование! штрафных функций норм векторов невязок. В работах В.А. Горелика, O.A. Клименко рассмотрена задача коррекции данных несовместных линейных систм комбинаторного типа. Предложен метод решения задачи оптимальной коррекци] несовместных систем линейных уравнений и неравенств комбинаторного типа i использованием квадратичного и минимаксного критериев. Для обоих критерие: разработаны алгоритмы коррекции с учетом структуры задачи. Рассмотрен! приложение матриц и систем комбинаторного типа и их коррекции в задача; распознавания на примере задачи кластеризации.

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

коррекции несовместных систем линейных алгебраических уравнений и неравенств и несобственных задач линейного программирования общего вида. Они характеризуются дополнительными ограничениями на матрицу коррекции. В большинстве исследований исходная задача матричной коррекции данных сводится к некоторой задаче математического программирования. Исключениями могут служить работы В.А. Горелика, В.И, Ерохина, Р.В. Печенкина, И.А. Золтоева, в которых намечаются подходы к разработке соотвествующих численных методов и алгоритмов матричной коррекции данных на основе TLN (Total Least Norm -алгоритм обобщенной наименьшей нормы) и метода Ньютона.

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

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

Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.

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

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

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

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

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

2. Разработку методов матричной коррекции несовместных систем линейных уравнений и неравенств, обладающих блочной структурой.

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

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

5. Применение методов коррекции систем блочного типа к задачам обработки информации.

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

• Постановки новых задач коррекции несовместных систем линейных алгебраических уравнений и неравенств с блочной структурой.

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

• Алгоритмы, реализующие разработанные методы.

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

Проведенные вычислительные эксперименты показывают работоспособность предлагаемых методов и алгоритмов.

Основные положения, выносимые на защиту:

• Формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами блочного типа при наличии ошибок в данных обеих частей системы;

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

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

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

1. На научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010 г.,

2. На всероссийской конференции «Математика, информатика и методика их преподавания». Москва, 2011 г.,

3. На научно-практической конференции молодых ученых «Интеграция научных исследований в рамках реализации приоритетных направлений науки», МПГУ (Москва, 2011г.),

а также на научно-методических семинарах кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета и отдела Имитационных систем и исследования операций Вычислительного центра им. A.A. Дородницына РАН.

Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 6 печатных работах, из них 3 статьи в журналах включенных в перечень ВАК РФ [1-3], 1 статья в сборнике ВЦ РАН [4], 2 статьи в сборниках конференций [5, 6].

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы, содержащего 104 источников. Объем диссертации составляет 72 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации, определяется цель работы, выдвигается гипотеза, положенная в основу исследования, формулируются задачи, которые необходимо было решить для реализации поставленной цели и проверки выдвинутой гипотезы, указывается методологическая основа исследования, раскрывается научная новизна и практическая значимость диссертационной работы, выдвигаются основные положения, выносимые на зишиту, представлено основное содержание работы.

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

Рассмотрим задачу матричной коррекции несовместных систем линейных алгебраических уравнений

Ах = Ь, х ä 0

и задачу коррекции несовместных систем неравенств

Ах<Ь,

где матрица А е R""" имеет следующую блочную структуру:

А

А 0 0

А = 0 А2 0

0 0 АК.

Лей"' <пк > к=1. л, к *=0

Л еЛ™

Введем в эти задачи дополнительные требования совместности А0х = Ь„, х>0 и А0хх>0 и неизменимостиматрицы А0.

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

Задача 1.1. Требуется найти матрицы Нк е л1"«""* > такие, что система

А

А,+ Я, О О А, + Н, ■•.

О Аг + НГ

Ли

имеет неотрицательное решение и выполнено требование минимальности сум квадратов евклидовых норм матриц коррекции

к

№1

Задача 1.2. Требуется найти матрицы Нк е Л™'""', такие, что система

Л,+Я, О О а2 + Н2

О

(2)

имеет неотрицательное решение и выполнено условие

К

->т!п.

Задача 13. Требуется найти матрицы Нк е и векторы Ик е Ящ, такие, что система

4.

Л,+Я,

О

Рк +ЬК.

(3)

имеет неотрицательное решение и выполнено условие

4-1

Задача 1.4. Требуется найти матрицы Нк е Л*'™' и векторы Нк е Д"*, такие, что система

А,+ Я, О

о

о

О Аг+Нг

[А

имеет неотрицательное решение и выполнено условие

»>1

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

Рассмотрим коррекцию задачи 1.1. Систему (1) при фиксированном * можно переписать как совокупность К систем линейных алгебраических уравнений с неизвестной матрицей Нк:

(Ак+Нк)хк=Ьк о Нкхк =Ък-Акхк. (5)

Единственным решением уравнения (5) относительно неизвестной матрицы Нк, обладающим минимальной евклидовой нормой при х„ ф 0 будет матрица

К={ьк~Акхк)х;, (6)

где х*к — псевдообратный вектор-строка к вектору хк.

При использовании взвешенной евклидовой нормы (квадратичный критерий) будет справедлива формула

1

Теорема 1.1. Задача

коррекции 1.1 эквивалентна задаче математического

программирования вида:

(7)

1**1

к

хк ¿0, к = \,...,К,

а именно, если (хк,/'(х')) - решение задачи (7), то матрицы коррекции Н'к вычисляются по формуле (б).

Задача 1.3 — поиск оптимальной расширенной матрицы коррекции, путем аналогичных преобразований может быть сведена к аналогиной задаче МП. Теорема 1.2. Задача коррекции 1.3 эквивалентна задаче математического программирования вида:

^ЬХ^ТГ-*11™. (8)

ы Ы1

к _ __ »-1

г, 2:0, к = \,...,К,

где

бЛГ', Л=к,|... Аок], AikeR^,

eb0 = b0+K-1„ еГ,

а именно, если {z\,g{z)) - решение задачи (8), то расширенные матрицы коррекци: Fi ~К\ вычисляются по формуле

[я; -hl]=-Akzkzl.

Обратимся к исследованию задачи 1.2, систему неравенств (2) перепишим как К систем линейных неравенств

{Ak+Hk)xk <,bk. (9)

Вводя дополнительные переменные yk, Ук >о, к = К, из (9) можно записать следующие равенства

(Ak+Hk]xk+yk=bk^Hkxk = bk- ук -Акхк, Ук> 0. (ю)

При фиксированном векторе xkeR"' решение (ю) относительно неизвестной

матрицы Нк, обладающее минимальной евклидовой нормой существует при любом хк * 0 и задается формулой:

н>{ьк-Ахк-уМ, (п)

причем

11 4,1 Ы ■

Теорема 1.3. Задача коррекции 1.2 эквивалентна задаче математического программирования вида:

t-1 Ix. 'Л

(12)

ZAa

<№1

х„1>0, ук> 0, к = \,...,К, а именно, если {х],у'к,(р'{х ,у)) - решение задачи (12), тогда матрицы коррекции Н'к вычисляются по формуле (11).

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

программирования вида:

Пх>У)-£,-., ||2 , -—>шш, (13)

к k-1

yk ¿0, k = \,...,K,

а именно, если [x'k,y't,i/y'(x' ,y')) - решение задачи (13), тогда расширенные матрицы

коррекции [//t" -h'k ] вычисляются по формуле

[я; -h;]={bk-AkXk-ytyk.

Рассматриваются оба подхода для коррекции несовместных систем неравенств

с блочной структурой. Для подхода «сверху-снизу» приведены формулы первых

производных оптимизируемой функции задач (12), (13).

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

Задача 2.1. Требуется найти матрицы Hk е Rmt""k t такие, что система (l) имеет неотрицательное решение и выполнено условие

где h' - элемент матрицы коррекции Нк.

Задача 2.2. Требуется найти матрицы Нк sä™**"' и векторы hk е R"'k, такие, что система (3) имеет неотрицательное решение и выполнено условие

тах У aJI min,

^..jcffl |

где hl - элемент расширенной матрицы коррекции [нк -ht].

Задача 2.3. Требуется найти матрицы Нк е RWk""k; такие, что система (l) имеет неотрицательное решение и выполнено условие

ElKbmin. t-i ij

Задача 2.4. Требуется найти матрицы Нк е Rm''"k и векторы hk е R""1, такие, что система (з) имеет неотрицательное решение и выполнено условие

К

ij

Задача 2.5. Требуется найти матрицы Нк е R"1'"'; такие, что система (2) имеет неотрицательное решение и выполнено условие

Задача 2.6. Требуется найти матрицы Ht е Rm,*"k и векторы \ е R"1, такие, что система (4) имеет неотрицательное решение и выполнено условие

Задача 2.7. Требуется найти матрицы НкеЯщ'"к, такие, что система (2) имеет неотрицательное решение и выполнено условие

к

max А* -> min.

t.i

Задача 2.8. Требуется найти матрицы Нк е Л™'""' и векторы hk е Rmt, такие, что система (4) имеет неотрицательное решение и выполнено условие

V max Aj, -> min.

tt и I I

При решении задач минимаксной коррекции часто используются векторные нормы II,, IL и гельдеровы нормы ||j|(i, |[|( , с использованием которых они

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

Теорема 2.2. Задача коррекции 2.1 эквивалентна задаче математического программирования вида:

d min, (l4)

äs,У

vt >bkrk-Akyk, k-1

vt>0, QSykZ\,y[ =1, -vt üd, l=\,...,nk, k= 1.....K,

где r" =-—T, rk >0, yk = r"xk, k = \,...,K,

max xk

а именно, если (¿V,у'к) - решение задачи (14), то х'к = Уук- и матрицы коррекции н'к вычисляются по формуле

Н'к=(ьк-Акхкук, (15)

- вектор, двойственный к вектору хк относительно нормы Щ,.

Теорема 23. Задача коррекции 2.2 эквивалентна задаче математического программирования вида:

а-)тш, (1б)

"л.р

<тк> 0, 0^<;1, р[= 1,

1 = \,...,пк +1, * = 1.....К,

х,

=

где Ак=[Ак -¿>4]еЛт'х("'+1),

Я* =k ije****0, еЛ\

6ДГ', q* =-i—, if >0, рк=2кЧ\

max zt

а именно, если (u',qk',p'k) - решение задачи (16), тогда z'k = рук. и расширенные

/ Я

матрицы коррекции [я4* -h'k \ вычисляются по формуле

[я; -h't]=-AkzkW;, (17)

wk — вектор, двойственный к вектору zk относительно нормы ||

Описывается метод декомпозиции на основе метода распределения ресурсов для решения задачи (16). Схему метода декомпозиции можно описать следующим образом.

Введем в рассмотрение К новых векторов tk, tk е Rm", к = 1.....К.

= '*?*> * = 1.....К,

К _

= V

к' 1

При фиксированных значениях векторов tk, процесс декомпозиции на каждом шаге приводит к решению К локальных задач:

ик —> min, (18)

^ * АРк. ак ^~АкРк,

<rt*0, р'к =1, / = 1.....пк +1.

Здесь вводятся новые переменные ик, соответствующие tk.

Задача (18) при фиксированном 1 является задачей линейного программирования (ЗЛП), т.е. ее решение сводится к нахождению минимума из минимумов ЗЛП при / = 1.....пк +!•

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

max ut[/]- min

*=1Г..,Л *=!,.. „Л

где / — номер итерации, а с — заданная точность.

Теорема 2.4. Задача коррекции 2.3 эквивалентна задаче математического программирования вида:

К

Z(*t>vt)->min, (19)

V, ¿Ькгк-Лкук,

vk +Лл»

1 = \,...,пк, к = \,...,К.

Здесь ек - вектор-столбец размерности тк, состоящий из единиц, а именно, если {у'кУ ,у'к) - решение задачи (19), то х'к и матрицы коррекции

Н\ вычисляются по формуле (15).

Теорема 2.5. Задача коррекции 2.4 эквивалентна задаче математического программирования вида:

К

Х^'^О-^пип, (20)

^ Лл.

к-1

оч>о, о<Рка, Р[= 1, 1=1,...,пк +1, * = 1.....К,

а именно, если {<т1,дк',р'к) ~ решение задачи (20), тогда г'к = и расширенные

матрицы коррекции [н'к - вычисляются по формуле (17).

Граница существования решения задач минимаксной коррекции СЛАУ определяется следующей теоремой.

Теорема 2.6. Задачи 2.1-2.4 не имеют решения, если существует вектор гей", 2 > 0, такой что выполняется условие

Лг = 0.

Доказываются теоремы, которые показывают, что решение задач коррекции систем неравенств 2.5-2.8 эквивалентно решению задач условной минимизации (в том числе к серии задач линейного программирования).

Теорема 2.7. Задача коррекции 2.5 эквивалентна задаче математического программирования

и -> тш (21)

и * '

при ограничениях

к

0, хк £0, ук >0, к = \,...,К, а именно, если (и',х'к,у'к) - решение задачи (21), то матрицы коррекции Н'к вычисляются по формуле

где хк - вектор, двойственный к вектору хк относительно нормы Ц^.

Зафиксируем и = и > 0 достаточно большим, чтобы обеспечить выполнимость ограничений задачи (21). Тогда решение и <.й задачи (21) может находиться методом одномерной минимизации на отрезке [о,й]. При этом на каждом шаге итерации проверяем совместность ограничений задачи (21), что эквивалентно решению ряда вспомогательных задач линейного программирования:

el ■ хк -> max, (22)

hU

хк1и0, ук£0, к = 1,...,К, где ск - вектор-столбец размерности пк, состоящий из нулевых, и - фиксированные значения из отрезка [о,и].

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

(23)

Сформулируем К задач линейного программирования:

с, х^ max,

Ал - h >

-и-\щ +Ак -и-1„( -Ак

' Ьк-у„

г(Ь1~УЛ

(24)

хк*0, ук> 0.

Введем вектор / = (г,,...,^) и М, - множество векторов г таких, что выполняется (23) и задачи (24) имеют решения.

Обозначим через М*у, к = \,...,К — ограниченные многогранники в пространствах К"':

1?-

Ку ■

Введем функцию Лагранжа

-"'V^+A -А,

Г

xk,yk>0

к

L{x,t,X)=^(Xt,tk -A0kxk),

где хк еМ,^, Як еЯ"', к = \,...,К.

Выбираются значения Я и /, Я,1 еЯ? - границы изменения переменных Як, !к, 0<Я4 йЯ, ¿1, к = \,...,К.

Введем два множества М, и Пд:

М, = |/|-/£/<;г, Е'*^}.

=[г|0<^ ¿1, Аг е [1: А:]}

и функционал <p(t,A) вида

к к

<р(г,Л) = max maх(-Л„Аок,хк).

ы\ k-1

Итак, имеем задачу о нахождении седловой точки функции <p(t,X)\

m]p <p{t, Л) max, teM,. (25)

Л«Пл v 1

Задача (25) может решаться методом фиктивной игры. Тогда первый (минимизирующий) игрок на каждом шаге итеративного процесса решает задачу

К _

min, t е Mi, (26)

где Лк — фиксированы.

Задача (26) может быть представлена как т0 независимых подзадач:

teM,, 1б[1:и0],

к=1

где Л'к — фиксированы.

Второй (максимизирующий) игрок в процессе итераций решает следующую

задачу:

ск • хк -» max,

Л|А ^ 1к >

(27)

~и '1 +Ак т* "к *

-и-1 -i: ~At

ьк-Ук

ук £0,

где (, — фиксированы.

Задача (27) рассматривается как К независимых подсистем. Таким образом, указанный подход осуществляет декомпозицию задачи (22) на К + т0 подзадач, имеющих меньшие размерности.

Теорема 2.8. Задача коррекции 2.6 эквивалентна задаче математического программирования

и -> шп (28)

при ограничениях

-" • 1„,(1Г,хк+\)<,Ък-ук-Акхк, )*Ък-Ук-Акхк,

к

и 2; О, хк £0, ук >0, к = 1,...,К, а именно, если (и',х^,у;) - решение задачи (28), то расширенные матрицы коррекции [я; -Л*] вычисляются по формуле

где wk — вектор, двойственный к вектору

относительно нормы

Теорема 2.9. Решение задачи 2.7 может быть получено из решения задачи математического программирования следующего вида:

1ТК - и -» min

при ограничениях

n,r(llxk)^bk-yk-Akxk, к

Y,Aokxk^h>

И-1

хк,у„>0, к = \,...,К,

и = (и.....,Ugf eRK, и> 0.

Теорема 2.10. Решение задачи 2.8 может быть получено из решения задачи математического программирования следующего вида:

•и -»min

при ограничениях

-Щ ■ L, ■ fc,х„+\)ibk-yk-Akxk, к

-^0kXk ^ >

4-1

x^SiO, k = \,...,K, и = 6 RK , »i0.

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

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

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

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

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

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

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

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

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

Основное содержание диссертационной работы отражено в следующих публикациях:

1. Горелик В .А., Ле Ньят Зюи. Метод декомпозиции в задачах минимаксной коррекции несовместных систем уравнений с матрицами блочной структуры // Вестник Тверского государственного университета. Серия: Прикладная математика, 2011. № 4. С. 83-92. - 0.7 п.л. (авторский вклад -50%).

2. Ле Ньят Зюи. Метод декомпозиции в задачах коррекции несовместных систем линейных неравенств с матрицами блочной структуры // Журнал вычислительной математики и математической физики, 2011. Т. 51. № 10. С. 1796-1805.-0.5 п.л.

3. Ле Ньят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры по минимаксному критерию // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика, 2011. № 4. С. 18-25. -1,1 п.л.

4. Горелик В.А., Ле Ньят Зюи. Некоторые результаты по проблематике коррекции несовместных систем уравнений и неравенств с матрицами блочной структуры // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М.: ВЦ РАН, 2011. С. 51-67. - 0,8 п.л. (авторский вклад - 50%).

5. Горелик В.А., Ле Ньят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры // Сборник материалов научно-практической конференции министерства высшего и среднего специального образования Республики Узбекистан. Ташкент, 2010. С. 342-353. - 0,8 п.л. (авторский вклад - 50%).

6. Ле Ньят Зюи. Коррекция несовместных систем линейных неравенств с матрицами блочной структуры по минимаксному критерию // Сборник материалов Всероссийской конференции «Математика, информатика и методика их преподавания». М.: МПГУ, 2011. С. 66-68. - 0,2 п.л.

Подп. к печ. 09.04.2012 Объем 1 п.л. Зак. № 89 Тир. 100 экз.

Типография МПГУ

61 12-1/801

МОСКОВСКИЙ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

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

ЛЕ Ньят Зюи

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

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

ДИССЕРТАЦИЯ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

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

доктор физико-математических наук, профессор ГОРЕЛИК В.А.

Москва-2012

Содержание

ВВЕДЕНИЕ............................................................................................................4

ГЛАВА 1. Коррекция и декомпозиция несовместных блочных систем линейных алгебраических уравнений и неравенств с квадратичными критериями........................................................14

1.1. Постановки задач блочной коррекциии ..................................................14

1.2. Коррекция и декомпозиция несовместных блочных СЛАУ..................20

1.3. Коррекция несовместных систем неравенств.........................................25

1.4. Выводы к первой главе .............................................................................35

ГЛАВА 2. Коррекция и декомпозиция несовместных блочных СЛАУ и

неравенств с минимаксными критериями ...............................36

2.1. Постановки минимаксной задачи коррекции .........................................36

2.2. Решение задач коррекции СЛАУ с минимаксными критериями .........39

2.2.1. Редукция задач коррекции с минимаксными критериями к задачам условной минимизации ......................................................................39

2.2.2. Применение метода декомпозиции для решения вспомогательных задач условной минимизации ...........................................................43

2.2.3. Условия неразрешимости задач коррекции системы линейных уравнений с минимаксными критериями ........................................46

2.3. Решение задач коррекции систем неравенств с минимаксными критериями .................................................................................................47

2.3.1. Сведение задач минимаксной коррекции к задачам условной оптимизации .......................................................................................47

2.3.2. Решение вспомогательных задач методом декомпозиции..............51

2.4. Выводы ко второй главе............................................................................55

ГЛАВА 3. Численные методы коррекции и декомпозиции несовместных СЛАУ и неравенств с блочной структурой и их применение к анализу и обработке данных.........................................................56

3.1. Алгоритмы коррекции несовместных СЛАУ и неравенств по минимуму взвешенной евклидовой нормы.............................................56

3.1.1. Алгоритмы решения задачи коррекции несовместных СЛАУ

с квадратичными критериями............................................................56

3.1.2. Алгоритмы решения задачи коррекции несовместных систем неравенств с квадратичными критериями ........................................57

3.1.3. Вычислительные эксперименты ........................................................57

3.2. Алгоритмы решения задач минимаксной коррекции несовместных СЛАУ и неравенств ...................................................................................60

3.2.1. Алгоритмы решения задачи коррекции несовместных СЛАУ

с минимаксными критериями ............................................................60

3.2.2. Алгоритмы решения задачи коррекции несовместных систем

неравенств с минимаксными критериями ........................................61

3.2.3. Вычислительные эксперименты ........................................................62

3.3. Выводы к третьей главе.............................................................................63

ЗАКЛЮЧЕНИЕ ..................................................................................................64

ЛИТЕРАТУРА ....................................................................................................66

ВВЕДЕНИЕ

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

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

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

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

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

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

- плохую определенность ограничений и критериальных функций (их малую изученность, сложную структуру);

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

- неоднозначность решений;

- неустойчивость моделей (в частности, эволюция моделируемого объекта и наших знаний о нем);

- неточность информации;

- переопределенность требований.

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

Период начала систематизированных и интенсивных исследований задач многопараметрической коррекции несовместных систем линейных алгебраических уравнений (СЛАУ) пришелся на 80-е годы прошлого века. При этом в России (СССР) и за рубежом примерно в одно и то же время были независимо получены с использованием разного математического аппарата близкие результаты.

Прикладные задачи, вызвавшие обозначенные исследования, были различными. В зарубежных исследованиях указанное направление развивалось в связи с задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов -Total Least Squares (TLS), который является обобщением классического метода наименьших квадратов (МНК) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Предполагая, что погрешности всех переменных подчиняются нормальному закону распределения с одними и теми же средним и дисперсией, было получено статистическое обоснование TLS как метода, дающего оценки неизвестных параметров линейной модели, гарантирующего максимум функции правдоподобия. Как правило, системы линейных алгебраических уравнений, обрабатываемые с помощью TLS, это переопределенные системы полного

ранга. Для сравнения - системы, возникающие при коррекции несобственных задач линейного программирования в канонической форме - как правило, являются недоопределенными. Главная задача TLS - определить квазирешение исследуемой линейной системы. В то же время, можно показать, что указанное квазирешение - это точное решение модифицированной системы, подвергшейся матричной коррекции по минимуму евклидовой нормы. Интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов после появления работ бельгийского математика S. Van Huffel [93].

В 1993 году появилась публикация американского математика профессора Дж.Б. Розена (J.b.Rosen) с учениками [95], послужившая началом развития нового научного направления - Structured Total Least Norm Approach. В этой работе была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась СЛАУ вида Лх = Ь, в которой вектор правой части Ъ содержит неточные данные (ошибки измерения), левая часть системы - матрица А - задана неточно в силу недостаточной априорной информации. Кроме того, матрица А обладает определенной структурой.

Дальнейшее развитие такой подход к решению задач структурной матричной коррекции получил в работах Дж.Б .Розена и его научной группы [96]-[98] и в работах бельгийских математиков под руководством профессора С. Ван Хаффел [101]-[103].

Изучение методов коррекции несобственных (не имеющих решения в классическом смысле) задач математического программирования является относительно новым направлением развития теоретической информатики. Предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить в работах А.Н.Тихонова [81], [82]. Систематические же исследования в данной области (с введением соответствующей терминологии) были начаты в 80-х годах (ХХ-века) И.И. Еремиными [44]-[47], его учениками и коллегами: H.H. Астафьевым [2], A.A. Ватолиным [13]-[15], Л.Д. Поповым [72], [73] и другими. В перечисленных работах рассматриваются несобственные задачи линейного и выпуклого программирования, вводится классификация несобственных задач линейного программирования [48], строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений - комитетные конструкции, предлагаются различные постановки и методы решения задач полной и частичной (правая часть системы уравнений и неравенств) параметрической коррекции и их содержательная, в основном экономическая, интерпретация. В большинстве исследований рассматривается коррекция по вектору правой части ограничений и коэффициентам вектора целевой функции. Ф.П. Васильевым [9] рассматривались методы коррекции правой части ограничений двойственной пары задач линейного программирования, причем все вспомогательные задачи были также задачами линейного программирования.

В конце 90-х годов в ВЦ им. А.А. Дородницына РАН и Mill У появился другой центр исследования несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования под руководством профессора В.А. Горелика (В.И. Ерохин, В.А. Кондратьева, О.В. Муравьева, P.P. Ибатуллин, Р.В. Печенкин, И.А. Золтоева и др.) [19]—[31], [35]—[39]. Указанными авторами широко исследовалась коррекция несовместных систем линейных алгебраических уравнений с условием неотрицательности решения, показана их тесная связь с задачами матричной коррекции несобственных задач линейного программирования. В их работах рассмотрены несобственные задачи линейного программирования 1-го и 3-го рода в классификации [48], т.е. задачи линейного программирования с несовместными системами ограничений. В качестве вспомогательных, решены задачи коррекции несовместных систем линейных уравнений и неравенств.

В монографии В.А. Горелика и В.И. Ерохина [21] приведено систематизированное описание методов решения задач оптимальной многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений с критериями оптимальности, построенными с использованием евклидовой нормой. Исследованы задачи коррекции, в которых часть элементов матрицы коэффициентов системы или часть элементов расширенной матрицы зафиксированы (задачи с фиксированными строками, задачи с фиксированными столбцами и задачи с совокупностью фиксированных строк и столбцов). Предложены модификации для критерия оптимальности коррекции с помощью взвешивания элементов матрицы коррекции как посредством ее левого и правого умножения на невырожденные весовые матрицы, так и с использованием индивидуальных неотрицательных весов для каждого элемента. Анализируются необходимые и достаточные условия существования решения задач матричной коррекции, вид оптимальных матриц коррекции и вид множеств решений скорректированных систем. Сформулированы возможные обобщения и модификации постановок задач матричной коррекции, а также способы их регуляризации.

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

Ибатуллин P.P. [52] рассмотрел задачу коррекции всех данных для несовместных систем линейных уравнений с минимаксным критерием.

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

В работах В.А. Горелика, В.И. Ерохина, Р.В. Печенкина [25] осуществлено развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимальной коррекции по квадратичному и минимаксному критериям. Получен метод решения задачи оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, обладающих блочной структурой, с использованием квадратичного и минимаксного критериев. Сформулирован критерий оптимальной коррекции несовместной системы с матрицей Теплица и Вандермонда при наличии ошибок только в левой части и предложен метод коррекции с использованием штрафных функций норм векторов невязок. Для плохо обусловленных систем со структурой Вандермонда сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах.

В.А. Горелик, И.А. Золтоева и Р.В. Печенкин [28] рассмотрели проблему оптимальной коррекции несовместной системы с матрицами разреженной структуры и ее применение к задачам многокритериальной оптимизации. Естественным требованием для таких систем является сохранение разреженной структуры, что вносит ограничение на структуру матрицы коррекции, но с другой стороны уменьшает размерность задачи, что приводит к построению более эффективных алгоритмов.

В работах В.А. Горели