Отделимость выпуклых множеств ступенчато-аффинными функциями и ее приложения в теории оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

гГЙ од

УДК 517.982.252+519.853 ' г ,„л„ п

Шннкевкч Елена Алексеевна

ОТДЕЛИМОСТЬ ВЫПУКЛЫХ МНОЖЕСТВ СТУПЕНЧАТО-АФФИННЫМИ ФУНКЦИЯМИ И ЕЕ ПРИЛОЖЕНИЯ В ТЕОРИИ ОПТ ИМИЗАЦИИ

01.01.09 - математическая кибернетика

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

Минск, 2000

Работа выполнена ь Институте математики Национальной Академии ;<аук Беларуси

Научный руководитель - член-корреспондент НАМ Беларуси, доктор

физико-математических наук, профессор Гороховик Валентин Викснтьевич

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

Борухов Валентин Терентьевич

кандидат физико-математических наук, доцент Альсевич Виталий Викентьевич

Оппонирующая организация Санкт-Петербургский государственный

университет

Защита состоится «иссиЯ____2000 г. в /В" на заседании

совета но защите диссертаций ДО 1.02.02 в Институте матсмашки Национальной Академии наук Беларуси по адресу:

220072, г. Минск, ул. Сурганова, 11, Институт математики Национальной Академии наук Беларуси, конференц-зал. Телефон ученого секретаря - 284-19-63.

С диссертацией можно ознакомиться в библиотеке Института математики Национальной Академии наук Беларуси.

г

Автореферат разослан 2000 г.

Ученый секретарь

совета по защите диссертаций

доктор физ.-мат. наук, /

профессор Матус П.П.

А473. /

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

Актуальность темы диссертации. Настоящая диссертационная работа посвящена методам исследования нерегулярных выпуклых задач оптимизации. Как известно, критерий оптимальности решений задачи выпуклого программирования, доказанный еще в 50-ые годы Х.В. Куном и A.B. Таккером, справедлив лишь для задач, удовлетворяющих условию регулярности Слейтера. Вопрос о критерии оптимальности решений в нерегулярных задачах выпуклого программирования остается актуальным и в настоящее время, о чем свидетельствуют, например, работы А. Бен-Тала, А. Бен-Израэля, С. Злобека, A.M. Рубинова, Б.М. Гловера, В. Джеякумара, посвященные некоторым классам нерегулярных задач выпуклого программирования. Аналогичная ситуация характерна и для большинства других выпуклых задач оптимизации. Анализ методов вывода условий оптимальности для решений выпуклых задач оптимизации показывает, что источником возникновения условий регулярности в задачах этого класса являются классические теоремы об отделимости выпуклых множеств гиперплоскостью, лежащие в основе этих методов. Поэтому одна из основных задач данной работы состоит в том, чтобы найти такие обобщения классических теорем об отделимости выпуклых множеств, которые были бы свободны от ограничивающих их применение предположений и, вследствие этого, не приводили бы к условиям регулярности. Вторым требованием к обобщенным теоремам об отделимости является их аналитическая форма, что позволило бы в приложениях к задачам оптимизации получить аналитически выраженные двойственные критерии оптимальности. Решение этой задачи актуально не только с точки зрения теории нерегулярных выпуклых задач оптимизации, но и для развития выпуклого анализа, а также функционального анализа в целом.

Связь работы с крупными научными программами, темами. Исследования проводились в рамках следующих научных тем: "Геометрические методы исследования в теории операторов и соответствий" (договор № Ф94-190 с Белорусским республиканским

фондом фундаментальных исследований); "Методы теории упорядоченных пространств и их приложения в нелинейном анализе" (договор № Ф96-140 с Белорусским республиканским фондом фундаментальных исследований ).

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

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

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

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

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

Научная новизна и значимость полученных результатов.

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

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

и рангам.

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

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

Результаты диссертации могут также найти применение в научных коллективах Белорусского, Гродненского, Московского и Санкт-Петербургского государственных университетов, а также Математического института им. В.А. Стеклова и Института математики и механики Уральского отделения РАН, ведущих исследования в области математической теории оптимизации, линейного и выпуклого анализа, а также функционального анализа в целом и их приложениях.

