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

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

КРАСНИКОВ Александр Сергеевич

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

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

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

1 О ИЮН 2010

Москва

- 2010

004603848

Работа выполнена на кафедре прикладной математики и информатики

физико-математического факультета ГОУ ВПО "Борисоглебский государственный педагогический институт"

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

доцент

ЕРОХИН Владимир Иванович

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

профессор

ЦУРКОВ Владимир Иванович

кандидат физико-математических наук БАРАТОВА Екатерина Дмитриевна

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

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

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

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

Автореферат разослан • 11 апреля 2010 г.

н

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

МУРАВЬЁВА О.В.

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

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

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

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

Изучение методов коррекции данных несобственных задач линейного программирования является относительно новым направлением развития теоретической информатики. Предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить в работах А.Н. Тихонова. Систематические же исследования были начаты в 80-х годах (XX века) И.И. Ереминым, его учениками и коллегами: H.H. Астафьевым, A.A. Ватолиным, Вл.Д. Мазуровым, Л.Д. Поповым, В.Д. Скариным, С.П. Трофимовым, В.Н. Фроловым и другими. Ф.П. Васильевым рассматривались методы коррекции правой части ограничений двойственной пары задач линейного программирования, причем все вспомогательные задачи были также задачами линейного программирования. В конце 90-х годов (XX в.) исследования в данной области были продолжены, и продолжаются в настоящее время в ВЦ им. A.A. Дородницына РАН и МПГУ В.А. Гореликом, его учениками и коллегами: В.И Ерохи-ным, В.А. Кондратьевой, О.В. Муравьевой, P.P. Ибатуллиным, Р.В. Пе-ченкиным, И.А. Золтоевой и другими. В частности, указанными авторами совместно с B.JI. Матросовым и С.А. Ждановым исследовалось применение методов коррекции данных в задаче классификации. Научные изыскания в указанной области велись также и зарубежными исследователями среди которых можно выделить П.Амарало (P. Amaral), П. Барахоно (Р. Вага-hona), А. Дакс (А. Dax), Дж.Б. Розен (J.B. Rosen), С. Ван Хаффел (S. Van Haffel), П. Леммерлинг (P. Lemmerling). И все же, несмотря на интенсивные исследования последних лет, остались нерешенными многие проблемы.

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

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

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

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

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

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

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

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

В основу исследования положена гипотеза о том, что несобственная линейная оптимизационная модель является результатом неточно заданных или противоречивых исходных данных, ее оптимальная совместная матричная коррекция сводится к задаче оптимизации, позволяющей получить оптимальные по минимуму евклидовой нормы матрицы коррекции Н* или [Н* — h*], гарантирующие собственность и структурный вид скорректированных линейных моделей

( (А + Н')х - Ь, х > 0, стх -4 max, j {А + Н')х = b + h', х > 0, стх max, \ ит{А + Я*) > ст, Ьти -> min, МИ \ ит(А + //*)> ст, (Ь + h*f и min, и соответствующие оптимальные векторы х* и и*.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций' (ВОСЖ'07) (Владивосток, 2007 г.), Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006, 2007 гг.), Всероссийской научно-практической конференции "Информационные и коммуникационные технологии в образовании" (Борисоглебск, 2006, 2007, 2008, 2009 гг.) и научных семинарах кафедры прикладной математики и информатики физико-математического факультета Борисоглебского государственного педагогического института, кафедры ресурсосберегающих технологий Санкт-Петербургского государствен-

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

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

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

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

В §1.1 вводится понятие матричной коррекции данных и даются постановки задач матричной коррекции данных двойственной пары несобственных задач линейного программирования в случае, когда матрица коэффициентов их систем ограничений не имеет специальной структуры. Для определенности считается, что прямая задача L(A, b, с) : Ах = 6, х ^ 0, ¿Fx max записана в канонической форме, а двойственная к ней

L*(A,b,c) : итА ^ сг, Ьти -» min - в стандартной. Выбор конкретных форм записи задач линейного программирования позволяет упростить некоторые выкладки, но не умаляет общности рассуждений, так как получаемые результаты всегда могут быть соответствующим образом адаптированы для задач линейного программирования, записанных в любых других формах.

В §1.2 исследована задача о матричном решении обратной задачи линейного программирования.

Теорема 1.2.1. Семейство матриц, гарантирующих, что при заданных b G Ет и с € К" вектор х S R", х > 0, принадлежит множеству решений задачи линейного программирования L(A,6,с), а вектор й е Rm. й ф 0, принадлежит множеству решений двойственной задачи линейного программирования L*(A,b,c), существует тогда и только тогда, когда выполняется условие стх — bTü — а, и описывается формулой А = А + А А, где ^ fox^ iicP* ctux^

А — -=— + з^---- матрица с минимальной евклидовой нормой,

х1 х и1 ü й1 их1 х И - . . И ]т й, - / °> если с; < 0 и ж, = 0, и - ЦП unJ , щ ^ в ПрОТИВНОМ случае,

АА - произвольная матрица такая, что vFAA = 0, ААх = 0.

1.7.12 11ЬИ2 1И12 При этом Л 2 = JLJL+"JL-

INI2 IMI2 М2И2

Здесь и далее знаком || ■ || обозначаем, в зависимости от контекста, евклидову матричную или векторную норму. Для векторов х и у из R" пишем: х ^ у, если х,- ^ % при всех i = 1,..., п; х > у, если х ^ у, но х ф у.

В §1.4 с опорой на теорему 1.2.1 получен метод оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двой-

ственной пары несобственных задач линейного программирования Ь(А, Ь, с) и Ь*(А, Ъ, с) без учета их структуры.

Задача -щ' Найти матрицу \Н* -Л*] с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач Ь(А + Н*,Ь+к*,с) и Ь* (А + Н*, Ь + Ь*, с), а также векторы х* ни*, являющиеся их решениями.

Задача £>я: Найти матрицу Н* с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач Ь(А+ Н*,Ь,д) и Ь*(А + Н*, Ь, с), а также векторы х* и и*, являющиеся их решениями.

Теорема 1.4.1. Задачи и Вн эквивалентны задаче безуслов-

ной минимизации

Ш «) = 116 " + Щ + ^ - ^ - (бГц - цТЛз;)2 Ч. шш (1)

где _ г 0, если решается задача

\ 1, если решается задача £)[я

Ыстх — Ъ^и]

х =х(х) = <1\а%(х)х, и = и(х,й) = й+(1 — Ь)--^-, (2)

