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

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

Баркалова Оксана Сергеевна

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

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

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

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

2 и НАР 2014

005546231

Москва-2014

005546231

Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский педагогический государственный университет»

Научный руководитель: доктор физико-математических наук, профессор

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

Официальные оппоненты: Дмитриев Михаил Геннадьевич

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

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

Ведущая организация: федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Московский государственный университет им. М.В. Ломоносова»

Защита диссертации состоится «10» апреля 2014 г. в 14:00 ч. на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном Учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук по адресу: 119333, Москва, ул. Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного Учреждения науки Вычислительный центр им. А. А. Дородницына Российской академии наук.

Автореферат разослан « 6 » мсср>пгд 2014 г.

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

Д 002.017.02, д.ф.-м.н., профессор В.В.Рязанов

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

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

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

• идеализацией или искажением некоторых соотношений, некорректностью требований, предъявляемых к модели (или объекту);

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

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

3

Тем не менее, исследование некорректных задач началось ещё в начале XIX века. Гаусс и Лежандр независимо друг от друга предложили решать переопределённые, как правило, несовместные системы линейных уравнений методом наименьших квадратов (МНК). Дальнейшим его развитием стало возникновение обобщённого метода наименьших квадратов (TLS — Total Least Squares).

Несовместные системы линейных алгебраических неравенств применительно к задачам проектирования механических систем рассматривал П.Л. Чебышёв. Позднее системы линейных неравенств, не обязательно совместные, изучались И.И. Ерёминым, С.Н. Черниковым и другими авторами.

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

A.Н. Тихонов (1943 г.). Во многом благодаря его трудам разработана общая стратегия построения устойчивых методов решения некорректных (неустойчивых) задач.

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

Исследования матричной коррекции несовместных линейных систем и соответствующих задач линейного программирования проводились параллельно и отечественными математиками, и зарубежными. Решения с точки зрения сингулярных разложений опубликовали в 1980 г. американские математики-вычислители Gene H. Golub и Charles F. Van Loan. Монография начала 90-х годов бельгийских математиков S.Van Huffel и J. Vandewalle «The total least squares problems» описывает дальнейшие расширения и приложения. Начались исследования и структурной коррекции. Gene H. Golub, Alan Hoffmann и G. W. Stewart исследовали случаи, когда некоторые столбцы матрицы коэффициентов могут быть фиксированы. Вопросы коррекции обеих частей матрицы системы с ограничениями описал Amir Back.

Среди отечественных математиков матричной коррекцией впервые занялся в середине 80-х годов XX в A.A. Ватолин. Работы в этом направлении, но с упором на несобственные задачи математического программирования, проводились под руководством академика РАН И.И. Еремина научной школой Института математики и механики УрОРАН.

В конце 90-х годов XX в. исследования уральской школы были продолжены в ВЦ РАН и МПГУ В.А. Гореликом и его учениками:

B.И. Ерохиным, И.А. Золтоевой, P.P. Ибатуллиным, O.A. Клименко, В.А. Кондратьевой, О.В. Муравьёвой, Р.В. Печёнкиным и другими. В основном в качестве критерия оптимальности решения задачи коррекции использовался минимум евклидовой нормы матрицы коррекции. Исследованы вопросы существования решения, вид решения скорректированной системы,

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

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

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

Использование в качестве критерия оптимальности полиэдральных норм даёт новые возможности с точки зрения формализации постановки и содержательной интерпретации задач оптимизации, в том числе прикладных. Основными достоинствами полиэдральной оптимизации являются:

• ясный практический смысл полиэдральных критериев качества коррекции;

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

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

Всё вышесказанное и обуславливает актуальность выбора темы для данной исследовательской работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• структурная коррекция линейных систем по минимуму полиэдральных норм матрицы коррекции;

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

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

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