Основные положения диссертации, выносимые на защиту. На защиту выносятся следующие основные положения диссертации:

- определения и свойства ступенчато-линейных и ступенчато-

аффинных функций — новых классов вегцественнозначных функций, определенных на вещественном векторном пространстве;

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

- геометрические и порядковые признаки полупространств (выпуклых подмножеств вещественного векторного пространства, дополнения которых также выпуклы);

- классификация бесконечномерных полупространств по типам и рангам;

- двойственность класса ступенчато-линейных функций и совокупности конических полупространств, а также двойственность класса ступенчато-аффинных функций и совокупности всех полупространств;

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

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

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

Апробация результатов диссертации. Результаты диссертации докладывались и обсуждались на ряде научных конференций и семинаров, в том числе на: 5-ой Межгосударственной научной конференции "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (Минск, 1996 г.); 7-ой Белорусской математической конференции (Минск, 1996 г.); 20-м Международном симпозиуме студентов и молодых исследователей (Польша, Зелена Гура, 1998г.); Международной конференции "Динамические системы: устойчивость, управление, оптимизация" (Минск, 1998г.); Германско-польской конференции по оптимизации (Польша, г. Жаган, 1999г.).

Опубликованность результатов. Основные результаты диссертации опубликованы в 12 работах (3 работы без соавторов), из которых 6 статей в научных журналах, 1 препринт Института ма-

тематики HAH Беларуси и 5 публикаций в тезисах докладов конференций. Общее количество страниц опубликованных материалов — 87.

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

Объем диссертации — 106 страниц. Список использованных источников содержит 84 наименования на 7 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

Пусть X — вещественное векторное пространство, и пусть V — совокупность всех векторных подпространств из X, упорядоченная отношением включения. Подсемейство £ С V называется цепью, если для любых L, L' € £ выполняется либо L С Lлибо L' С L. Цепь £ С V, содержащая в себе объединения и пересечения любого своего подсемейства, называется полной.

Пирамидой векторных подпространств над X назовем любую полную цепь £ из V такую, что U{.L|Ze£} = X, ПРИ этом векторное подпространство Е0 := р|{£ | L G £} будем называть вершиной пирамиды £.