¿ = й(х,й) = [ё1 ... ¿!=/0, если^-А^Ои^О,

4 ' 1 ' (_ (с —Л1 г»);, в противном случае.

При этом, если векторы х*, й* являются решением задачи (1) и Ф(х*, й*) > 0, то единственное решение задачи Ощ _л] или (в зависимости от параметра £) выражается формулами

г{Ьти* - и*тАх*)и* (Ъти* - стх*)и* ¿(6 - Ах*)

h* =

U*TU*(t + X*TX*) U*TU* t -f х*тх*'

Н*_(Ь- Ах*)х*т u*d*T (ihTu* - и*тАх*)и*х*т

t + x*Tx* + u*Tu* u,Tu*{t + x*Tx*) '

где x* = x(i*), и* — u(i*,w"), d* — d(x*,u*). Векторы x*, и* являются решением скорректированных задач.

Заметим, что в (2) алгоритмически учитываются ограничения х ^ О, (Fx — Ьти.

В §1.5 дано необходимое условие разрешимости задач D\h -h] и Он-

Теорема 1.5.1. Для разрешимости задач D[h и Пц необходимо, чтобы выполнялось условие гапк([Л 6]) = min{m, п +1}, где тип- число строк и столбцов матрицы А соответственно.

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

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

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

, х ^ 0, сТх —>■ max,

г г„., (3)

■ X

т

mm,

причем подсистема Ajx — bf, х ^ 0 является совместной (/ от англ. fixed. - фиксированный, с от англ. corrected - корректируемый).

Задача D^g°'hy Найти матрицу [Н* -h*] с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач

bf bc + h'

АСЛН*

bf К + h

(4)

а также векторы хаи, являющиеся их решением.

Задача Drff°s. Найти матрицу Н* с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач

а также векторы х* и и*, являющиеся их решением. Перепишем (3) равносильно в виде

А/х = Ь/, Асх = bc, х ^ 0, (с — AfUf)Tx шах, и^Ас ^ ст — UjAj, b^Uc —> min. Из (4) видно, что задачи D]Jj"-h\ > DW могут быть сведены к задачам D[h и Djj соответственно с параметрами Ас, Ьс, сс = с —Aj и/ и дополнительным ограничением А/х = bf. С опорой на теорему 1.4.1 получаем, что решение задач DT^lhy Dr^ws указывает следующая Теорема 2.1.1. Задачи Dr{^h]

и Dэквивалентны задаче Фrows(x,üf,üc) = II[Я -/i]||2 .min , (5)

при ограничении AfX = bf, где

{

г, и/, ис

||[Я =

_ IIЬс - Лсх||2 , ||de||2 , t(bTcuc - <*хУ (%ис - uTcAcxf

t + ||х|Р t =

■ +

: +

IMa(f + Nla)'

О, если решается задача ,

—ifbws

1, если решается задача Цщ^щ, х — х(§) = diag(5)i, сс = с с(й/) = с — Afüf,

bc(c£x - ЬТсйс)

dc = dc(i,ü/,üc)

U c(x,üf,üc) =Üc + (l-t) ~(dc)!

,(dc)n

bjbc

/. \ _ f 0, если (cc - A^uc)i < 0 и i| = 0, 1 (Cc ~ A^uc)i,b противном случае.

При этом, если векторы х*, йй*с являются решением задачи (5) и Фгаи!3{х*,Щ,й*с) > 0, то единственное решение задачи или (в

зависимости от параметра £), связанное с указанными векторами, выражается формулами

Щч*с-ч?Асх*)ч\ 1{ЬС-АСХ\)

и*ти*г г + х*тх* '

h* =

ufu*c{t + х*тх*) ut_(bc-Acx*)x*T , Kdf (bTcu'c-u?Acx*)u*ex*T

tl = -Г"---1----

t + xtTx*

u*Tut

u?u*c{t + x*Tx*)

где x* = x(x*), с* = cc(üj), и* = uc(i*,üj,ü*), d* = dc(x\ й*}, ü*c). Векторы

ж , и =

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

С использованием метода, при котором квадрат нормы расширенной матрицы коррекции ¡([Я —h]\\2 есть целевая функция, а квадрат нормы вектора невязки ||6/ — Л/х||2 имеет смысл штрафной функции была получена редукция задачи (5) к задаче безусловной оптимизации. Получены условия сходимости метода штрафов.

Теорема 2.1.2. Пусть допустимое множество G в задаче (5) ограничено, тогда min Фг™*(х,й,,йс) = lim inf Ф^3(х, üf,üc, и), где (x,ü/,üc)eG l'->oo(i,ü;,üc)£ Р ^

$r™'(x,üf,üc,p) = Фгошз(х,й},йс) + ß\\Afx{x) - bf\\2, Р- компакт такой, что G С Р.

Если последовательность точек £ Р (к = 1,2,...) та-

кою, что Ф™Ш8(ж W, üf\ й{с\ (№) < inf Ф™'{х,й], йс, цМ) + еЮ, где

(£,й/,йс)еР

оо, е® 0, > О (к = 1,2,...), то л;обая предельная точка этой последовательности является решением задачи (5).

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

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

(И/

(6)

min,

причем подсистема uTAf ^ с/ является совместной (/ от англ. fixed, - фиксированный, с от англ. corrected - корректируемый).

Задача Найти матрицу [Я* -Л*] с минимальной евклидовой

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

а также векторы х* и и*, являющиеся их решением.

Задача Dc^s. Найти матрицу Я* с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач

L ([А/ Ас + Н*],Ь, Щ) , L* ([А/ Ас + Я*],6, Щ) ,

а также векторы х* и и*, являющиеся их решением. Перепишем (6) равносильно в виде

Г Асхс - b- AjXf, Xf Ji 0, хс ^ 0, £хс -» max, , .

| UjAf ^ с?-, ^ с£, (6 - Ajxjyu min. '

Из (7) видно, что задачи могут быть сведены к зада-

чам -С^я-л] и 1>я соответственно, с параметрами Лс, bc = b ~ Ajxj, сс и дополнительными ограничениями с/, ^ 0.

Аналогично теореме 2.1.1. доказывается Теорема 2.2.1. Задачи и L>|fs эквивалентны задаче

$cols(xJ,xc,ü) = \\lH min , (8)

X),XC,Ü

при ограничении иTAj ^ с/, где

II[Я -Л]||2 =

\\Ьс-Асхс\\\\Щ\\фТи-<*хс)2 {Ьтси - итАсхс)2

*+1Ыа"+ нр

+

I

№ Н12(* + Ы2)'

если решается задача О^11, если решается задача

х/= - 6\щ(х/)х/, хс = хс(яс) = сИа§(5с)хс, Ьс = Ьс(а;/) = Ь-А/х/,

Ьс{с?хс - Ь^й)

-{5

¿с = с1с(£с, Й) =

и — и(£/, хс, й) = й + (1 — £)

> (4)[

_ Г 0, если (сс -

~ \ (Сс ~ 4")/,

- А^и)1 < О и (хс)1 = о, в противном случае.

При этом, если векторы Щ, х*с, й* являются решением задачи (8) и Фс°1з(хрх*с,й*) > 0, то единственное решение задачи или В^1" (в

зависимости от параметра ¿) выражается формулами

ФХт-и*тАсх*сУ (Ь1ти* - £х*)и* т-Асх*с)

Н* =

и*ти*(г + х*/х*с)

I + х?х*с

Н. = (6*С-Асх;)х1т |

с

■ и*тАсх*с)и*х*ст

I + х?х*с

и* игТи*^ + Х*ТХ*с) '

где х) = х/(£}), ж* = хс(£*), 6* = Ьс(ж)), и* = и(5},ж*,й*),

Гж*1

— й*), ¿1 = сЦж*, й*). Векторы х* = I , и* являются решением

хс

скорректированных задач.

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

В §2.3 предложен метод совместной коррекции данных двойственной пары несобственных задач линейного программирования Ь(А, Ь, с) и Ь*(А,Ь,с), матрица систем ограничений которых имеет следующую блочную структуру:

А =