полученные в диссертации, докладывались: на региональной научно-методической конференции «Актуальные проблемы модернизации математического и естественно-научного образования», БИ СГУ, 8 апреля 2010г.; на итоговой научной студенческой конференции Саратовского государственного университета, 12 мая 2010 г; на научной конференции «Математика, информатика и методика их преподавания», МПГУ, март 2011 г; на научной сессии математического факультета МПГУ 14 марта 2013 г.; на VI Международной научно-практической конференции «Молодёжь и наука: реальность и будущее», г. Невинномысск, 2013 г.; на научном семинаре отдела «Имитационные системы и исследование операций» Вычислительного центра им. А.А. Дородницына РАН, 12 ноября 2013 г.

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

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

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

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

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

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

Ах = Ь,х> 0, (1)

где А 6 Ятхп,х е Яп,Ье Ят. Пусть Ь) = {х\Ах = Ь,Х > 0 } = 0, т.е.

множество её решений пусто.

Сформулируем следующие задачи коррекции:

Щьс{ъ}{А, ЪУ ||Я|и -» (ъ°Пх[ь} = ™п||Я И^) ^

В (2) требуется найти матрицу коррекции Н для задачи Н/1Х[ь}(А> Ь) и расширенную матрицу коррекции [к Н] для задачи ^о£а;(Л, Ь), имеющие минимальные нормы:

\pi_Ax~)

- Т,аох к^Г

где (р, гр — некоторые векторные нормы.

Определение. Векторную норму ||-|| называют полиэдральной, если её единичный шар

%ц(1;0) = {уедп:||у||<1} является многогранником, т.е. выпуклой оболочкой конечного множества точек.

Определение. Матричную (р,гр - норму будем называть полиэдральной, если соответствующие векторные нормы <р(0 и ¡/>(0 являются полиэдральными.

Для матрицы А £ Ятхп существует четыре вида полиэдральных норм:

т п

М1--ЖЫ. ии-^Ы

т

1=1 ]=1

1ИН1Д = тахУ|ау|, А

В пункте 1.3 рассмотрены условия существования решения задач Щ1х{ь){А, Ъ) и Я"СоСа((Л, Ь). Приведём теоремы для случая коррекции по минимуму ||-Цоод-нормы.

Теорема 1.1. Решением задачи коррекции Щ1Х{ь)(А- Ь) по минимуму 11*11 оо 1-нормы является

. - а1х|

кПх(Ь] = тт-■

' 1 ' х тах х,

1 <)<п J

Достижимость °^ является необходимым и достаточным

условием существования решения задачи ^/£;<-{ь}(А Ю-

Если решение задачи коррекции А, Ь) существует, то

й/г*{ь} > °< [/г* Н*] = 0Ь-Ах)уТ,

х* е + н*,ь- Н'),

где

х € Argmin- -

max Xj

1<j<n 1

у £ Дп — вектор, двойственный к вектору х* относительно нормы |Н1оо-

Теорема 1.2. Решением задачи коррекции О-С^^А, Ь) по минимуму Ц-Цоо д-нормы является

h°totai= rnin У [Ь — a']z,

z: ram z,=l

о <j<m

jn+1

где гЕЛ ,г>0. Для того чтобы задача ^о£а)(Л,Ь) имела решение, необходимо и достаточно, чтобы выполнялось условие

3z* G Argmin Y[b; -a']z|zo^O.

z: шах z,=1 ^-r1

: max z,—j. -о <j<m 1 1=1

Если решение задачи (А Ь) существует, то

Сш > О, [Л* Я*] = [Ь -где у £ /?"+1 - вектор, двойственный к вектору г* относительно нормы При этом

ех (Л + Я*,Ь-/Г).

1

** =-

Теорема 1.3. Если задача Щ1Х{ъ}(А> Ь) (jKtotal(A, ft)) имеет решение, то для любой матрицы Я такой, что я(Л + Я, b(+ft.)) ^ 0,гапк Я = 1, множество + Н, b(+h)) состоит только из одного элемента. Теорема 1.4. Если несовместная система вида (1) такова, что rank А < п, то задача Wfix[b}(A> b) (j^totai СА Ь))не имеет решения.