Каждому L 6 £, L у- Е0, поставим в соответствие содержащееся в нем векторное подпространство L := U{L' 6 £ | L' С L, L' ф L}. Истинными ступенями пирамиды £ будем называть непустые подмножества вида L\L, где ¿е£\{£0}- Вершину Е0 также будем

рассматривать как одну из ступеней пирамиды £ и называть ее вершинной ступенью.

Семейство ¿7с, состоящее из всех (вершинной и истинных) ступеней пирамиды £, является разбиением векторного пространства X.

Каждой ступени 5 6 51 ф Е0, сопоставим векторное подпространство Ь$ € С такое, что 5 = Ь5\Ь5. Для вершинной ступени Б — Е0 положим = Е0. Соответствие 5 —► Ь$ инъективно отображает совокупность всех ступеней 2С в пирамиду С и индуцирует на Не отношение совершенного порядка определяемое для любых 51,52 € £с условием: 5*1 52 <=Ф- С

Рангом нетривиальной (£ ф {X}) пирамиды векторных подпространств £ назовем порядковый тип р{£) множества её истинных ступеней Ее \ совершенно упорядоченного отношением <£ . Ранг тривиальной пирамиды С — {X} будем считать равным нулю.

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

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

Пирамида векторных подпространств £ над X с вершиной Е0 назовается максимальной, если как цепь она максимальна среди всех пирамид векторных подпространств над X с той же вершиной Е0.

Пусть Ь(Х) — векторное пространство вещественнозначных линейных функций, определенных на X.

Семейство Т из Ь{Х) назовем кортежем линейных функций на X, если на Т определено отношение совершенного порядка Ч такое, что для любого подсемейство Тх := {/ € Т | I (х) ф 0}

либо пусто, либо имеет наименьший (в смысле Ч ) элемент 1Х.

Кортеж линейных функций Т из Ь(Х) назовем несократимым,

если для любого I € Т существует х £ X такой, что ф 0 и / = /«.

Одноэлементный кортеж Т — образованный нулевой линейной функцией I (х) = О, х £ X, назовем тривиальным.

Любой несократимый кортеж нетривиален. Нетрудно видеть также, что любой нетривиальный кортеж Т содержит в себе несократимый кортеж Т~ {7 6 Т | За: £ X такой, что Тх ф 0 и / = 1Х}, который будем называть несократимой частью кортежа Т.

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

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

В разделе 1.4 дается определение ступенчато-линейной функции.

Вещественнозначную функцию с : X —► К будем называть ступенчато-линейной, если над X существует максимальная пирамида векторных подпространств £ такал, что

(БЛ!) с(х) = 0 х € Е0 (В0 — вершина пирамиды £ );

(Б1Ь2) для каждого Ь € £, Ь ф Е0, функция

, , ч [ 0, если х 6 2, х ¡¿(х) := < ?

[ с (г), если х£Ь\Ь,

является линейной на векторном пространстве Ь .

Нулевая функция (с(г) = 0,г£1) также считается ступенчато-линейной, при этом ей соответствует тривиальная пирамида С = {X}.

Ранг ступенчато-линейной функции с : X —► К определяется

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

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

Теорем а 1.7. Ненулевая вещественнозначная функция с : X —► К ступенчато-линейна тогда и только тогда, когда существует (вообще говоря, не единственный) несократимый кортеж линейных функций Т на X такой, что

. ._ / 0, если Тг - 0,

С[Х> ■"{ 1х(х), если Тх ф 0,

при этом ранг с : X —> К является обратным рангу кортежа Т'.

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

В разделе 1.5 по схеме, аналогичной предыдущим разделам, вводится более широкий класс ступенчато-аффинных функций, при этом в работе реализуется лишь дуальный подход к определению ступенчато-аффинных функций, основанный на понятии кортежа аффинных функций. Ступенчато-аффинная функция является ступенчато-линейной в том и только том случае, когда она однородна. Показывается, что каждой ступенчато-аффинной функции однозначно соответствует некоторая ступенчато-линейная функция. Выделяются регулярные ступенчато-аффинные функции. Те же ступенчато-аффинные функции, которые не являются регулярными, называются сингулярными. Доказывается (предложение 1.6), что регулярные ступенчато-аффинные функции и только они представимы в виде композиции ступенчато-линейной функции и параллельного переноса. Связь между сингулярными ступенчато-аффинными функциями и соответствующими им ступенчато-линейными функциями является более сложной и раскрывается в предложениях 1.6 и 1.7. Доказывается ряд свойств ступенчато-аффинных функций (предложение 1.5 и следствие 1.4), важных с точки зрения последующего примене-

ния функций этого класса в диссертации.

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

Теорема 1.14. Бинарное отношение определенное на векторном пространстве X, является полным коническим отношением предпорядка тогда и только тогда, когда существует ступенчато-линейная функция с : X —► К такая, что х у с( ::-у)< 0-

Ранг полного конического отношения предпорядка ;<, определенного на векторном пространстве X, определяется равным рангу соответствующей ему ступенчато-линейной функции с : X К.

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

Результаты, представленные в первой главе, опубликованы в следующих работах [1, 3, 5, 8, 12].

Основным объектом исследования главы 2 являются полупространства — выпуклые подмножест/!а вещественного векторного пространства, дополнения которых также выпуклы. Определение и наиболее распространенные примеры полупространств приводятся в разделе 2.1. Там же обсуждаются предшествующие диссертации исследования полупространств, осуществленные другими авторами. В частности, приводятся результаты Х.-Э. Мартинец — Легаза и И. Зингера, посвященные классификации полупространств в конечномерных векторных пространствах. Основана их классификация на аналитическом представлении конечномерных полупространств, которое задается при помощи линейных операторов и отношений лексикографического порядка. В главе 2 данная классификация распространяется на бесконечномерные полупространства. Развиваемый в диссертации подход является новым и основан на геометрических и порядковых признаках полупространств, а не на их аналитическом представлении.

Геометрические признаки (как конических, так и произвольных)

полупространств устанавливаются в разделе 2.2. В частности, там покалывается (теорема 2.2), что подмножество С вещественного векторного пространства X является полупространством в X тогда и только тогда, когда его рецессивный конус О+С := {Н £ X | х + ак € С для всех х € С и а > 0} является коническим полупространством в X. Другой важный геометрический признак полупространств доказывается в теореме 2.5: подмножество С С X является полупространством в X в том и только том случае, когда для любой прямой I из X пересечение /ПС является полупространством в I.

В разделе 2.3 осуществляется классификация полупространств произвольного (конечномерного или бесконечномерного) векторного пространства по рангам и типам.

Ранг полупространства С определяется равным рангу полного конического отношения предпорядка <с-, определяемого тождеством: у -<с % х — у € 0+С.

Определение типа полупространства основывается на следующем порядковом признаке полупространств.

Теорема 2.8. Подмножество С вещественного векторного пространства X является полупространством в X, тогда и только тогда, когда пара (Х\С, С) является сечением пространства X по некоторому полному коническому отношению предпорядка определенному па X, при этом •< С ^с •

Сечением пространства X, порожденным полупространством С, ниже называется сечение (X \ С,С), рассматриваемое по полному коническому отношению предпорядка ■

Известно, что в любом упорядоченном множестве возможны только четыре типа сечений: скачок, два дедекиндовых (нижнее и верхнее) и щель. В теореме 2.9 устанавливаются следующие свойства сечений векторного пространства X, порожденных полупространствами: а) в любом вещественном векторном пространстве X среди сечений, порожденных всевозможными его полупространствами нет скачков; б) в каждом вещественном векторном пространстве существуют как нижние, так и верхние дедекиндовы сечения, поро-

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

Тип полупространства С отождествляется в диссертации с типом порождаемого им сечения (X \ С, С) пространства X .

В соответствии с этим полупространство С С X называется

- заостренным дедекиндовым, если сечение (Х\С,С) является верхним дедекиндовым;

- незаостренным дедекиндовым, если (Х\С,С) является нижним дедекиндовым сечением;

- недсдскиндовым или полупространством-щелью, если сечение (X \ С, С) есть щель.

Таким образом, в соответствии с осуществленной в диссертации классификацией все полупространства делятся по типам на три непересекающихся класса: класс заостренных дедекиндовых полупространств, класс незаостренных дедекиндовых полупространств и класс недедекиндовых полупространств. В конечномерных векторных пространствах класс недедекиндовых полупространств пуст (следствие 2.2) и данная в диссертации классификация полупространств (как по рангам, так и по типам) совпадает с классификацией Х.-Э. Мартинец-Легаза и И. Зингера (замечание 2.2).

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

Теорема 2.14 (2.16). Собственное подмножество С вещественного векторного пространства X является заостренным (незаостренным) дедекиндовым полупространством ранга р тогда и только тогда, когда существует ступенчато-линейная функ-

ция с : X —> К того же ранга р и тонка а £ А" такие, что

С = {х £ X I с(х - а) > 0} (С = {х £ X I с(х - а) > 0}).

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

Следствие 2.3. Собственное подмножество С вещественного векторного пространства X является коническим полупространством в X тогда и только тогда, когда существует ступенчато-линейная функция с : X —* К. такая, что либо

С = {х е X | с(®) >0}, Х\С = {х € X | с (а:) < 0},

либо

С = {хех\ с(х) >0}, Х\С = {х 6 X I с(х) < 0}.

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

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

Теорема 2.25. Собственное подмножество С С X является недедекиндовым полупространством ранга р тогда и только тогда, когда существует сингулярная ступенчато-аффинная функция и : X —у К ранга р такая, что

С = {х 6 X | и(х) >0}, X \ С = {х £ X \ и{х) < 0}.

Теорема 2.25 вместе с теоремами 2.14 и 2.16 устанавливает, фактически, двойственность совокупности всевозможных полупространств классу ступенчато-аффинных функций, в силу которой де-декиндовым полупространствам соответствуют регулярные ступенчато-аффинные функции, а недедекиндовым — сингулярные ступенчато-аффинные функции.

Результаты второй главы опубликованы в работах [3, 5, 6, 7, 9].

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

Теорема 3.3 (об отделимости выпуклых конусов ступенчато-линейными функциями). Пусть Кг и К2 — выпуклые конусы в векторном пространстве X, причем конус К\ асимметричен. Тогда следующие утверждения эквивалентны:

а) Кх П К3 = 0;

б) в X существует заостренное (О £ С) коническое полупространство С такое, что К\ П С — 0, С С;