- А №1 1 Г^юи А\02] -¿[ОвТ

Аш 0 0 Л[11 0 0

0 0 = 0 АЩ 0

1. о 0 [ 0 6

В соответствии со структурой матрицы А вводятся блочные представления векторов Ь, и, с, х:

6 =

Г [01 1 т Ь\21 , и = Г "[01 1 , С = Г с[111 С[21 , х = Г ж1111 (9)

1 Ь[Б) \ 1 "[51 ]

и формулируются задачи "блочной" коррекции.

Задача Найти матрицу [Н* — /г*] вида

н=

Щ 02] H\osî

0 0

0 0

Lи 0 %U

h =

Ж

s

iKs) J

(10)

с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач L(A + Я*, b + h*, с) и L*(A + Я*, b + h*,c), а также векторы ж* и«', являющиеся их решениями.

Задача Dt1jtalblock. Найти матрицу Я* вида (10) с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач L(A + H*,b,c) и L*(A + H*, b, с), a также векторы х* и и*, являющиеся их решениями.

В следующих двух задачах считается, что подсистема Ащх = 6[о], х ^ 0 является совместной и исключается из коррекции.

Задача Найти матрицу [Я* — h*] вида

0

Н =

0

Мщ cJ u 0

0 0

L ^ 0-1 ... H[S]\

h =

h

ËL

(П)

с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач Ь{А + Я*, Ь + И*, с) и Ь*(А + Я", Ъ + К*, с), а также векторы х* и и*, являющиеся их решениями.

Задача Найти матрицу Я* вида (11) с минимальной евкли-

довой нормой, гарантирующую собственность скорректированных задач Ь(А + Я*,Ь, с) и Ь*{А + Н*,Ь,с), а также векторы х* и и*, являющиеся их решениями.

Перепишем блочные задачи Ь(А, Ь, с), Ь*(А, Ь, с) равносильно, в виде Г : ^и^и = Ь[ф > 0, -4 тах,

где 5

Л[0в]Я[я] = Ь[0ф С[я] = С[з]{и[0]) = С[я] - >1[оа]'"[0]. X] &[0в] = 6[0]> (13)

¿=1

Таким образом, задачи или Оь^оск сводятся к й задачам

или Б^"13 соответственно, с дополнительными связывающими их условиями (13). Используя для решения каждой из пар задач (12) теорему 2.1.1., и учитывая, что

(12)

«=1

s

m -ft]ii2=Ell№] -МП2. II^-AOFIP-Eiivi-AO^WII

S = 1

приходим к тому, что справедлива

Теорема 2.3.2. Задачи и эквивалентны задаче мини-

мизации

при ограничении 8-1

= Ь[0],

(14)

«•[Jj "[»JV-li - {?;

где „

"Mll =

ЦЬМ - H<y|2 t(bg]UM - C^M)2 (bg]U[l] - ц^мдм)а

i + lkwll2 llu[s]ll2 ll«wll2 ll«wll2(i+ll®wll2) '

_ f 0, если решается задача DHocfc, — | 1, если решается задача х — х(ж) = diag(i)i,

C[S] = cw(ü[0j) = cw - Лр^йр],

6[sj(C[siXrs] — ЬыЙи)

«w = uw(^w»ü[0], «и) = «H + (1 -1)--i-^Tjrr—u-,

d[;](i[3],ä[o],ü[s]) = [(d[3])\ ■■■ (d[3]k] , если (cw - Afau^i < 0 и ц,,], = 0, в противном случае.

При этом, если векторы ..., ü*0j.....являются решением

задачи (14) и ФЫос*(ж^..., х^, й^,..., й^) > 0, то единственное решение задачи D^^ или Dgock (в зависимости от параметра t) выражается формулами

u[I]u[s}^ + 2;м:ги) uwuw tJrX[I]xU

Н* = ~ ^М^М ! цм^м ^"м ~ цм Лма;м)цма;м W t + x$xU uWwW "^"и^ + ^й^и)

где х* = х(х*), с^си^,), u^ =uM(£[*s],ü['0],ü^]), rff.j = d[e],äp,],«f«]),

s = 1,..., S. Векторы x*, и*, составленные в соответствии с (9), являются решением скорректированных задач.

Для учета ограничений (15) при решении задачи (14) также, как и при решении задач (5) и (8), использовалась соответствующая модификация метода штафной функции. Получены условия сходимости метода штрафов.

Задачи £)МаШоск и Qtotaibiock также сведены к задачам безусловной минимизации.

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

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

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

В §3.1 вводится понятие векторизации матрицы как параметрической зависимости матрицы коэффициентов А S Rmxn и матрицы коррекции Я € Ешх" несобственных задач линейного программирования от некоторых векторов а € и Л £ R^ соответственно, где N = т ■ п, причем справедливы равенства

/ А(а)х = Х(х)а, ( H{h)x = Х(х)П,

\ А(а)Ти = U{u)a, \ H{h)Tu = U(u)h.

Здесь же даются формулы построения векторизованных задач: А{а) = {a{j | <nj = Q(j_i)n+j, г = 1,. • •, m, j = l,...,n},

H{h) = {hij | hij = fi(i-i)n+j, i = 1,..., m, j = 1,...,n}, X{x) = {(xr,s) 6 ЕтхЛГ|хГ)(г_1)п+а = xs, r = 1,..., m, s = 1,..., n}, U(u) = {(ur,.,) € RnxJV|u8i(r_1)n+s = ur, r = 1,..., m, s = 1,... ,n}.

Заметим, что матрица А состоит из тех же элементов, что и вектор а, а значит их евклидовы нормы совпадают. Тоже самое справедливо для матрицы Я и вектора h.

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

В §3.5 решена задача коррекции со структурным ограничением на матрицу коррекции, а именно запретом изменения некоторой совокупности элементов матрицы системы ограничений.

Задача Пусть задачи L(A, b, с) и L*(A,b,c) являются несобственными. Пусть также дано множество

К = {(г, j)(коррекция элементов a,j запрещена}.

Требуется найти матрицу Я* с минимальной евклидовой нормой, гарантирующую собственность скорректированных задач L(A + H*,b,c) и L*(A + Я*, 6, с), а также векторы х* и и', являющиеся их решением. При этом должно выполняться условие Н*^ — 0, если (i,j) £ К, г = 1,... , т, j = 1,..., п.

Теорема 3.5.1. Задача Dj" эквивалентна задаче безусловной минимизации

<Hiix{x, й) = rTGQTQGTr min, (16)

i,ü

где Q = GfP^G.,, P = GsGTGGj, Gs = WSG, Ws - матрица, получаемая из единичной матрицы порядка (m + п) путем удаления строки с номером s.

Номер s выбирается в соответствии со следующим правилом если 1 ^ s ^ m, reu, / О,

если т < s ^ т + п, то xs-m ф 0.

г = г(х,й) —

Ь - Ах

Х(х и(и

■V,

V - матрица, получаемая из единичной матрицы порядка (т • п), путем удаления столбцов с номерами ((г — 1 )п + j) , (г, у) б К,

Ыс?х — Ь^и} х = х(я) = diag(i)í, и = и(х, й) = й + ■

ьч

(I = в(£, й) = • (с - Ати),

... ¿„Г' «5, = /?' если (с - Лти), < 0 и ж, = О, 1 ' ' ' 1 1, в противном случае.

При этом, если векторы £*, й* являются решением задачи (16) и Ф(ж*, й*) > 0, то единственное решение задачи Бц находится из известного соотношения Н* = Я(Г), где П* = У&ЛС^СС^У^^г, С = <?(£*, и*), = х*=х(х*), и* = \1(х*,й*), ¿* = й(х*,й*).

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

Границы применимости предложенного метода дает

Лемма 3.5.2. Для разрешимости задачи БдХ методом векторизации необходимо чтобы:

1. Количество корректируемых элементов было не меньше т + п — 1, где тип- число строк и столбцов матрицы А соответственно;

2. В каждой строке и каждом столбце матрицы А корректировалось хотя бы по одному элементу;

3. Элемент а^ не был единственным корректируемым элементов в строке г (г = 1,..., т) и столбце 3 = 1,..., п).

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

В §4.1. исследуется решение задачи распознавания образов с пересекающимися классами.

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

/Н = Ат + А2и2 + ... + Ал + 1 = Ати + 1 (17)

и использовании при классификации следующего решающего правила:

{отнесение объекта в первый класс, если /(5) > О, отказ от классификации объекта, если /(3) = О, отнесение объекта во второй класс, если /(5) < 0.

Существуют различные варианты математических постановок критериев выбора /(«). Основной постановкой является поиск неизвестных коэффициентов А), А2,..., А„, являющихся решением системы

' А1и1(51) 4- Аг^й) + ... + А„«„(51) + 1 > 0,

Ацч^т,) + А2и2(£т1) + ... 4- А„%(5тл + 1 > 0, Ахг;1(5т1+1) + А2и2(5т1+1) 4-... + АЛ(5т1+1) + 1 < 0, ^

, А1«х(5т) + А2г;2(Зт) + ... + Апьп{8т) + 1 < 0.

Однако заранее неизвестно, совместна данная система или нет. Поэтому на методы решения системы (18) обычно накладывают следующее ограничение: если система является совместной, то метод находит некоторое ее решение, если система несовместна - находится некоторое "обобщенное" решение системы. Под обобщенным решением Ах, Аг,..., А„ системы (18)

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

Пусть каким-либо образом получено "обобщенное" решение системы (18) и, соответственно, коэффициенты Ai,A2,...,АП линейной функции (17), определяющей положение разделяющей гиперплоскости.

Сформулируем и решим следующую задачу. Минимально "исправить" положение объектов в признаковом пространстве таким образом, чтобы можно было провести новую разделяющую гиперплоскость, по возможности "близкую" к исходной и строго разделяющую классы. Назовем эту задачу задачей Рг и формализуем ее: ||A-Ä||i -¡-min, ||£||2 min, (V + E)-X = p,

где

(19)

V

Vl,l Vl,n ei,i • Ci,T»

rvi vmul ■ Vm-i ,n , E = Ei

Vi. Vmi+1,1 ' • ^mi+1,71 E2, emi+l,l ' em, 1

Ai" "Ai" ■5i-V

vy - Vj(Si), X = ä'„ ii .A„. . P = ßm 1.

Г f Qu если ßi > О, • \ а в противном

случае,

для г = 1,2,... ,7Tii,

r f Qi, если ßi < 0, ■ I 1 _ I о

ь ={-ав противном случае, для * = mi + 1, пц + 2,..., тп,

Qi = AiUi,i + Ä2Vi,2 + - • • + Anvi!,i-f 1, er > 0 - некоторое число, г = 1,2, j = 1,2,.'. .,п.

Введем замену ip = А — А, тогда задача (19) примет вид W\\ min, ||Z>||2 -> min, (V + D)-il> = p-V-\ = b, причем матрицы E и D связаны соотношением D -1р = Е ■ А,

ПОЛОЖИВ 2Г(1). = + fy), x(2)j = - Ф]), для j = 1,2,..., п

получим Х(ху ^ 0, X(2)j ^ о, l/)j = 1(1). - x(2)j, \lpj\ = + Х{2)р и, соответственно

п п

,771,

(20)

h п

Х{1) Х{2)\

llalli = Ш = + X(2)í) = га j=l j=1

• (К + Z?) - ^ - (К + D) ■ (s(I) - х{2}) = \V + А -К - £>г] ■ И,

причем, матрицы D, Di и £>2 связаны соотношением Dip = DyX^ — L>2X(2), hn ~ единичный вектор порядко 2тг.

Теперь задачу (20) можно переписать следующим образом: из всех возможных матриц Н — [Di —D2} найти матрицу Н* с минимальной евклидовой нормой такую, чтобы задача линейного программирования (А + Н*)х — Ь, х ^ 0, стх max,

оказалась собственной, где х =

6 е А, Н е RmxJV, N — 2п + т.'

есть решение задачи

Далее, как было показано в предыдущих параграфах, получаем задачу £>д, или задачи £)™'3, 1Уц3, 1){\х, при необходимости учета структуры задачи Рт.

В §4.2. исследуется решение задачи гарантирующего оценивания параметров. Рассматривается простейшая задача гарантирующего оценивания параметров ("схема бортиков"), в предположении, что уравнения измерений имеют вид

Ъ = у?<1+= 1,2, ...,п, где - измерения, q £ Мт - неизвестный вектор параметров, У^ £ Ет -заданные векторы, д^ - ошибки измерений; для типичных случаев тп <С п, Задача состоит в оценке параметра I* = Ътц,где 6 £ К"1 - заданный вектор. Предполагается также, что данных для статистического описания недостаточно, и поэтому считается что вектор измерений д} = [£>1 ... ¿?П]Т принадлежит параллелепипеду Р = {д £ К" | ^ а^, ] = 1,2,...,п} ,где С], з = 1,2,..., п - заданные неотрицательные числа.

