Содержание к диссертации
Введение
1 Теорема о матричном решении обратной задачи линейного программирования и ее применение к матричной коррекции данных двойственной пары несобственных задач линейного программирования 16
1.1 Постановка задачи оптимальной матричной коррекции данных двойственной пары несобственных задач линейного программирования 16
1.2 Матричное решение обратной задачи линейного программирования 18
1.3 Совместная коррекция данных двойственной пары несобственных задач линейного программирования, гарантирующая существование заданных ненулевых решений 22
1.4 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования, не имеющих специальной структуры 31
1.5 Необходимое условие разрешимости задачи оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования 40
2 Оптимальная совместная коррекция данных двойственной пары несобственных задач линейного программирования с ограничениями на матрицу коррекции 50
2.1 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с запретом изменения произвольных строк 50
2.2 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с запретом изменения произвольных столбцов 58
2.3 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с блочной структурой 68
2.3.1 Оптимальная матричная коррекция всех блоков системы ограничений двойственной пары несобственных задач линейного программирования с блочной структурой 70
2.3.2 Оптимальная матричная коррекция с запретом изменения связывающего блока двойственной пары несобственных задач линейного программирования с блочной структурой 77
3 Использование векторизации матрицы коэффициентов для матричной коррекции данных двойственной пары несобственных задач линейного программирования 86
3.1 Векторизация задачи матричной коррекции 86
3.2 Матричное решение обратной задачи линейного программирования с использованием векторизации 89
3.3 Совместная коррекция данных двойственной пары несобственных задач линейного программирования с использованием векторизации, гарантирующая существование заданных ненулевых решений 93
3.4 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования, не имеющих специальной структуры с использованием векторизации 97
3.5 Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с запретом коррекции некоторых элементов 106
4 Оптимальная матричная коррекция данных в задачах рас познавания образов с пересекающимися классами и гарантирующего оценивания параметров 113
4.1 Использование матричной коррекции данных несобственных задач линейного программирования в задаче распознавания образов с пересекающимися классами 113
4.2 Использование матричной коррекции данных несобственных задач линейного программирования в задачах обработки данных по методу гарантирующего оценивания параметров 125
Заключение 131
Литература 133
Приложение
- Матричное решение обратной задачи линейного программирования
- Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с запретом изменения произвольных столбцов
- Совместная коррекция данных двойственной пары несобственных задач линейного программирования с использованием векторизации, гарантирующая существование заданных ненулевых решений
- Использование матричной коррекции данных несобственных задач линейного программирования в задачах обработки данных по методу гарантирующего оценивания параметров
Введение к работе
Актуальность темы исследования. Линейные оптимизационные модели находят многочисленные приложения в технике, экономике, задачах помехоустойчивого анализа экспериментальных данных, гарантирующего оценивания параметров, распознавания образов и классификации.
Как показывает практика, погрешности (шум) в экспериментальных данных, ошибки округления, возникающие при вычислениях в арифметике с конечной разрядностью, а также нечеткость и противоречивость информации, использующейся при построении указанных моделей, могут приводить к неразрешимым задачам линейного программирования. Такие задачи принято называть противоречивыми или несобственными.
Очевидно, что несобственная задача линейного программирования не позволяет получить содержательную информацию об исследуемом процессе или явлении непосредственно, требуется ее уточнение, изменение, в результате чего должна быть получена собственная задача, в некотором смысле "близкая" к исходной. Т.е. возникает задача предварительной обработки данных. При малой размерности модели ситуацию неразрешимости можно преодолеть простыми средствами: проверить правильность исходных данных, и, в случае необходимости, изменить их, ослабить некоторые ограничения или совсем исключить их из модели и т.д. Однако, при автоматизированном (программном) формировании модели или в случае модели высокой размерности, требуются более сложные средства коррекции данных, причем, желательно программно обеспеченные. В этом случае матричная коррекция - это инструмент обработки данных (информации), позволяющий решать задачи линейного программирования с нечеткими, неопределенными, зашумленными данными, что позволяет ее включить в область исследования теоретических основ информатики.
Изучение методов коррекции данных несобственных задач линейного программирования является относительно новым направлением развития теоретической информатики. Предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить в работах А.И. Тихонова. Систематические же исследования были начаты в 80-х годах (XX века) И.И. Ереминым, его учениками и коллегами: Н.Н. Астафьевым, А.А. Ватолиным, Вл.Д. Мазуровым, Л.Д. Поповым, В.Д. Скариным, СП. Трофимовым, В.Н. Фроловым и другими. Ф.П. Васильевым рассматривались методы коррекции правой части ограничений двойственной пары задач линейного программирования, причем все вспомогательные задачи были также задачами линейного программирования. В конце 90-х годов (XX в.) исследования в данной области были продолжены, и продолжаются в настоящее время в ВЦ им. А.А. Дородницына РАН и МПГУ В.А. Гореликом, его учениками и коллегами: В.И Ерохи-ным, В.А. Кондратьевой, О.В. Муравьевой, P.P. Ибатуллиным, Р.В. Пе-ченкиным, И.А. Золтоевой и другими. В частности, указанными авторами совместно с В.Л. Матросовым и С.А. Ждановым исследовалось применение методов коррекции данных в задаче классификации. Научные изыскания в указанной области велись также и зарубежными исследователями среди которых можно выделить П.Амарало (P. Amaral), П. Барахоно (Р. Вага-hona), А. Дакс (A. Dax), Дж.Б. Розен (J.B. Rosen), С. Ван Хаффел (S. Van Haffel), П. Леммерлинг (P. Lemmerling). И все же, несмотря на интенсивные исследования последних лет, остались нерешенными многие проблемы.
Известные к настоящему времени методы матричной коррекции данных фактически сводятся к коррекции допустимой области задач линейного программирования. Указанные методы опираются на лемму Тихонова и ее модификации на нормы, отличные от евклидовой, и поэтому имеют специальный вид (оптимальные матрицы коррекции оказываются одноран-
говыми). Между тем, структура данных прикладной задачи может иметь более сложный вид: быть блочной, разреженной, иметь фиксированные элементы, строки или столбцы, коррекция которых запрещена. Такие задачи рассматривались и раньше, однако до сих пор не выработано единого подхода к их исследованию.
Кроме того, коррекция допустимой области задачи линейного программирования без обеспечения непустоты допустимой области соответствующей двойственной задачи, не гарантирует собственность скорректированной линейной оптимизационной модели.
В большинстве исследований исходная задача матричной коррекции данных сводится к некоторой задаче математического программирования, численные методы решения которой специально не рассматриваются. Исключениями могут служить работы В.А. Горелика, В.И. Ерохина, Р.В. Пе-ченкина, И.А. Золтоевой, в которых намечаются подходы к разработке соответствующих численных методов и алгоритмов матричной коррекции данных на основе TLN (Total Least Norm - алгоритм обобщенной наименьшей нормы) и метода Ньютона. Тем не менее, для того, чтобы матричная коррекция стала реально работающим инструментом анализа данных, формализуемых с помощью линейных оптимизационных моделей, необходимо более широко исследовать соответствующие численные методы и алгоритмы, добиваться их эффективности, проверять на большем количестве возникающих на практике задач.
Таким образом, актуальной научной проблемой является развитие методов и алгоритмов оптимальной совместной матричной коррекции данных двойственной пары несобственных задач линейного программирования, позволяющих включать несобственные линейные оптимизационные модели в число допустимых и конструктивно используемых методов теоретической информатики.
Объектом исследования является проблема матричной коррекции данных несобственных задач линейного программирования, возникающих в задачах оптимизации, классификации и гарантирующего оценивания параметров.
Предмет исследования составляют задачи совместной коррекции данных двойственной пары несобственных задач линейного программирования с евклидовой нормой матрицы в роли критерия качества коррекции.
Цель работы состоит в построении математического аппарата оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования и разработке соответствующих вычислительных алгоритмов.
В основу исследования положена гипотеза о том, что несобственная линейная оптимизационная модель является результатом неточно заданных или противоречивых исходных данных, ее оптимальная совместная матричная коррекция сводится к задаче оптимизации, позволяющей получить оптимальные по минимуму евклидовой нормы матрицы коррекции Н* или [Н* — /г*], гарантирующие собственность и структурный вид скорректированных линейных моделей
Г (А + Н*)х = Ъ, х ^ О, стх — max, ( {А + Н*)х = Ъ+ h*, х ^ 0, стх — max,
\ ит(А + Я*) ^ ст, Ъти -> min, ИЛИ \ ит(А + Я*) ^ ст, (6 + h*)Tu - min,
и соответствующие оптимальные векторы X* и и*.
Для достижения поставленной цели и проверки правильности выдвинутой гипотезы были поставлены следующие задачи:
1. Разработать методы оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования, не имеющих специальной структуры, а также соответствующих задач со специальной структурой в виде запрета на коррекцию отдельных элементов, столбцов, строк, блоков матрицы или расширенной матрицы коэффициентов их ограничений.
Исследовать условия разрешимости задач оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования.
Разработать, теоретически обосновать и проверить в вычислительных экспериментах алгоритмы решения перечисленных выше задач оптимальной совместной коррекции данных.
Исследовать приложения полученных методов к задачам распознавания образов с пересекающимися классами и задачам гарантирующего оценивания параметров.
Методологическую основу исследования составляют методы классической и вычислительной линейной алгебры, матричного анализа, математического программирования.
Научная новизна диссертации заключается в том в том, что предложены редукции задачи распознавания образов с пересекающимися классами и противоречивой задачи гарантирующего оценивания параметров к задаче оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования, для которой получены и теоретически обоснованы условия существования решения, гарантирующего собственность скорректированных задач и учитывающего их структуру, конструктивные формулы его построения и соответствующие численные алгоритмы ньютоновского типа с аналитическим вычислением производных.
Практическая значимость результатов. Предложенные в работе методы совместной коррекции данных двойственной пары несобственных задач линейного программирования могут быть использованы в задачах обработки данных, прогнозирования и управления, относящихся к области исследований специальности 05.13.17-теоретические основы информатики:
разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений;
разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил.
Основные положения, выносимые на защиту:
методы оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования, учитывающие ограничения на структуру корректирующей матрицы в виде запрета на коррекцию отдельных элементов, блоков, строк или столбцов систем ограничений задач линейного программирования;
необходимые условия существования решения задач оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования;
алгоритмы решения задач оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования.
Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций' (DOOR'07) (Владивосток, 2007 г.), Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006, 2007 гг.), Всероссийской научно-практической конференции "Информационные и коммуникационные технологии в образовании" (Борисоглебск, 2006, 2007, 2008, 2009 гг.) и научных семинарах кафедры прикладной математики и информатики физико-математического факультета Борисоглебского государственного педагогического института, кафедры ресурсосберегающих технологий Санкт-Петербургского государствен-
ного технологического института (технического университета), кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, отдела интеллектуальных систем Вычислительного центра имени А.А. Дородницына РАН.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы, содержащего 157 источников, и семи приложений. Полный объем диссертации составляет 180 страниц, основная часть - 150 страниц.
Матричное решение обратной задачи линейного программирования
Исследовать приложения полученных методов к задачам распознавания образов с пересекающимися классами и задачам гарантирующего оценивания параметров.
Методологическую основу исследования составляют методы классической и вычислительной линейной алгебры, матричного анализа, математического программирования.
Научная новизна диссертации заключается в том в том, что предложены редукции задачи распознавания образов с пересекающимися классами и противоречивой задачи гарантирующего оценивания параметров к задаче оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования, для которой получены и теоретически обоснованы условия существования решения, гарантирующего собственность скорректированных задач и учитывающего их структуру, конструктивные формулы его построения и соответствующие численные алгоритмы ньютоновского типа с аналитическим вычислением производных.
Практическая значимость результатов. Предложенные в работе методы совместной коррекции данных двойственной пары несобственных задач линейного программирования могут быть использованы в задачах обработки данных, прогнозирования и управления, относящихся к области исследований специальности 05.13.17-теоретические основы информатики: разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений; разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил.
Основные положения, выносимые на защиту: методы оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования, учитывающие ограничения на структуру корректирующей матрицы в виде запрета на коррекцию отдельных элементов, блоков, строк или столбцов систем ограничений задач линейного программирования; необходимые условия существования решения задач оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования; алгоритмы решения задач оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования. практические приложения методов оптимальной по минимуму евкли-довой матричной нормы совместной коррекции данных двойственной пары несобственных задач линейного программирования в задачах распознавания образов и гарантирующего оценивания параметров.
Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций" (DOOR 07) (Владивосток, 2007 г.), Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006, 2007 гг.), Всероссийской научно-практической конференции "Информационные и коммуникационные технологии в образовании" (Борисоглебск, 2006, 2007, 2008, 2009 гг.) и научных семинарах кафедры прикладной математики и информатики физико-математического факультета Борисоглебского государственного педагогического института, кафедры ресурсосберегающих технологий Санкт-Петербургского государственного технологического института (технического университета), кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, отдела интеллектуальных систем Вычислительного центра имени А.А. Дородницына РАН.
Основное содержание диссертации отражено в 10 публикациях [71] -[77], [87] - [89], в том числе в 1 статье [75] в журнале, включенном в перечень ВАК РФ.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы, содержащего 157 источников, и семи приложений. Полный объем диссертации составляет 180 страниц, основная часть - 150 страниц.
Оптимальная по минимуму евклидовой матричной нормы совместная коррекция данных двойственной пары несобственных задач линейного программирования с запретом изменения произвольных столбцов
Выражения (2.7), (2.14) наводят на мысль, что для получения приближенного решения исходной задачи нужно лишь определить минимум вспомогательной "оштрафованной" функции при достаточно больших значениях //. Однако, при увеличении параметра штрафа /z, как правило, отме чается увеличение "овражности" линий уровня вспомогательной функции. Методы, основанные на квадратичной аппроксимации целевой функции, не существенно зависят от вытянутости линий уровня целевых функций. Однако при практической реализации методов ньютоновского типа может наблюдаться эффект неустойчивости, связанный с плохой обусловленностью матриц. В этом случае, если минимизацию функции при большом /І начать из точки, которая не является достаточно близкой к точке минимума, то могут потребоваться слишком большие затраты времени ЭВМ и увеличиться вероятность прерывания процесса ввиду потери точности при вычислениях. По этой причине в практических алгоритмах метода штрафов лучше постепенно увеличивать параметр /і вместе с постепенным увеличением точности решения вспомогательных задач.
В настоящей главе исследованы задачи структурной оптимальной матричной коррекции данных двойственной пары несобственных задач линейного программирования.
Рассмотрен вариант задачи коррекции, при котором некоторая совместная подсистема системы ограничений прямой задачи исключается из коррекции. Данная задача рассмотрена также в двух постановках (коррекция только левой части и коррекция обеих частей совместно с целевой функцией). Задачи коррекции с запретом коррекции некоторых строк матрицы коэффициентов ограничений (в обеих постановках) также удалось свести к задаче безусловной минимизации, для решения которой предложен алгоритм.
Рассмотрен вариант задачи коррекции, при котором некоторая совместная подсистема системы ограничений двойственной задачи исключается из коррекции. Данная задача рассмотрена также в двух постановках (коррекция только левой части и коррекция обеих частей совместно с целевой функцией). Задачи коррекции с запретом коррекции некоторых столбцов матрицы систем ограничений (в обеих постановках), также удалось свести к задаче безусловной минимизации, для решения которой предложен алгоритм.
Для задачи коррекции двойственных пар несобственных задач линейного программирования с блочной структурой исследованы четыре варианта постановки задачи:- коррекции подвергаются все блоки расширенной матрицы коэффициентов; коррекции подвергаются все блоки матрицы коэффициентов ; верхний блок матрицы коэффициентов, связывающий все переменные прямой задачи, не корректируется; верхний блок расширенной матрицы коэффициентов, связывающий все переменные прямой задачи, не корректируется.
Все блочные задачи сведены к задачам безусловной минимизации, для каждой из которых разработан алгоритм решения.
Рассмотренный в первых двух главах метод, позволяющий свести задачу матричной коррекции двойственной пары несобственных задач линейного программирования к задаче безусловной минимизации функции, имеющей дробно-квадратичной вид, хорошо показал себя при исследовании несобственных задач линейного программирования, не имеющих специальной структуры, а также задач со специальной структурой в виде запрета коррекции некоторых столбцов, сторк или блоков матрицы коэффициентов.
На практике же может оказаться, что матрица коэффициентов систем ограничений двойственной пары задач линейного программирования имеет более сложную специальную структуру. Она может быть разреженной, иметь заданные нулевые элементы, или элементы, коррекция которых запрещена, т.е. может обладать дополнительными свойствами, которые в общем случае не обеспечиваются предложенными в предыдущих главах методами.
В данной главе рассматривается метод коррекции данных двойственных пар несобственных задач линейного программирования, основанный на векторизации матрицы, входящей в их системы ограничений, который поможет устранить эту трудность.
Совместная коррекция данных двойственной пары несобственных задач линейного программирования с использованием векторизации, гарантирующая существование заданных ненулевых решений
Для задачи коррекции только левых частей систем ограничений двойственной пары несобственных задач линейного программирования, не имеющих специальной структуры, дополнительно предложен метод коррекции, основанный на векторизации матрицы коэффициентов.
С опорой на метод коррекции, основанный на векторизации матрицы коэффициентов, предложен метод коррекции, позволяющий исключать из коррекции произвольные элементы матрицы коэффициентов. Данный метод может применяться для задач коррекции двойственных пар несобственных задач линейного программирования, обладающих специальной структурой (блочных, разреженных). Полученный метод также редуцирует задачу оптимальной матричной коррекции к задаче безусловной минимизации, для решения которой разработан алгоритм поиска решения.
В различных областях человеческой деятельности (экономике, финансах, медицине, бизнесе, геологии, химии, и др.) повседневно возникает необходимость решения задач анализа, прогноза и диагностики, выявления скрытых зависимостей и поддержки принятия оптимальных решений. Вследствие бурного роста объема информации, развития технологий ее сбора, хранения и организации в базах и хранилищах данных (в том числе интернет-технологий), точные методы анализа информации и моделирования исследуемых объектов зачастую отстают от потребностей реальной жизни. Здесь требуются универсальные и надежные подходы, пригодные для обработки информации из различных областей, в том числе для решения проблем, которые могут возникнуть в ближайшем будущем. В качестве подобного базиса могут быть использованы технологии и подходы математической теории распознавания и классификации [11], [12], [31], [33], [50], [54], [78]- [80], [94], [109], [110], [134], [139], [141],[145], [156].
Данные подходы в качестве исходной информации используют лишь наборы описаний-наблюдений объектов, предметов, ситуаций или процессов (выборки прецедентов), при этом каждое отдельное наблюдение-прецедент записывается в виде вектора значений отдельных его свойств-признаков. Выборки признаковых описаний являются простейшими стандартизованными представлениями первичных исходных данных, которые возникают в различных предметных областях в процессе сбора однотипной информации, и которые могут быть использованы для решения различных задач обработки данных.
Итак, исходной информацией в задачах распознавания являются описания объектов (ситуаций, предметов, явлений или процессов) 5 в виде векторов значений признаков для рассматриваемых объектов и значений некоторого "основного свойства" П(5) объекта 5. Свойство Г2(5) принимает конечное число значений.
Значения признаков Vj, j = 1, 2,..., п, характеризующих различные стороны-свойства объектов 5 для некоторых объектов 5i, 5г,..., 5ТО считаются известными. Предполагается, что существует функциональная связь между признаками и основным свойством (неизвестная пользователю). Задача распознавания (прогноза, идентификации, "классификации с учителем") состоит в определении значения свойства П(5) некоторого объекта 5 по информации (обучающей или эталонной выборке).
Рассмотрим алгоритм распознавания, основанные на построении разделяющих поверхностей [79]. В основе данного подхода лежат геометрические модели классов. Предполагается, что множеству объектов каждого класса соответствует определенная область в n-мерном признаковом пространстве. Данные области имеют достаточно простую форму и их можно разделить "простой" поверхностью (прежде всего линейной). Рассмотрим пример данного алгоритма, считая, что имеются лишь два класса объектов.
Задача построения линейной разделяющей поверхности (гиперплоскости) состоит в вычислении некоторой линейной относительно признаков функции [79] и использовании при классификации следующего упрощенного решающего правила:
Здесь Q(S) = 1 означает отнесение объекта в первый класс, fl(S) = 0 -отнесение во второй, Q(S) = А - отказ от классификации объекта.
Существуют различные варианты математических постановок критериев выбора f(v). Основной постановкой является поиск неизвестных коэффициентов Ai, А2,..., Ап, являющихся решением системы
Если система (4.3) совместна, то достаточно найти произвольное ее решение относительно неизвесных Ai, А2,..., An , для чего можно использовать релаксационные методы решения систем линейных неравенств [62], метод конечных приращений [55] алгоритмы линейного программирования и другие (рис. 4.1)
Однако заранее неизвестно, совместна данная система или нет. Обычно, вследствии различных проблем моделирования, система (4.3) оказывается именно несовместной, т.е. обучающие выборки невозможно безошибочно разделить гиперплоскостью. Поэтому на методы решения системы (4.3) обычно накладывают следующее ограничение: если система является совместной, то метод находит некоторое ее решение, если система несовместна - находится некоторое "обобщенное" решение системы. Под обобщенным решением Ai,A2,...,An системы (4.3) обычно понимают решение некоторой ее максимальной совместной подсистемы, либо любое другое решение, удовлетворяющее лицо принимающее решения (рис. 4.2).
Пусть каким-либо образом получено "обобщенное" решение системы (4.3) и, соответственно, коэффициенты Ai, А2,..., Ап линейной функции (4.1), определяющей положение разделяющей гиперплоскости.
Использование матричной коррекции данных несобственных задач линейного программирования в задачах обработки данных по методу гарантирующего оценивания параметров
Обе задачи сведены к задачам оптимальной по минимуму евклидовой матричной нормы коррекции данных двойственной пары несобственных задач линейного программирования. Проведены вычислительные эксперименты, подтверждающие работоспособность разработанных методов. В работе рассмотрены задачи оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойсвенной пары несобственных задач линейного программирования, которые, помимо несобственности, могут обладать дополнительным свойством, а именно, определенной структурой, связанной с природой задач: запретом изменения произвольных строк; запретом изменения произвольных столбцов; запретом изменения произвольных элементов; запретом изменения некоторых блоков. Все классы задач (кроме задач с запретом коррекции произвольных элементов) рассматривались в двух постановках: коррекции подвергается матрица коэффициентов системы ограничений (матрица А), или расширенная матрица ([А 6]) совместно с коэффициентами целевой функцией. Основные выводы: 1.
Разработан метод оптимальной по минимуму евклидовой,нормы матричной коррекции данных двойственной пары несобственных задач линейного программирования, который включает в себя: - использование минимального по евклидовой норме матричного решения обратной задачи линейного программирования; - алгоритмический учет неотрицательности части переменных; - использование штрафных функций для учета структуры (запрет коррециии отдельных строк, столбцов) корректируемой задачи; - способ декомпозиции задачи коррекции с фиксированными блоками на совокупность бесструктурных задач, связи между которыми учитываются алгоритмически и с помощью штрафов; - редукцию задачи матричной коррекции данных двойственной пары несобственных задач линейного программирования к вспомогательной задаче безусловной минимизации; - модификацию метода Марквардта (с аналитическим вычислением производных) для вспомогательной задачи безусловной минимизации, позволяющую решать задачи оптимальной матричной коррекции данных двойственной пары несобственных задач линейного программирования с возможными ограничениями в виде фиксированных строк, столбцов и блоков. 2. Разработан метод оптимальной по минимуму евклидовой нормы матричной коррекции данных двойственной пары несобственных задач ли нейного программирования, основанный на векторизации матрицы коэф фициентов систем ограничений, включающий в себя: - векторизацию минимального по евклидовой норме матричного решения обратной задачи линейного программирования; - алгоритмический учет неотрицательности части переменных; - использование булевых матриц для учета структуры фиксированных элементов корректируемой задачи; - редукцию задачи матричной коррекции данных двойственной пары несобственных задач линейного программирования к вспомогательной задаче безусловной минимизации; - модификацию метода
Марквардта (с аналитическим вычислением производных) для вспомогательной задачи безусловной минимизации, позволяющую решать задачи оптимальной матричной коррекции данных . двойственной пары несобственных задач линейного программирования с возможными ограничениями в виде некоторой совокупности фиксированных элементов. 3. Теоретически исследована область применимости предложенных методов матричной коррекции данных. Получены важные для практического применения и легко проверяемые по исходным данным необходимые условия разрешимости задачи оптимальной по минимуму евклидовой нормы матричной коррекции данных двойственной пары несобственных задач линейного программирования. 4. Показано, что предложенные в работе методы коррекции двойственных пар несобственных задач линейного программирования могут быть использованы для решения задач надежного и помехоустойчивого распознавания образов и анализа экспериментальных данных, относящихся к области исследований специальности 05.13.17 - теоретические основы информатики.