в) существует ступенчато-линейная функция с : X Ш такая, что

с(х) > 0 для всех х € Кь с(х) < 0 для всех х £ К2.

Т е о р ем а 3.4 (об отделимости выпуклых множеств ступенчато-аффинными функциями). Для того чтобы выпуклые подмножества А и В вещественного векторного пространства X не пересекались необходимо и достаточно, чтобы существовала ступенчато-аффинная функция и: X -*Ш такая, что либо

и (х) > 0 для всех х е А, и (у) < 0 для всех у £ В,

либо

и(х) > 0 для всех х £ А, и (у) < 0 для всех у £ В.

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

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

Пусть заданы некоторое множество ф и отношение предпорядка < , определенное на <3 . Точка называется < -минимальной в (¡) (минимальной в <5 относительно < ), если в <5 не существует точки 2 £ <5 такой, что х -< х°. Здесь х -< х° означает, что х < х° ,

Под задачей оптимизации (СЦ,^) понимается задача нахождения подмножества ^-минимальных точек множества <5. Задача оптимизации (<3,;<) называется задачей векторной оптимизации, если множество <5 — подмножество некоторого векторного пространства X, а отношение предпорядка < определено на всем X и является коническим. Говорят, что задача векторной оптимизации (С^,-^) является выпуклой, если выпукло множество <3 {х е X | Зу 6 Я : у ■< х}.