Л «

Введем алгоритм оценивания / = X) Фзг]' гДе Фз ~ весовые коэф-

з=1

фициенты оценивателя, подлежащие определению. Тогда ошибка оценивания I — I* зависит от оценивателя ф, неизвестного параметра д и реализации шума измерений д. Как было показано Лидовым М.Л. вектор

ф* = [ф\ Ф1 ... ф*п]'Г является оптимальным оцепнивателем тогда и толь-

Га;?,, £ КП1

ко тогда, когда ф* = х^ — х^, где х* =

линейного программирования

Ах = Ь, х ^ 0, сгж -»• шах, (21)

где с = - [а\ ... ап ах ... ап]т, А = [V -V].

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

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

Ц = (Ц + Я + в], л' = 1,2,...,п, "близкая" к исходной. Причем матрица коррекции Ю данной задачи и матрица коррекции Н задачи линейного программирования (21) связаны соотношением Нх = Бф.

Вычислительные эксперименты, проведенные с использованием системы Ма^аЬ для всех рассмотренных в диссертации задач, показали работоспособность предложенных методов коррекции.

В заключении приведены основные результаты, полученные в диссертации.

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

5(2) е

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

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

- использование минимального по евклидовой норме матричного решения обратной задачи линейного программирования;

- алгоритмический учет неотрицательности части переменных;

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

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

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

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

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

- векторизацию минимального по евклидовой норме матричного решения обратной задачи линейного программирования;

- алгоритмический учет неотрицательности части переменных;

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

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

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

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

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

Основное содержание диссертации отражено в работах:

Ерохин В.И., Красников A.C. Матричная коррекция двойственной пары несобственных задач линейного программирования с блочной структурой // Журнал вычислительной математики и математической физики, 2008. Т. 48. № 1. С. 80-89. - 0,63 п.л. (авторский вклад - 50 %)

2. Красников A.C. О матричном решении обратной задачи линейного программирования с минимальной евклидовой нормой /'' Научное обозрение, 2009, № 4. С. 37-39. - 0,31 п.л.

3. Красников A.C. Необходимое условие разрешимости проблемы оптимальной матричной коррекции двойственной пары несобственных задач линейного программирования /7 Научное обозрение, 2009. № 4. С. 39-42. -0,44 п.л.

4. Красников A.C., Ерохин В.И. Матричная коррекция двойственной пары несобственных задач линейного программирования с блочной структурой // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. - Екатеринбург: УрО РАН, 2007. С 330-334. - 0,31 п.л. (авторский вклад - 50 %)

5. Ерохин В.И., Красников A.C. Матричная коррекция двойственной пары блочных несобственных задач линейного программирования /7 Российская конференция "Дискретная оптимизация и исследование операций": Материалы конференции. - Новосибирск: Изд-во Института математики, 2007. С. 104. - 0,06 п.л. (авторский вклад - 50 %)

6. Ерохин В.И., Красников A.C. Матричная коррекция блочных несобственных задач линейного программирования // Совершенствование преподавания физико-математических дисциплин в педвузе и школе: Сб. науч. тр. - Вып. 4. - Борисоглебск: Борисоглебский госпединститут, 2007. С. 75-8G. - 0,72 п.л. (авторский вклад - 50 %)

7. Ерохин В.И., Красников A.C. Матричная коррекция взаимодвой-ственпых задач линейного программирования с условием неположительности матрицы коррекции // М-лы ежегод. науч. конф. преподавателей и студентов БГПИ по итогам НИР за 2006 год. Естественные науки / Под ред. А.Ф.Тараканова. - Борисоглебск: ГОУ ВПО "БГПИ", 2007." С.19-21. -0,13 и.л. (авторский вклад - 50 %)

8. Ерохин В.И., Красников A.C. Использование метода Марквардта для матричной коррекции несобственных задач линейного программирования /7 М-лы ежегод. науч. конф. преподавателей и студентов. Работы преподавателей. / Под ред. Н.М. Муравьевой. - Борисоглебск: ГОУ ВПО "БГПИ", 2009. С. 143 - 146. - 0,25 п.л. (авторский вклад - 50 %)