Объединим формулировки задач ?Г//*{ь}(А Ь) и ?ftotai(/l, й) в задаче 3~С(Л, Ь), введя параметр Z:

=f0 lu

О, если корректируется только левая часть, , если корректируются левая и правая части. При решении задач "К(А, Ь) используется их сведение к задаче линейного или билинейного программирования (пункт 1.3).

Теорема 1.5. Задача коррекции Э£(А,Ь) по минимуму Ц'Ноод - нормы эквивалентна задаче математического программирования

г di > Ъ(Г — а1ц, [ = 1 ,т, di > —Ь(г + а1д, I = 1,7П,

I

i=1

di

min при условиях -d,q,r

qj<l,j = \1-1\,п, 3;: Rj

(3)

l,j £ Ц-11,71, г > 0, q > 0, d > 0.

Если существует (d°, q°, r°) — решение ЗЛП (3), то задача 0~С(А, Ь) имеет

решение, которое, в частности, может быть построено по формулам: m 0

h° = ^ di° ,х° = [h H] — (b — Ах°)у°, i = TTiïij = \l-l\,n,

¿=i

где y0 — вектор, двойственный к вектору относительно нормы ||-1|х.

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

Пусть К е /j"ix(n+i) _ матрица, содержащая информацию о корректируемых элементах. К = (kij), ky £ {0,1}, i = 1, m,j = 0,n. При этом kij = 0, если соответствующий элемент матрицы [- Ь ¿4] фиксированный, и

кц = 1,

если соответствующий элемент матрицы

И л]

может

корректироваться.

Теорема 1.6. Если для элементов матрицы К = (/с^) выполняются условия

кц = = 1, £ = 1,^, ку = кп - 0,1 = сг + 1, т,] = 0,с2, кц = 0,1 = 1 ,т,} = с2 + 1 ,п, то задача коррекции Э{{А,Ь) по минимуму Ц-Ц^д-нормы эквивалентна следующей задаче математического профаммирования

I

di

min при условиях

di > btr — alq, i = 1, c1( di > —bir + alq, i = 1, cv

b{r — alq = 0, i = ct + 1, m, qj < 1,j = |i - l|,c2, 3;': qj

(4)

1,у е \1- 1|,с2, г > о, <7 > о, с? > о.

Если существует - решение задачи (4), то задача 3~С(Л, Ь)

имеет решение, которое может быть построено по следующим формулам

10

/10 = = (Ь-Ах°)у°,1 = 1,с1(

¿=1_ _ _

= К - 1|, с2, кц = О, I = + 1, т,;' = с2 + 1, п.

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

Теорема 1.7. Если для элементов матрицы К = выполняются

условия

3/' = {1\ки = 0, у = Т/тг Л /С;о = 1}, _

кц = кп = 1Л = 1, с1( к1} - к^ - 0,1 = сг + 1, т,;' - 0, с2, кц = 0,1 = 1 ,т,} = с2 + 1 ,п, то задача коррекции ТГСЛ,Ь) по минимуму |И|оод - нормы эквивалентна следующей задаче математического программирования

> ¿¡г — а'лгг, I = 1, с1(

I

dt

min при условиях

d,x,r

di > —Ь(г + alxr, i = 1, с1(

b¡ - alx = 0, i = Ci + 1, m - |/'|

d¿ > bt — alx, i = m — |/'| + 1, m, di > —bi + alx, i = m — Ц'| + 1, m, x¡r < 1= - l|,c2,

(5)

3j:x}r = l,j e\l- l|,c2, г > 0,x > 0,d > 0. Будем считать элементы вектора d, соответствующие фиксированным строкам, нулевыми, то есть = 0, i = сг + 1,т — |/'|.

Если (d°,x°,y °) - решение задачи (5), то решение задачи К (А, Ь) может

быть найдено по формулам: т

h° = ^ di°,hi} = (^ - а1х°)у0,i = 1TE[,j = \l-l\,c2,

i=l

hij = 0, i = cx + l,77i — II'\,j = c2 + l,n,hij = bi~ alx°,

I - l|,c2,

¿1

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

i — m— |/'| + l,7n,y = где y° - вектор, двойственный к вектору

Если в матрице исходной системы присутствуют отдельные фиксированные элементы, то К(_А, Ь) методом векторизации сводится, в зависимости от нормы, к одной из дискретных минимаксных задач (7):

ft = (УГ)+(ВД ■ Ю+(Ь — Ах) = V • (ВД ■ V)+(b - Ах). (6)

h° = min||H||i о, = min max |/ь,| = min max IftJ,

X ' X 1 <¡<m' X l<s<N

l<j<n

т т

h° = пип||Я||1Д = mjnmax^J/i;7| = min max

i=l ~ " i=1 71 П

h° - minll^lUco = min max ) \hu\ = min max ) |ftfi_1)n+I-|,

X X Кктп / ■' 11 X 1<i<m / v ' ' 1

J=l 1=1

или к нелинейной оптимизационной задаче нахождения минимума функции многих переменных (при х > 0):

N

N

h° = min / IhsI = min

X ' ' X _

s=l (i-l)n+j

I

- (bi - alx)

í = 1 ,m,j e 1 ,n.

/=1I ?>jejtx?

Если найдено решение h° на векторе х° £ Rn, то матрицу Н° и скорректированную матрицу коэффициентов Л° можно найти по следующим формулам:

Н° = Я°(й) = [Ь°ц\Щ = ft(í_ 1)n+/, i = T~m.y = Ui}, = А + Н°,

где h = h(x) определяется формулой (6) при х = х°.

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

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

сТх -* тах (8)

порогового значения с0, которое не подлежит коррекции: сТх > с0.

Теорема 2.1. Задача коррекции Я"(Л,6) по минимуму ||-|!oo,i - нормы задачи линейного программирования, определяемой условиями (8), (1), эквивалентна следующей задаче математического программирования:

r di > Ь(г — alq,i = 1, m, dt > —biT 4- alq, i = l,m,

n

Zdt -» min при условиях

u,q,r

i=1

^ Cj4j - C0r ^ 0,

í=1

(9)

qj<lJ = \l-l\,n,

3/: = 1,; £ |г- 1|,п, г > 0, д > 0, с* > 0.

Пусть (<2°, <7°,г°) - решение ЗМП (9). Если указанное решение существует, то задача 'К {А, Ь) имеет решение, которое, в частности, может быть построено по следующим формулам:

т 0

И.0 =^<1°,х° Н] = (Ь- Ах°)у°, I = Ът.) = \1-1\,п.

г=1

Если задача коррекции 7С{А,Ь) не имеет решения, то для Ц-Ц^оо и Н'Ихд-норм применяется регуляризация вида

ft £

Xj <м,ме R+,

1=1

а для случаев ||-||co,i и ||-||оо,оо-норм - вида max Xj <М,М е R+.

ls/<n J

Так как после коррекции возможно, что скорректированная задача будет неограниченной, то наряду с коррекцией только прямой задачи в пункте 2.2 рассматривается совместная коррекция пары взаимно двойственных задач, обозначенных L и L*. Считается, что L и L* заданы в стандартном виде. Вновь принимаются во внимание два случая - коррекции обеих частей системы, и только левой её части. Формулируются соответственно задачи D^ щ и DH\

Д

(г

L{A + H,b — h, с): (Л + Н)х < b - h,x > О, с х -> max,

[h н]' I i*(A + H,b-h, с): ит(А + Н)>ст,и> О, (Ь - h)Tu -» mm.

Задача Он получается из Н] при /г = 0. Теорема 2.2. Задача £)[й щ по норме || задаче математического программирования:

'<1 > а1 г — Ь^у, I = 1, тп, й > с ¡у — ау'2,у = 1, п, й > — с0у, й > —ЪТ1 + с0у,

1оо эквивалентна следующей

d. -» min при условиях

y,z,y,z,d,c0

^ CjZj - С0у = О,

7 = 1

(10)

7=1

Z

Z; = 1,

¿=1

у,г,у,г,й,с0 > 0.

Если существует (у0,г0,у0,г0,1°,с10) - решение задачи (10), то решение задачи Н], а также скорректированной пары задач линейного

программирования можно будет найти по формулам:

2° _ _

= й°,х° = — ,и° = —I = 1, т, У = 1,п.

уи уи

Если к коррекции пары двойственных задач предъявляется только требование существование решения, то в задаче (10) можно зафиксировать значение с0, при этом она станет ЗЛП. Соответствующие скорректированные задачи будут собственными. При нахождении наименьшего при котором задача коррекции и скорректированная пара двойственных задач имеют решения, получаем задачу одномерной минимизации по с0 € (—оо; +оо). Если

возможно получить нижнюю и верхнюю (с^) оценки для значений целевой

функции, то осуществляем минимизацию по с0 6 (с0;с0)- Если существенным

является достижение наибольшего значения целевой функции стх —> гпах , что более адекватно постановке исходной задачи, то следует осуществить перебор значений с0 £ (с^; с^), где Сд - пороговое значение целевой функции, которое удовлетворяет требованиям ЛПР.

Для многокритериальных задач рассмотрены два подхода. В пункте 2.3 для целевых функций вводится, по аналогии с однокритериальным случаем, вектор пороговых значений, и, таким образом, они переводятся в ограничения-неравенства. При втором подходе (пункт 2.4) пороговые значения не фиксированы и, наряду с элементами матрицы коэффициентов ограничений, могут корректироваться. Задача коррекции принимает вид:

Я(А,Ь,С,с°у. _

/г° = т^{||[Н]||„^: (Л + Н)х = Ь — к,Шк(х) >4-wk,k = 1 ,г.

где Я =

V

Йю Ли ' ■ Ащ\

Ь-тО Лгп1 Ьтп

0 • ■ 0

\МГ 0 • о/

= Г н\

Чу О/

При решении задачи К {А, Ь, С, с°) используется сведение к задаче билинейного программирования, к которой применяются численные методы нахождения минимума функции одной переменной. Проведён сравнительный анализ метода дихотомического поиска и метода золотого сечения на скорость сходимости.

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

м {НРО^У,,] - [^,у]\\(р,ф'ун = /(4).I =

f£ФЛн,Уh

В зависимости от конкретного вида полиэдральной нормы получаем различные частные постановки данной задачи.

Теорема 3.1. Пусть в пространстве признаков Яп даны т точек (х1,х2, ■..., Ос™,*™, ...,х™), а в пространстве И множество ответов у1, ...,ут, и не существует аффинной функции Д такой, что

у1 = /(*')> I = 1,ш. Тогда задача нахождения минимального изменения

матрицы параметров [-у Х\ =

"У1 х\ -у2 х\

в смысле минимума

Х1 — ХП

Н'Исод- нормы, в результате которого интерполяционная аффинная функция существует, эквивалентна задаче математического программирования

II l i

di-

min при условиях

d,q,r

dt > ylr — xlq,i = l,m, di > —ylr + xlq, i = 1 ,m,

\qj\<l.j = Üi, _ (И)

3k:qk - 1 Vqk = -1 ,k e l,n

v d > 0.

Если существует (d°, q°, r°) - решение задачи (3.3), то коэффициенты аффинной функции

fix) = аухх + а2х2 + ... + а„хп + а0 = (ajc) + а0 и скорректированные значения параметров находим по формулам

т о

i=1 _ _

[-h H] = (y — Xä°)b°, i = 1 ,m,j = 0,n, [~Ул XH] = [-y X] + [-h H], где b° - вектор, двойственный к вектору [1, а]т относительно нормы Ц-^.

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

Постановка задачи классификации: необходимо разбить точки «-мерного пространства на два класса К^ и К2 аффинной разделяющей функцией вида F(x) = а^ + а2х2 Н-----Ь апхп — b = (_а,х) — Ь.

При этом если объект х принадлежит классу К1г то должно выполняется неравенство F(x) < 0, а если х 6 К2, то F(x) > 0. Задача коррекции для случая неразделимости классов принимает вид

мь{||[Н]||„,„: [X + н -р] [I] < о} = hineq°.

Теорема 3.2. Пусть в пространстве Rn даны / точек (х\,х2, ...,х\),..., (х[,х2, принадлежащих классу Klt и т-1 точек

(х[+1,х2+1, ....Хп1),..., {х™,х™, ...,Хп), принадлежащих классу К2, и не существует разделяющей их линейной функции. Тогда задача нахождения минимального изменения матрицы координат X в смысле минимума Ц'Цоод-нормы, в результате которого разделяющая аффинная функция существует, эквивалентна задаче математического программирования

' di > —xlq + PiQb'1 е dj > х1д-р1(jb,ie Г, dt -» min при условиях - |9у| < lj = i,n, (12)

Яа<ър 3k: qk = 1 V qk = —l,k e I7n,

d > 0,

iei-

где X — подматрица X, состоящая из строк с номерами I £ р -соответствующий вектор из элементов вектора р, а Ха <Ър - подсистема, составленная из остальных неравенств системы Ха < Ьр.

Если существует — решение задачи (12), то коэффициенты

разделяющей аффинной функции

F(x) = а1х1 + а2х2 + ... + апхп — Ь = (а,х~) — Ь и скорректированные значения параметров находим по формулам

¡е/-

Н = (-Ха° + рЬ°)у°; х\, = х1 + к1,1 £ Г ,1 < I < I, х1н=х1-к\1еГ,1 + 1<1<т,

х1и =х1Л& Г. 1 < / < гп, где у0 - вектор, двойственный к вектору а относительно нормы Ц-Ц-^

В каждом параграфе последним пунктом приведены вычислительные эксперименты (пункты 1.5, 2.5 и 3.4), которые подтверждают работоспособность полученных методов.

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

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

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

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

• Исследована структурная коррекция систем линейных алгебраических уравнений, а именно:

- задачи с запретом коррекции некоторых строк, столбцов или какой-либо их комбинации сведены к задачам линейного программирования или (в зависимости от вида нормы) конечной последовательности таких задач;

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

- задачи с запретом коррекции отдельных элементов методом векторизации сведены в трёх случаях нормы к дискретным

минимаксным задачам, а в одном — к задаче нахождения минимума функции многих переменных.

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

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

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

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

• Созданы вычислительные алгоритмы, соответствующие указанным методам и реализованные в математической среде MatLab.

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

1. Баркалова, О. С. Коррекция несобственных задач линейного программирования в канонической форме по минимаксному критерию II Журнал вычислительной математики и математической физики, 2012, т. 52, №12, С. 2178-2189. - 1,5 п.л.

2. Баркалова, О. С. Коррекция несобственных задач классификации по минимуму различных видов полиэдральных норм II Качество. Инновации. Образование, 2013, №2, С. 39-43. — 0,63 п.л.

3. Баркалова, О. С. Применение методов коррекции по минимуму полиэдральных норм к задачам регрессии // Экономика, статистика и информатика. Вестник УМО, 2013, №2. С. 98-102. - 0,53 п.л.

4. Павлова (Баркалова), О. С. Применение информационных технологий к коррекции несобственных задач линейного программирования // Актуальные проблемы модернизации математического и естественнонаучного образования: матер. Регион, науч.-методич. конф., г. Балашов, 8 апреля 2010 г. - Балашов: Николаев, 2010. - С. 78-80. - 0,2 п.л.

5. Павлова (Баркалова), О. С. Коррекция несобственной задачи линейного программирования (ЗЛП) с матрицей ограничений, имеющей фиксированные столбцы // Научные исследования студентов Саратовского государственного университета: Материалы итог. студ. науч. конф. - Саратов: Издательство Саратовского университета, 2010. — С. 65-68. - 0,25 п.л.

6. Горелик В. А., Павлова (Баркалова), О.С. Программная реализация коррекции несобственных задач линейного программирования по минимаксному критерию // Моделирование, декомпозиция и оптимизация сложных динамических процессов. - М.: Вычислительный

центр им. A.A. Дородницына Российской академии наук, 2010. - С. 66-80. (авторский вклад - 50%). - 0,94 п.л.

7. Баркалова, О. С. Численные методы коррекции многокритериальных задач линейного программирования (ЗЛП) // Математика, информатика и методика их преподавания: Материалы Всероссийской конференции, посвященной 110-летию математического факультета МПГУ (Москва, 14-16 марта 2011 г.) / Ответственный редактор B.JI. Матросов. - Москва: МПГУ, 2011. - С. 28-30. - 0,2 п.л.

8. Баркалова, О. С. Решение задачи матричной коррекции несобственной задачи линейного программирования по минимуму ||-||сх>д - нормы // Математика, информатика, физика в науке и образовании: сборник научных трудов. М.: МПГУ, Прометей, 2012. С. 33-34. - 0,13 п.л.

9. Баркалова, О. С. Классификация задач коррекции систем линейных алгебраических уравнений по минимаксному критерию // Молодёжь и наука: реальность и будущее: Материалы VI Международной научно-практической конференции (г. Невинномысск, 2013). — Т. I. — Невинномысск: НИЭУП, 2013. - С. 22-25. - 0,5 п.л.

Подписано в печать: 27.02.2014 Объем: 1,0 п. л. Тираж: 100 экз. Заказ №143 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495) 363-78-90; wwv.reglet.ru

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

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

\

\

Баркалова Оксана Сергеевна

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

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПО МИНИМУМУ ПОЛИЭДРАЛЬНЫХ НОРМ И ИХ ПРИМЕНЕНИЕ В ПРОЦЕССАХ

ОБРАБОТКИ ИНФОРМАЦИИ

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

Диссертация на соискание ученой степени кандидата физико-математических наук

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

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

Москва 2013

Содержание

Введение....................................................................................4

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

1.1. Понятие полиэдральной нормы и постановка задачи коррекции несовместных линейных систем................................................... 16

1.2. Необходимые и достаточные условия существования решения задачи коррекции..............................................................................24

1.3. Методы решения задач коррекции несовместных линейных систем по минимуму полиэдральных норм...................................................36

1.4. Коррекция линейных систем с ограничениями на матрицу коррекции...............................................................................41

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

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

Глава 2. Коррекция несобственных задач линейного программирования с одним и многими критериями по минимуму полиэдральных норм ... 56

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

2.2. Коррекция несобственной задачи линейного программирования с использованием теории двойственности........................................60

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

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

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

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

Глава 3. Применение методов коррекции по минимуму полиэдральных норм к задачам регрессии и классификации.................................89

3.1. Применение методов коррекции по минимуму полиэдральных норм к задачам регрессии.....................................................................89

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

3.3. Применение методов коррекции по минимуму полиэдральных норм к несобственным задачам классификации........................................ 100

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

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

Заключение..............................................................................114

Литература..............................................................................116

Приложение.............................................................................128

Введение

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

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

Несобственность любой модели, в том числе и линейной, может быть обусловлена [35]:

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

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

• идеализацией или искажением некоторых соотношений;

• некорректностью требований, предъявляемых к модели (или объекту);

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

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

Тем не менее, исследование некорректных задач, началось ещё в начале XIX века. Гаусс и Лежандр независимо друг от друга предложили решать переопределённые, как правило, несовместные системы линейных уравнений методом наименьших квадратов (МНК). Он заключается в поиске вектора поправок правой части системы, имеющую минимальную норму и гарантирующего совместность полученной системы.

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

Несовместные системы линейных алгебраических неравенств применительно к задачам проектирования механических систем рассматривал П.Л. Чебышёв. Позднее системы линейных неравенств, не обязательно совместные, рассматривались и другими авторами [53, 66, 75, 96].

С развитием науки и техники (в частности, цифровой) необходимость в умении решать некорректные задачи всё возрастает. Следует отметить ведущие позиции российских учёных в данной проблематике. Начало бурному развитию теории и практики методов решения некорректных задач положил академик А. Н. Тихонов (1943 г.) [88-91]. Во многом благодаря его трудам разработана общая стратегия построения устойчивых методов решения некорректных (неустойчивых) задач. Термин «корректность по Тихонову» принадлежит другому крупному специалисту по некорректным задачам - академику РАН Лаврентьеву М.М.

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

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

параллельно и отечественными математиками, и зарубежными [99-113]. Решения с точки зрения сингулярных разложений опубликовали в 1980 г. американские математики-вычислители Gene H. Golub и Charles F. Van Loan в виде статьи «An analysis of the total least squares problem» («Анализ обобщённого метода наименьших квадратов») [104]. Монография начала 90-х годов Бельгийских математиков S.Van Huffei и J. Vandewalle «The total least squares problems» [112] описывает дальнейшие расширения и приложения. Начались исследования и структурной коррекции. В статье Gene H. Golub, Alan Hoffmann и G. W. Stewart «A Generalization of the Eckart-Young-Mirsky Matrix Approximation Theorem» были исследованы случаи, когда некоторые столбцы матрицы коэффициентов могут быть фиксированы. Вопросы коррекции обеих частей матрицы системы с ограничениями описал Amir Back [99].

Среди отечественных математиков матричной коррекцией впервые занялся в середине 80-х годов XX в А.А.Ватолин [20, 21]. Работы в этом направлении, но с упором на несобственные задачи математического программирования, проводились под руководством академика РАН И.И.Ерёмина научной школой Института математики и механики УрОРАН [49-53].

В конце 90-х годов XX в. исследования уральской школы были продолжены в ВЦ РАН и МПГУ В.А.Гореликом и его учениками: В.И. Ерохиным, И.А. Золтоевой, О.В. Муравьёвой, P.P. Ибатуллиным, В.А. Кондратьевой, Р.В. Печёнкиным, O.A. Клименко, Н.З. Ле и другими [63, 64, 68, 69, 72, 79, 82]. В основном в качестве критерия оптимальности решения задачи коррекции использовался минимум евклидовой нормы матрицы коррекции. Исследованы вопросы существования решения, вид решения скорректированной системы, структурной коррекции (когда матрица коррекции имеет фиксированные строки и/или столбцы, отдельные элементы, является разреженной, матрицей Теплица, комбинаторного типа, имеет блочную структуру).

Р.Р.Ибатуллиным был рассмотрен минимаксный критерий оптимальности для коррекции систем линейных уравнений; описана коррекция линейных управляемых систем при ограничениях на управляющие переменные, значения входа и выхода системы. Предложены методы минимаксной коррекции, сводящие их к решению задач линейного программирования [64]. И.А. Золтоевой исследованы вопросы многокритериальной коррекции, в том числе с использованием минимаксного критерия, коррекция несовместных линейных систем с разреженными матрицами коэффициентов [63]. Также В.А. Гореликом и О.В. Муравьёвой задачи коррекции по минимуму евклидовой нормы применены к проблемам оптимизации и распознавания [41, 42, 44].

В настоящее время при моделировании реальных систем возникают новые некорректные задачи. В связи с этим необходимо разрабатывать новые численные методы решения таких задач и реализовывать их с использованием современных математических пакетов, таких как МшкСас! и МшЬаЬ. В частности, не полностью исследованными остаются вопросы коррекции линейных систем и соответствующих задач линейного программирования, для которых в качестве критерия оптимальности рассматривается минимум какой-либо полиэдральной нормы матрицы коррекции. Частным его случаем является минимаксный критерий. Всё вышесказанное и обуславливает актуальность выбора темы для данной исследовательской работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• структурная коррекция линейных систем по минимуму полиэдральных норм матрицы коррекции;

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

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

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

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

1)на региональной научно-методической конференции «Актуальные проблемы модернизации математического и естественно-научного образования», БИСГУ, 8 апреля 2010 г.;

2) на итоговой научной студенческой конференции Саратовско