Однородная функция ¡р : X —> К называется сильно ложительной, если 1) (х) > 0 для всех х £ X таких, что 0 -< 2) у? (г) = 0 для всех х 6 X таких, что г ~ О ( 0).

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

Теорем а 3.6. Для того чтобы х° было ^ -минимальным решением выпуклой задачи векторной оптимизации (С^,^), необходимо и достаточно, чтобы существовала сильно -положительная ступенчато-линейная функция с : X Ж такая, что

с(х — хс) > 0 для всех х & С}.

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

Пусть X — вещественное векторное пространство, /; : X —> R, i — 0,1,..., т., — выпуклые функции, Q — выпуклое множество из X.

Задача выпуклого программирования состоит в минимизации функции /а : X —> R на множестве С := {х £ Q j /,(г) < 0, г = 1,..., т} .

Точка 1° 6 П называется оптимальным решением в задаче выпуклого программирования, если /о(я°) < /о(х) для всех х £ Q.

Пусть I ■.— {1,2,..., гп} и пусть Ia(x) := {i 6 1 j ¡¡(х) — 0} для х € Ü. Символом |/0(i)i обозначим число элементов в 1а(х).

Теорема3.7. Точка х° € Q является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существуют вектор А = (Aj, Л2,..., Лт) 6 Rm и упорядоченное разбиение {1Х, • • •; h] (1 < к < |/а(з;0)|4-1) множества индексов 1= {1,2,..., т} , удовлетворяющие условиям:

а) неотрицательности Лх > 0, Л2 > 0,..., Лт > 0;

б) дополняющей нежесткости А,-/;(г°) = 0, i = 1,2,...,т;

в) минимума

V Л./.Сх°) = min Xifi(x), s = 1,2,..., k - 1, ш, xCQ- ш.

f0(x°) + \<Мх°) = min (fo(x) + А,■/,•(*) ieh \ «e/i,

где Qi = Q, Qi+1 = {xeQs | £ А./Дг) = 0}, s = 1,2,..., fc - 1.