9. Ерохин В.И., Красников A.C. Матричная коррекция двойственной пары задач линейного программирования со специальной структурой '/ Информационные и коммуникационные технологии в образовании. Сб. м-лов VII Вссрос. науч.-практ. конф. - Борисоглебск: ГОУ ВПО "БГПИ", 2006. С. 110-114. - 0,25 п.л. (авторский вклад - 50 %)

10. Ерохин В.И., Красников A.C. Матричная коррекция несобственных задач линейного программирования с теплицевой матрицей ограничений // Информационные и коммуникационные технологии в образовании. Сб. м-лов IX Международ, науч.-практ. конф. - Борисоглебск: ГОУ ВПО "БГПИ", 2008. С. 194-199. - 0,28 п.л. (авторский вклад ■ 50 %) j/Q

Подп. к печ. 22.04.2010 Объем 1 п.л. Заказ № 52 Тир 100 экз. Типография МПГУ

Список используемых обозначений

Введение

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

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

1.2 Матричное решение обратной задачи линейного программирования

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

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

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

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

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

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

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

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

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

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

3.1 Векторизация задачи матричной коррекции.

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

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

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

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

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

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

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

Актуальность темы исследования. Линейные оптимизационные модели находят многочисленные приложения в технике, экономике [7], [9] [10], [29], [30], [53], [63], [82], [84], [85], [93], [121] - [123], задачах помехоустойчивого анализа экспериментальных данных, гарантирующего оценивания параметров [8], [90] - [92], [97], [138], [157], распознавания образов и классификации [11], [12], [31], [33], [50], [54], [78] - [80], [94], [109], [110], [134], [139], [141], [145], [156].

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

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

Изучение методов коррекции данных несобственных задач линейного программирования является относительно новым направлением развития теоретической информатики. Предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить в работах А.Н. Тихонова [115] - [119]. Систематические же исследования в данной области (с введением соответствующей терминологии) были начаты в 80-х годах (XX века) И.И. Еремиными [58] - [68], его учениками и коллегами: Н.Н. Астафьевым [1] - [3], А.А. Ватолиным [19] - [26], [154], [155], Вл.Д. Мазуровым, [95], [96], Л.Д. Поповым [104] - [107], В.Д. Ска-риным [111] - [113], С.П. Трофимовым [120], В.Н. Фроловым [121] - [124] и другими. В перечисленных работах рассматриваются несобственные задачи линейного и выпуклого программирования, вводится классификация несобственных задач линейного программирования [64], строится и исследуется теория двойственности, вводятся и исследуются дискретные аппроксимации решений - комитетные конструкции, предлагаются различные постановки и методы решения задач полной или частичной (правая часть системы уравнений или неравенств) параметрической коррекции и их содержательная, в основном экономическая, интерпретация. В большинстве исследований рассматривается коррекция по вектору правой части ограничений и коэффициентам вектора целевой функции. Ф.П. Васильевым [13] - [17] рассматривались методы коррекции правой части ограничений двойственной пары задач линейного программирования, причем все вспомогательные задачи были также задачами линейного программирования. В конце 90-х годов (XX в.) исследования в области коррекции несобственных задач линейного программирования были продолжены (а также продолжаются в настоящее время) в ВЦ им. А.А. Дородницына РАН и МПГУ В.А. Гореликом [34] - [52], [135] - [136], [98], [100] его учениками и коллегами: В.И. Ерохиным [69] [70], В А. Кондратьевой [86], О.В. Муравьевой [101], P.P. Ибатуллиным [83], Р.В. Печенкиным [103], [137], И.А. Золтоевой [81] и другими. Указанными авторами широко исследовалась коррекция несовместных систем линейных алгебраических уравнений с условием неотрицательности решения, показана их тесная связь с задачами матричной корекции несобственных задач линейного программирования. В их работах рассмотрены несобственные задачи линейного программирования 1-го и 3-го рода в классификации [64], т.е. задачи линейного программирования с несовместными системами ограничений. В качестве вспомогательных, решены задачи коррекции несовместных систем линейных уравнений и неравенств. Коррекция задачи линейного программирования рассматривалась как двухкритериальная проблема максимизации исходного линейного критерия и минимизации нормы корректирующей матрицы ограничений. Эта проблема была формализована как задача минимизации нормы корректирующей матрицы при ограничении снизу на значение исходного критерия. Получены условия существования решения всех поставленных задач и аналитические выражения решений через собственные числа и векторы специальных матриц. В качестве приложения решена линейная задача аппроксимации по критерию минимального расстояния. Кроме того, с использованием некоторых специфических свойств одноранговых матриц и чебышевской матричной нормы, удалось получить решение задачи минимаксной коррекции матрицы коэффициентов несобственной задачи линейного программирования в канонической форме путем сведения ее к задаче линейного программирования. Совместно с B.J1. Матросовым и С.А. Ждановым [99] исследовалось применение методов коррекции данных в задаче классификации.

Научные изыскания в области коррекции данных систем линейных алгебраических уравнений и несобственных задач линейного программирования велись и зарубежными исследователями. Так, П. Амарало (Р. Amaral) и П. Барахоно (P. Barahona) [127] - [132], независимо от перечисленных выше исследователей, но несколько позже были получены схожие результаты в области коррекции несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования. Отдельные вопросы коррекции несовместных систем линейных неравенств рассматривались А. Дакс (A. Dax) [133]. В работах Дж.Б. Розена (J.B. Rosen) и его научной группы [147] - [151] была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась система линейных алгебраических уравнений, в которой вектор правой части b содержит неточные данные (ошибки измерения), а левая часть системы - матрица А - задана неточно в силу недостаточной априорной информации. Кроме того, матрица А обладает определенной, а именно теплицевой структурой. Результатом работы алгоритма [150] является расширенная матрица коррекции, обладающая такой же структурой, как и исходная матрица.

Дальнейшее развитие такой подход к решению задач структурной матричной коррекции получил в работах бельгийских математиков под руководством профессора С. Ван Хаффела (S. Van Haffel) [140], [142], [143].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций" (DOOR'07) (Владивосток, 2007 г.), Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006, 2007 гг.), Всероссийской научно-практической конференции "Информационные и коммуникационные технологии в образовании" (Борисоглебск, 2006, 2007, 2008, 2009 гг.) и научных семинарах кафедры прикладной математики и информатики физико-математического факультета Борисоглебского государственного педагогического института, кафедры ресурсосберегающих технологий Санкт-Петербургского государственного технологического института (технического университета), кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, отдела интеллектуальных систем Вычислительного центра имени А.А. Дородницына РАН.

Основное содержание диссертации отражено в 10 публикациях [71] -[77], [87] - [89], в том числе в 1 статье [75] в журнале, включенном в перечень ВАК РФ.

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

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

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

- использование минимального по евклидовой норме матричного решения обратной задачи линейного программирования;

- алгоритмический учет неотрицательности части переменных;

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

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

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

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

- векторизацию минимального по евклидовой норме матричного решения обратной задачи линейного программирования;

- алгоритмический учет неотрицательности части переменных;

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

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

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

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

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

Заключение

В работе рассмотрены задачи оптимальной по минимуму евклидовой матричной нормы совместной коррекции данных двойсвенной пары несобственных задач линейного программирования, которые, помимо несобственности, могут обладать дополнительным свойством, а именно, определенной структурой, связанной с природой задач: запретом изменения произвольных строк; запретом изменения произвольных столбцов; запретом изменения произвольных элементов; запретом изменения некоторых блоков. Все классы задач (кроме задач с запретом коррекции произвольных элементов) рассматривались в двух постановках: коррекции подвергается матрица коэффициентов системы ограничений (матрица А), или расширенная матрица ([А 6]) совместно с коэффициентами целевой функцией.

