Смешанные системы неравенств в обучаемых методах оптимизации

Настоящая диссертационная работа посвящена вопросам использования методов распознавания образов для моделирования плохо определенных элементов оптимизационных задач.

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

В нашей стране развитие теории распознавания образов связано с именами Э. М. Бравермана, В. Н. Вапника, Ю. И .Журавлева, Н.Г.За-горуйко, М. М. Камилова, Вл.Д.Мазурова, Л. А. Расстригина, В. Н. Фомина, Я. З. Цыпкина и др. Из зарубежных ученых, работающих в этой области, следует отметить Р. Гонсалеса, У. Гренандера, Д. Кэйлора, М. Минского, Н. Нильсона, М. Осборна, Ф. Розенблатта, Р. Такияму, Дж. Ту, С. Эй, блоу.

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

На существование плохо формализуемых факторов и важность их учета в моделях прирожных, технологических, экономических и других процессов, указывается в работах Ю. И. Журавлева [l7j, Вл.Д. Мазурова [I, 32, 33], Н. Н. Моисеева [28, 39], Ю. М. Свирежева [23J и других авторов. В работах Ю. И. Журавлева [ 12, I7J с точки зрения плохой формализуемости рассматриваются задачи распознавания образов и изучается вопрос построения корректных алгоритмов для таких задач.

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

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

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

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

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

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

Таким образом, в связи с построением обучаемых методов оптимизации оказывается необходимым построение процедур дискриминант-ного анализа. В данной работе рассматривается постановка задачи дискриминантного анализа с использованием аппарата линейных неравенств. Систематическое и глубокое изложение теории линейных неравенств приведено в монографии С. НЛерникова [54]. В используемой постановке [3l] задача дискриминантного анализа есть по сути дела задача решения системы линейных неравенств, которая однозначно определяется разделяемыми множествами. Эта система может быть конечной или бесконечной в зависимости от того, конечны или бесконечны разделяемые множества. Совместность этой системы эквивалентна линейной разделимости множеств. В случае линейной не разделимости понятие комитета система неравенств позволяет говорить о комитетном разделении [28].

Понятие комитета системы неравенств было введено в [56, 57] Эйблоу и Кэйлором. Дальнейшее развитие комитетных методов в распознавании образов связано s нашей стране с работами Вл.Д.Мазурова [27] и В. Н. Фомина [53], за рубежом — с исследованиями Н. Ниль-сона (4lJ, М. Осборна [59], Р. Такиямы [60, 6lj. Вл.Д.Мазуровым были, в частности, получены условия существования комитета конечной системы линейных неравенств и сформулированы условия коми-тетной разделимости конечных множеств. Оказывается, всякие два непересекающиеся конечные множества векторов пространства R разделимы комитетом аффинных функций. Вопросы корректности комитетных алгоритмов подробно изучены в работах Ю. И. Журавлева [13-I6J.

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

Во-вторых, обычно в задачах дискриминантного анализа конечные разделяемые множества суть некоторые подмножества множества всех возможных ситуаций. Так, например, если вектор. X&R отражает состояние некоторой системы, X — R — множество всех возможных состояний, то X, как правило, бесконечно. Если все возможные состояния системы делятся на 2 типа, то есть Y-fl^B то множества Й и В обычно тоже бесконечны. Чаще всего эти множества неизвестны, известны лишь конечные их подмножества и комитетная конструкция, разделяющая hi и В1 выбирается в качестве некоторого приближения комитетной конструкции, разделяющей множества й и 6. В связи с этим встает вопрос о существовании разделяющей комитетной конструкции для двух произвольных бесконечных множеств, то есть вопрос оценки широты класса комитетно разделимых бесконечных множеств.

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

Комитетная дискриминация бесконечных множеств рассматривалась А. И. Кривоноговым в [25]. Некоторым новым результатам в этой области посвящена глава I настоящей работы.

Дадим теперь краткий обзор результатов работы по главам.

ЗАКЛЮЧЕНИЕ

.

Отметим следующие основные результаты данной работы.

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

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

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

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

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