¡6/,

В следствии 3.4 показывается, что в том случае, когда задача выпуклого программирования удовлетворяет условию регулярности Слейтера, доказанный в теореме 3.7 критерий совпадает с известным критерием Куна-Таккера.

Результаты главы 3 опубликованы в работах [3, 10, 11].

17

ЗАКЛЮЧЕНИЕ

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

Основными результатами диссертации являются:

1. Определение и свойства ступенчато-линейных и ступенчато-аффинных функций — новых классов вещественнозначных функций, определенных на вещественных векторных пространствах [1, 3, 5, 8, 12]. Самостоятельный интерес представляют также исследования таких объектов как пирамиды векторных подпространств [3], ступенчатые отношения предпорядка [2, 4], кортежи линейных и аффинных функций [3, 5], которые в диссертации играют вспомогательную роль при определении ступенчато-линейных и ступенчато-аффинных функций.

2. Геометрические и порядковые признаки полупространств (выпуклых подмножеств вещественного векторного пространства, дополнения которых также выпуклы) [2, 7, 9] и осуществленная на их основе классификация полупространств по типам и рангам [2, 5, 7].

3. Доказательство двойственности класса ступенчато-линейных функций и совокупности конических полупространств [1, 3, 5, 6], а также двойственность класса ступенчато-аффинных функций и совокупности всех полупространств вещественного векторного пространства [5, 11]. Эти двойственности распространяют, соответственно, классическую двойственность между линейными функциями и гиперподпространствами, а также двойственность между аффинными функциями и гиперплоскостями.

4. Общие теоремы об отделимости выпуклых множеств ступенчато-линейными и ступенчато-аффинными функциями [3, 10, 11].

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

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

6. Аналитическое представление конических отношений предпо-рядка, определенных на вещественном векторном пространстве, при помощи ступенчато-линейных функций [3, 8].

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

Статьи в научных жг/рпалах

1. Гороховик В.В., Семенкова Е.А. Ступенчато-линейные функции в конечномерных векторных пространствах. Определения, свойства и их связь с полупространствами// Докл. АН Беларуси,- 1997Т. 41, № 5.- С. 10-14.

2. Гороховик В.В., Семенкова Е.А. Классификация полупространств по типам в бесконечномерных векторных пространствах// Математические заметки.-1998,- Т. 64, вып. 2.- С. 191-198.

3. Гороховик В.В., Шинкевич Е.А. Теоремы об отделимости выпуклых множеств ступенчато-линейными функциями и их приложения к выпуклым задачам оптимизации// Нелинейный анализ и приложения/ Национальная Академия наук Беларуси. Труды Института математики.- 1998.- Т. 1.- С. 58-85.

4. Гороховик В.В., Шинкевич Е.А. Ступенчатые отношения предпорядка на векторных пространствах// Докл. АН Беларуси.-1998.- Т. 42, № 6.- С. 28-31.

5. Гороховик В.В., Шинкевич Е.А. Аналитическое представление бесконечномерных полупространств ступенчато-аффинными функциями// Нелинейный анализ и смежные вопросы/ Национальная Академия наук Беларуси. Труды Института математики.-1999.-Т. 2,- С. 63-72.

6. Семенкова Е.А. Об аналитическом представлении полупространств в конечномерных векторных пространствах// Весщ АН Беларусь Сер. ф!з.-мат. навук.- 1996 - №2,- С. 35-40.

Препринты

7. Гороховик В.В., Семенкова Е.А. О типах полупространств

в бесконечномерных векторных пространствах- Мн., 1996.- 14 с.-(Препринт/ Ин-т математики АН Беларуси; Аг?5(517)).

Тезисы докладов

8. Гороховик В.В., Семенкова Е.А. Ступенчато-линейные функции и отношения предпочтения на конечномерных векторных пространства,х// Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Материалы V межгос. науч. конф., Минск, 14-18 мая 1996 г./ Мин. образования и науки РБ. Бел. гос. университет. Академия Наук Беларуси.- Минск, 1996.- С. 182.