1. Астафьев Н.Н. Некоторые элементарные преобразования двойственных задач линейного программирования. Попарная альтернативность // Современные методы оптимизации и их приложения к моделям энергетики: сб. науч. тр. - Новосибирск: Наука, 2003. - С. 46-55.

2. Астафьев Н.Н. Одновременная регуляризация пары двойственных задач линейного программирования // Алгоритмический анализ неустойчивых задач: Тез. докл. Всероссийской конф. Екатеринбург: Изд-во Урал, ун-та, 2004. - С. 250-251.

3. Астафьев Н.Н. О мере несовместности системы линейных уравнений с требованием неотрицательности // Дискретный анализ и исследование операций: М-лы Российской конф. Новосибирск: Изд-во Ин-та Математики СО РАН, 2004. - С. 120.

4. Ашманов С.А. Линейное программирование. М.: Наука, 1982. 134 с.

5. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. 448 с.

6. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989. 176 с.

7. Барсов А. С. Линейное программирование в технико-экономических задачах. М.: Наука, 1964. 280 с.

8. Башхиян Б.Ц. Гарантированные характеристики точности линейного оценивания, их свойства и применение. Препринт Института космических ииследований № 1332, М: АН СССР, 1987.

9. Березнев В.А. Математические методы планирования производствен-• ной программы предприятий легкой промышленности. М.: Легкая индустрия, 1980. 144 с.

10. Браверман Э.М. Математические модели планирования и управления в экономических системах. М.: Наука, 1976. 368 с.

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

12. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Изд-во "Факториал Пресс", 2003. 352 с.

13. Васильев Ф.П., Иваницкий А.Ю., Морозов В.А. Оценка скорости сходимости метода невязки для задач линейного программирования с приближенными данными // Ж. вычислит, матем. и матем. физики, 1990. Т. 30. № 8. С. 1257-1262.

14. Васильев Ф.П., Иваницкий А.Ю., Морозов В.А. Метод поточечной невязки для решения некоторых задач линейной алгебры и линейного программирования. Сб. работ НИВЦ МГУ "Информатика и вычислительные системы". М.: Изд-во Московск. ун-та, 1993. С. 46-65.

15. Васильев Ф.П. О регуляризации некорректных задач миниминимиза-ции на множествах, заданных приближенно. Ж. вычислит, матем. и матем. физики, 1980. Т. 20. № 1. С. 38-50.

16. Васильев Ф.П. Численные методы решения экстремальных задач: Учеб. пособие для вузов. 2-е. изд., перераб. и доп. М.: Наука Гл. ред. физ.-мат. лит., 1988. - 552 с.

17. Ватолин А.А. Метод апроксимации несобственной задачи выпуклого программирования. В кн.: Несобственные задачи оптимизации. -Свердловск: УНЦ АН СССР, 1982. С. 67-74.

18. Ватолин А.А. Об аппроксимации несобственных задач линейного программирования,- Деп. в ВИНИТИ, № 3501-84 Деп., 1984. 31 с.

19. Ватолин А А. Апроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Ж. вычисл. матем. и матем. физики, 1984. Т. 24. № 12. С. 1907-1908.

20. Ватолин А.А. Методы анализа несобственных задач математического программирования: Дисс. . канд. физ.-мат. наук: 01.01.09.- Свердловск, 1984.

21. Ватолин АА. Множества разрешимости и коррекции седловых функций и систем неравенств. Препринт. Свердловск: ИММ Уро РАН, 1989. -90 с.

22. Ватолин А А. Об одной общей реализации схемы двойственности для несобственной задачи линейного программирования. В кн.: Противоречивые модели оптимизации. Свердловск: УНЦ РАН, 1987. - С. 21-27.

23. Ватолин А А. О коррекции расширенной матрицы несовместной системы линейных неравенств и уравнений // Комбинаторные, алгебраические и вероятностные методы дискретного анализа. Горький, 1989. - С. 40-54.

24. Ватолин АА. Несобственные задачи математического программирования и методы их коррекции: Дисс. . д-ра. физ.-мат. наук: 01.01.09.-Екатеринбург, 1992.

25. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

26. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1988. 552 с.

27. Гейл Д. Теория линейных экономических моделей. М.: Иностр. литер., 1963. 418 с.

28. Голъштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. 384 с.

29. Головкин Б.А. Машинное распознавание и линейное программирование. Под ред. Н. А. Лившица. Серия: Библиотека технической кибернетики. М.: Сов. радио. 1973г. 99 с.

30. Голуб Дою., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. -548 с.

31. Горелик А.Л., Гурееич И.В. Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. М.: Радио и связь, 1985. 162 с.

32. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Ж. вычисл. матем. и матем. физики, 2001. Т.41. №11. С. 1697-1705.

33. Горелик В.А., Ерохин В.И., Печенкин Р.В.Минимаксная матричная коррекция несовместимых систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Изв. РАН ТиСУ, 2006. № 5. С. 52-62.

34. Горелик В.А., Ерохин В.П., Печенкин Р.В. Матричная коррекция несовместных линейных систем с матрицами Тёплица (Ганкеля) // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М: ВЦ РАН, 2003. С. 41-73.

35. Горелик В.А., Ерохин В.И., Печенкин Р.В. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Дискрет, анализ и исслед. операций. Сер. 2. 2005. Т. 12. № 2. С. 3-22.

36. Горелик В.А., Ерохин В.И. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса //

37. Моделирование, оптимизация и декомпозиция сложных динамических процессов. М.: ВЦ РАН, 2001. - С.51-56.

38. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М.: ВЦ РАН, 2004. 193 с.

39. Горелик В.А., Ерохин В.И., Печенкин Р.В. Численные методы коррекции несобственных задач линейного программирования и структурных систем уравнений. М.: ВЦ РАН, 2006. 150 с.

40. Горелик В.А., Золтоева И.А., Печенкин Р.В. Методы коррекции несовместных линейных систем с разреженными матрицами // Дискретный анализ и исследование операций. Июль декабрь 2007. Сер 2. Том 14, № 2. С. 62-75.

41. Горелик В.А., Ибатуллин P.P. Коррекция системы ограничений задачи линейного программирования с минимаксным критерием./ /Моделирование, декомпозиция и оптимизация сложных динамических процессов. М: ВЦ РАН, 2001, С. 89-107.

42. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации. Сб. работ ВЦ РАН "Моделирование, декомпозиция и оптимизация". М.: Изд-во ВЦ РАН, 1999. С. 57-82.

43. Горелик В.А., Муравьева О.В. Задача аппроксимации с коррекцией всех данных. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 21-32.

44. Горелик В.А., Муравьева О.В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями // Декомпозиционные методы в математическом моделировании. Тез. докл. 1-й Московской конференции. М.: ВЦ РАН, 2001. - С.36-37

45. Горелик В.А., Муравьева О.В. Методы коррекции данных в задаче распознавания образов // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. - С.39.

46. Горелик В.А., Муравьева О.В. Устойчивость решения системы линейных неравенств // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. -М.: ВЦ РАН, 2004. С.40.

47. Горелик В.А., Муравьева О.В. Матричная коррекция данных в задачах оптимизации и классификации // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. -С.94-120.

48. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. 600 с.

49. Дмитриев А.Н. Журавлев Ю.И. Кренделев Ф.П. О математических принципах классификации предметов и явлений // Дискретный анализ: Сб. ст. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 7. С. 3-15.

50. Дуда Р., Харт П. Распознавание образов и анализ сцен. Издательство "Мир", Москва, 1976, 511 с.

51. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.

52. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: Изд-во УрО РАН, 2001. 179 с.

53. Еремин И. И. Двойственность для несобственной задачи линейного программирования и методы их коррекции. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982. - С. 3-10.

54. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования и методы их коррекции // Изв. АН СССР. Сер. Техн. киберн. 1983, №1. - С. 20-32.

55. Еремин И.И. Двойственность и апроксимация для несобственных задач математического программирования //для несобственных задач линейного и выпуклого программирования и методы их коррекции // Изв. АН СССР. Сер. Техн. киберн. 1987, №1. - С. 70-81.

56. Еремин И. И. Вопросы двойственности для несобственной задачи многокритериальной линейной оптимизации. В кн.: Исследования по несобственным задачам оптимизации. Свердловск; УНЦ АН СССР, 1988. С. 27-33.

57. Еремин И. И. О системах неравенств с выпуклыми функциями в левых частях. Известия АН СССР, серия математическая, 30 (1966), стр. 265278.

58. Еремин И.И. Противоречивые модели оптимального планирования. -М.: Наука, 1988. 160 с.

59. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. - 336 с.

60. Еремин И.И. Противоречивые модели планирования и управления. В кн.: Противоречивые модели оптимизации. Свердловск: УНЦ АН СССР, 1987. - С. 28-37.

61. Еремин И.И., Соколинская И.М. Фейеровские итерационные процессы для несобственных задач линейного программирования // Математические структуры и моделирование: Сб. научн. тр. Омск: Омск. гос. ун-т. - 2002. - Вып. 9. - С. 10-26.

62. Ерохин В.И. Матричная коррекция двойственной пары несобственных задач линейного программирования // Ж. вычисл. матем. и матем. физики, 2007. Т.47. № 4. С. 587-601.

63. Ерохин В.И., Красников А.С. Матричная коррекция двойственной пары несобственных задач линейного программирования с блочной структурой // Ж. вычисл. матем. и матем. физики, 2008. Т. 48. № 1. С. 80-89.

64. Журавлев Ю.И., Гуревич И. Б. Распознавание образов и распознавание изображений // Распознавание. Классификация. Прогноз. Математические методы и их применения. Вып. 2. М.: Наука, 1989. 72 с.

65. Журавлев Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. -М.: Фазис, 2006. 176 с.

66. Журавлев Ю.И. Экстремальные задачи, возникающие при обоснова-• нии эвристических процедур // Проблемы прикладной математики имеханики. М,: Наука, 1971. С. 67-75.

67. Золтоева И.А. Методы коррекции данных для формализации и решения задач многокритериальной оптимизации: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2006.

68. Зуховицкий С.И., Радчик ИА. Сатематические методы сетевого планирования. М.: Наука, 1965. 296 с.

69. Ибатуллин P.P. Методы коррекции и аппроксимации несобственных задач оптимизации и управления с минимаксным критерием: Дисс. .канд. физ.-мат. наук: 05.13.17. М., 2002.

70. Канторович JI.B. Математические методы в организации и планировании производства. JL: Изд-во Ленинградск. ун-та, 1939. 68 с.

71. Канторович JI.B. Экономический расчет наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960. 347 с.

72. Красников А.С. Необходимое условие разрешимости проблемы оптимальной матричной коррекции двойственной пары несобственных задач линейного программирования // Научное обозрение, 2009, № 4. -С. 39-42.

73. Красников А. С. О матричном решении обратной задачи линейного программирования с минимальной евклидовой нормой // Научное обозрение, 2009, № 4. С. 37-39.

74. JIudoe M.JI. К оприорным оценкам точности определения параметров по методу наименьших квадратов // Космические исследования, 1964. Т.2. № 5. С. 713-718.

75. Лидов М.Л., Бахшиян Б.Ц., Матасов А.И. Об одном направлении в проблеме гарантирующего оценивания (обзор). // Космич. исслед. 1991. Т. 29. № 5. С. 659-684.

76. Лидов М.Л., Матасов А.И. Об одном обобщении задачи о "наихудшей корреляции" // Космические исследования, 1989. Т.27. № 3. С. 454-456.

77. Лотов А.В. Введение в экономико-математическое моделирование. М.: Наука. 1984. 392 с.

78. Мазуров Вл.Д. Метод допустимых коррекций. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982. - С. 11-22.

79. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 246 с.

80. Матасов А.И. Введение в теорию гарантирующего оценивания. Учебное пособие Москва: МАИ, 1999.- 80 с.

81. Матросов В.Л., Горелик В.А., Жданов С.А., Муравьева О.В. Коррекция данных в задаче классификации // Математические методы распознавания образов: Доклады XI Всероссийской конф. (ММРО-11). -М.: ВЦ РАН, 2003. С. 136-137.

82. Муравьева О.В. Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2002.

83. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. 2-е изд., исп. и доп. - М.: ФИЗМАТЛИТ, 2004. -176 с.

84. Печенкин Р.В. Методы коррекции несовместных систем со структурными ограничениями: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2006.

85. Попов Л.Д. Об одном методе декомпозиции в несобственном линейном программировании. В кн.: Нерегулярная двойственность в математическом программировании. Свердловск: УрО РАН, 1990. - С. 42-45.

86. Попов JI.Д. Несобственные задачи оптимизации, методы их оптимальной коррекции и приложения. Дисс. . докт. физ.-мат. наук: 01.01.09. -Новосибирск, 1997.

87. Рейклетис ГРейвипдран А., Рэгсдел К. Оптимизация в технике: В 2-ч кн. Кн. 1. Пер. с англ. М.: Мир, 1986. - 349 е., ил.

88. Рудаков К.В. О некоторых классах алгоритмов распознавания (общие результаты) . М. : ВЦ АН СССР, 1980. 66 с.

89. Скарин В.Д. О применеии метода регуляризации для коррекции несобственной задачи линейного программирования первого рода. В кн.: Методы аппроксимации несобственной задачи линейного пргграм-мирования. Свердловск: УНЦ АН СССР, 1984. - С. 39-54.

90. Скарин В.Д. Об одном регуляризующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. В кн.: Исследования по несобственным задачам оптимизации. Свердловск: УНЦ АН СССР, 1988. - С. 48-56.

91. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации: Учеб. пособие. 2-е изд. - М.: ФИЗМАТЛИТ, 2005. - 368 с.

92. Тихонов А.Н. О нормальных решениях приближенных систем линейных алгебраических уравнений // Докл. АН СССР, 1980, т. 254, 3, С. 549-554.

93. Тихонов А.Н. О приближенных системах линейных алгебраических уравнений // Ж. вычисл. матем. и матем. физики, 1980. т. 20. № 6. С.1373-1383.

94. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. -М.: Наука, 1970. 288 с.

95. Тихонов А.Н., Рютпин А.А., Агаян Г.М. Об устойчивом методе решения задачи линейного программирования с приближенными данными // Докл. АН СССР, 1983, т. 272, 5, С. 1058-1063.

96. Тихонов А.Н., Морозов В.А., Карамзин В.Н. О задаче коррекции линейных неравенств. Сб. работ НИВЦ МГУ "Численный анализ: методы, алгоритмы, приложения". М.: Изд-во Моск. ун-та, 1985. С.3-13.

97. Трофимов С.П. Анализ соотношений двойственности для задач по-лубесконечпого и бесконечного линейного программирования. Дисс. . канд. физ.-мат. наук: 01.01.09. Свердловск, 1988.

98. Фролов В.Н. Оптимизация плановых программ при слабо согласован-• ных ограничениях. М.: Наука, 1986. - 166 с.

99. Фролов В.Н., Вашолин А.А. Анализ противоречивых ситуаций в задачах текущего планирования производства. В кн.: Противоречивые модели оптимизации. Свердловск: УНЦ РАН, 1987. - С. 79-92.

100. Фролов В.Н. Оптимизация плановых программ при слабо согласованных ограничениях. Дисс. . докт. эконом, наук. М., 1987.

101. Фролов В.Н., Чернавин П.Ф. Построение непротиворечивых программ развития производственно-экономических объектов // Экономика и матем. методы. 1987. - Т. 23, № 6. - С. 1069-1076.

102. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 655 с.

103. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981. 352 с.

104. Amaral P. Contribui3xes para о estudo de sistemas lineares inconsistentes. PhD dissertation, Faculty of Science and Technology, UNL, Lisbon, Portugal, 2001 (in Portuguese).

105. Amaral P., Barahona P. About infeasibility in the constraints of a linear model. Ricerca Operativa, 1999. № 92. P. 49-67.

106. Amaral P., Barahona P. A framework for optimal correction of inconsistent linear constraints. Constraints, 2005. № 10 P. 67-86.

107. Amaral P., Barahona P. Connections between the total least squares and the correction of an infeasible system of linear inequalities. Linear Algebra and its Applications, 2005. № 395. P. 191-210.

108. Amaral P., Barahona P. On optimal correction of inconsistent linear constraints. In: Hentenryck PV, editor. Principles and practice of constraint programming, CP'2002 (Proceedings), Lecture notes in computer science, vol. 2470; 2002. P. 33-46.

109. Amaral P., Trosset M. W., Barahona P. Correcting an Inconsistent System of Linear Inequalities by Nonlinear Programming, Technical Report 00Y 27, Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005.

110. Dax A. The Smallest Correction of an Inconsistent System of Linear Inequalities // Optimization and Engineering, 2001'. №2. P. 349-359.

111. Fung G.M., Mangasarian O.L. Multicategory Proximal Support Vector Machine Classifiers // Machine Learning, 2005, № 59, P. 77-97.

112. Gorelik V.A., Ibatullin R.R. Correcting the system of constraints of a linear program with the aid of minimax criterion // Тезисы докладов 3-й международной конференции по исследованию операций. М.: ВЦ РАН, 2001. - С. 42.

113. Gorelik V.A., Muravyova О. V. Problem of approximating with variation of all data. // Тезисы докладов 3-й международной конференции по исследованию операций. М.: ВЦ РАН, 2001. - С. 43.

114. Gorelik V.A., Pechenkin R. V. Decomposition approach for solving signal identification problem // Декомпозиционные методы в математическом• моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. - С. 41-42.

115. Greenberg HJ. Murphy FH. Approaches to diagnosing infeasible linear programs. ORSA Journal on Computing, 1991 № 31. P. 79-97.

116. Khachay M. Yu. On Approximate Algorithm of a Minimal Committee of a Linear Inequalities System // Pattern Recognition and Zimage Analysis. 2003. - Vol. 13, № 3. - P. 459-464.

117. Lemmerling P. Structured total least squares: analysis, algorithmus and applications. PhD dissertation. Kattholieke Universiteit Leuven, Aren-bergkasteel, Belgium, 1999. 189 p.

118. Mangasarian O.L. Support Vector Machine Classification via Parameter-less Robust Linear Programming // Optimization Methods and Software 2005, № 20, P. 115-125.

119. Markovsky I. Exact and approximate modeling in the behavioral setting // PhD dissertation. Kattholieke Universiteit Leuven, Arenbergkasteel, Belgium, 2005. 200 p.

120. Markovsky I. and Willems J. C. and De Moor B. and Van Huffel S. Exact and Approximate Modeling of Linear Systems: A Behavioral Approach. SIAM. 2006. March. Monographs on Mathematical Modeling and Computation.

121. Marquardt D. W. An algorithm for least-squares estimation of nonlinear parameters. J. Soc. Indust. Appl. Math., 1963. V. 11. № 2. - P. 431-441.

122. Mazurov Vl.D., Khachay M. Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceeding of the Steklov Institute of mathematics/ 2002/ - Suppl/ 1/ - 3. - P. 67-101.

123. Murty K.G. Linear Programming. J. Wiley & Sons.Inc. New York, 1983. P.254.

124. Park H., Zhang L., Rosen J.B. Exponential modeling with unknown model order using structured nonlinear total least norm, Advances in Computational Mathematics, 2003. № 19: P. 307-322.

125. Pruessner A., O'Leary D.P. Blind Deconvolution Using A Regularized Structured Total Least Norm Algorithm // SI AM J. on Matrix Analysis and Applications, 2003. Vol. 24. № 4. P. 1018-1037.

126. Park H., Zhang L., Rosen J.B. Exponential modeling with unknown model order using structured nonlinear total least norm, Advances in Computational Mathematics , 2003. No 19: P. 307-322.

127. Rosen J.B., Park H. Glick J. Total least norm problems: formulation and solution // illUMSI research report. Minniapolis(Mn) Univ. of Minnesota. Supercomput. inst., 1993, 93/223. 18 p.

128. Rosen J.B., Park H.} Glick J. Total least norm formulation and solution for strucured problems. SIAM Journal on Matrix Anal. Appl. 1996. Vol. 17. m. P. 110-128.

129. Rosen J.B., Park E., Glick J. Structured nonlinear total least norm problems// UMSI reserch report. Minniapolis (Mn): Univ. of Minnesota. Supercomput. inst., 1995. 11 p.

130. Rosen J.B., Park H., Glick J. Total least norm for linear and nonlinear structured problems, Recent advances in total least squares techniques and errors-in-variables modellign. Ed. S. Van Huffel, SIAM, 1997. P. 203-214,

131. Vatolin A.A. Parametric approximation of inconsistent systems of linear equations and inequalities. Seminarber., Humboldt-Univ. Berlin, Sekt. Math., 1986. P. 145-154.

132. Vatolin A.A. An LP-based algorithm for the correction of inconsistent linear equation and inequality systems // Optimization: A Journal of Mathematical Programming and Operations Resear ch, 1029-4945, Volume 24, Issue 1, 1992, P. 157 - 164.

133. Watanabe S. Pattern recognition: Human and mechanical. N.Y.: Wiley, 1985. 592 p.

134. Wisenhausen H.S. Sets of Possible States of Linear Sisrems Given Per-turber Observatons // IEEE Transactions Automatic Controls, 1968. vol. AC-13. P. 556-558.

135. Алгоритм решения задач Dh и -£>#/,.

136. Для решения задачи (1-23), к которой, согласно теореме 1.4.1, сводятся задачи Dh и Dhijj можно использовать следующий алгоритм.

137. Шаг 1. Задать й^ начальные приближения к х* и й* сответственно; М - максимальное (допустимое) количество итераций; е - параметр сходимости; t - параметр, определяющий тип задачи0, для задачи!)#,t =1, для задачи£>НЛ.

138. Шаг 2. Положить к = О, = 104.

139. Шаг 3. Вычислить компоненты

140. Шаг 4. Если выполняется неравенство < е, то перейти к шагу 11, иначеперейти к следующему шагу.

141. Шаг 5. Если выполняется неравенство к ^ М, то перейти к шагу 11, иначе перейти к следующему шагу.1. Шаг 6. Вычислить1. АхМ Д«(*>va®(®Wfi№) + А<*> • 1п+т. 1 •где 1п+т единичная матрица порядка п +т. Шаг 7. Положить1. = г(*) + Д5(*)?й{к+1) =й(к) + Айк)ш

142. Шаг 8. Если выполняется неравенство < то перейти кшагу 9, иначе перейти к шагу 10.1

143. Шаг 9. Положить A(fc+1) = -А^, к = к -Ь 1 и перейти к шагу 3. Шаг 10. Положить А(*+1> = 2АМи перейти к шагу 6. Шаг 11. Вычислить Н*, h*, х*, и* в соответствии с (1.25) (1.26). Шаг 12. Вывести результаты и остановиться.

144. Дифференцирование целевой функции Ф(ж, й)

145. Для дифференцирования целевой функции Ф(х, й) задачи (1.23) удобнее будет переписать ее в виде

146. Ф{х,й) = В ■ X + D ■ U + t ■ С ■ U G • U ■ X,где

147. Матрица Гессе целевой функции Ф(ж, и) вычисляется следующим образом1. У2Ф(ж,й) =