9. Гороховик В.В., Семенкова Е.А. О классификации полупространств в бесконечномерных векторных пространствах// VII Белорусская математическая Конференция: Тез. докл., Минск, 18-22 ноября 1996 г./ Мин. образования и науки РБ. Бел. матем. общество. Бел. гос. университет. Ин-т матем. АН Беларуси.- Минск, 1996,-Часть 3.- С. 150-151.

10. Шипкевич Е.А. Отделимость выпуклых множеств ступенчато-линейными функциями// Int. Conference "Dynamical Systems: Stability, Control, Optimization". Abstracts.-Vol. 2,- Minsk:Institute of Mathematics, National Academy of Sciences of Belarus, 1998.-P. 281283.

11. Gorokhovik V.V., Shinkevich E.A. General separation theorem and their applications to optimization problems// German-Polish Conference on Optimization Methods and Application. Abstracts.-Zagan, 1999 - P. 18-19.

12. Shinkevich E. A. On analytical representation of preference relations in problems of mahtematical economics// 20th Int. Scientific Symposium of Students and Young Reseach Workers. - Zielona Gora, 1998.- P. 216-219.

20

РЭЗЮМЭ

Шьшкев1ч Алена Аляксееуна

АДДЗЯЛЯЛЬНАСЦЬ ВЫПУКЛЫХ МНОСТВАУ СТУПЕНЧАТА-АФШНЫМ1 ФУНКДЫЯМ1 I ЯЕ ДАСТАСАВАНШ У ТЭОРЫ1 АПТЫМ13АЦЫ1

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

На сапраудных вектарных прасторах вызначаны 1 даследаваны новыя класы сапраудназначных функцый, як!я атрымалй назву сту-пенчата-лшейных I ступенчата-афшных. Здейснена клас1ф!кацыя бясконцамерных паупрастор (выпуклых мноствау вектарнай прас-торы, дапауненш яюх таксама выпуклыя) 1 установлена двукна-сць сукупнасщ камчных паупрастор з класам ступенчата-лгаейных функцый 1 двукнасць сукуинаспд уах паупрастор з класам ступенчата-афшных функцый. Даказаны агульныя тэарэмы аб аддзеляльна-сщ выпуклых мноствау ступенчата-лшейным! \ ступенчата-афшны-м! функцыям1 i на \х аснове распрацавана методыка доказу умоу аптымальнасщ у нерэгулярных выпуклых задачах аптым!3ацьй. Атрыманы дву!сныя крытэрьп аптымальнасщ рашэнняу у выпукл-ай задачы вектарнай аптым}зацьп I у клаачнай задачы выпуклага праграмавання без папярэдшх умоу рэгулярнасщ.

21

РЕЗЮМЕ

Шинкевич Елена Алексеевна

ОТДЕЛИМОСТЬ ВЫПУКЛЫХ МНОЖЕСТВ СТУПЕНЧАТО-АФФИННЫМИ ФУНКЦИЯМИ И ЕЕ ПРИЛОЖЕНИЯ В ТЕОРИИ ОПТИМИЗАЦИИ

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

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

SUMMARY

Shinkevich Elena Alekseevxia

SEPARATION OF CONVEX SETS BY STEP-AFFINE FUNCTIONS AND ITS APPLICATIONS TO OPTIMIZATION

THEORY

Key words: step-linear function, step-affine function, halfspace, seperation of convex sets, vector optimization, convex programming, preorder relation.

In the thesis the following main result are presented.

The definition and properties of step-linear and step-affinc functions, which form new classes of real-valued functions defined on real vector spaces.

Geometric and order characterization of halfspaces (convex sets with convex complements) and classification of infmite-dimentional halfspaces by types and rangs.

The proof of the duality between step-linear functions and conic halfspaces as well as the duality between step-affine functions and all halfspaces.

General theorems on seperation of convex sets by step-linear and step-affine functions.

The method for studying nonregular convex optimization problems and the proof of the optimality criterion for the convex vector optimizatior problem and the optimality criterion for the classical convex programming problem without any regularity conditions.

Analytical representations for conic preorder by step-linear functions.