Содержание к диссертации
Введение
1. Наилучшее линейное отделение двух множеств 14
2. Постановка задачи строгого /г-отделения 25
3. Строгая /г-отделимость и линейное программирование 30
4. Метод «градиентного типа» строгого /г-отделения 37
5. Безградиентный метод локального поиска 47
6. Численные эксперименты 56
Дополнение А. Двойственность в линейном программировании. 79
Дополнение В. Свойства плюсиковой функции 82
Дополнение С. Производные по направлению 85
Дополнение D. Лемма о сумме минимумов 89
Список литературы
- Постановка задачи строгого /г-отделения
- Строгая /г-отделимость и линейное программирование
- Безградиентный метод локального поиска
- Численные эксперименты
Постановка задачи строгого /г-отделения
Переходим к описанию одного шага численного метода минимизации функции F(G). Пусть имеется v-e приближение Gv. Для определения направления спуска из точки Gv решаем вспомогательную экстремальную задачу где минимум берётся по матрицам V размера h х (п + 1), все элементы которых ограничены по модулю некоторой константой К 0. Задача (6) сводится к небольшому числу задач линейного программирования. Она имеет решение Vv. Если F\GVl Vv) 0, то Gv — стационарная точка функции F(G). Вычисления прекращаются. В противном случае матрица Vv является направлением убывания функции F(G) из точки Gv. Находим шаг tv 0 в направлении Vv, обеспечивающий гарантированное уменьшение функции F(G). Полагаем Gv+\ = Gv + tvVV) после чего вычисления повторяются. Описание принципиальной схемы метода «градиентного типа» для решения задачи (4) завершено.
В 4 приводится пример на применение данного метода к решению задачи 3-отделения. Основное внимание уделяется организации вычислений.
В 5 предлагается ещё один численный метод решения задачи (4), максимально усиливающий её специфику. Опишем общий шаг этого метода. Фиксируем положительные параметры точности є А, Є В И & Пусть имеется v-e приближение — матрица Gv со строками ? , s Є 1 : h. Для получения очередного приближения Gv+\ выполняем следующие операции: 1) Вычисляем F{GV). ю 2) Формируем индексные множества Iv = {iel:m\ max f{gsu, аг) -єА}, Jv = {j Є 1 : к І min/(# , bj) -єв}, sGl .n Ц = {s Є 1 : h I f{gav, bj) = min f(fi, bj)}, j Є Jv. 3) Перебираєм индексные цепочки S = {SJ}J&JU) Sj Є LJ, пока не найдётся цепочка 5 = {SJ}JGJ„ co следующим свойством: решение Vv экстремаль ной задачи Q(GV + V):=-J2 4 №v + V) + \ J2 min где минимум берётся по матрицам V, все элементы которых ограничены по модулю некоторой константой К О, удовлетворяет неравенству Q(G„ + К) F(G„) - а. (7) 4) Полагаем Gv+\ = Gv + V , где — точка минимума функции F{GV + tVv) на отрезке [0, 1]. Если цепочка S: обеспечивающая неравенство (7), отсутствует, то Gv — почти локально оптимальная матрица. В этом случае вычисления прекращаются. Доказывается, что описанный процесс конечен.
В 6 на примере задачи 4-отделения проводятся широкие эксперименты по анализу численных методов, предложенных в 4 и 5. Обсуждается общая для обоих методов проблема выбора начального приближения.
В диссертации имеются четыре Дополнения. Дополнение А посвящено линейному программированию. Приводится теорема существования решения и две теоремы двойственности. Делается замечание о практическом решении задач линейного программирования в среде MATLAB.
В Дополнении В собраны многочисленные свойства плюсиковой функции. В Дополнении С выводится формула для производной по направлению от функции матрицы F{G). В Дополнении D доказывается лемма о сумме минимумов. Все результаты из Дополнений активно используются в основном тексте.
На защиту выносятся следующие результаты: анализ задачи наилучшего линейного отделения как негладкой параметрической задачи; анализ задачи наилучшего /г-отделения как негладкой и невыпуклой параметрической задачи; разработка метода «градиентного типа» для решения задачи /г-отделения; разработка безградиентного метода /г-отделения, максимально учитывающего специфику данной задачи.
Отдельные результаты диссертации докладывались на приводимых ни же конференциях и семинарах: на 40-й, 41-й, 42-й и 44-й Международных научных конференциях ас пирантов и студентов «Процессы управления и устойчивость», Санкт Петербург [17-20]; на Международной конференции «Конструктивный негладкий анализ и смежные вопросы», Санкт-Петербург, 2012 [32]; на Всероссийской молодёжной научной школе-семинаре «Дискретные модели и методы принятия решений», Новосибирск, 2013 (диплом за лучший доклад); на Санкт-Петербургском городском семинаре «Дискретный гармонический анализ и геометрическое моделирование» [8-10,13,14,21-23]; на семинарах кафедры математической теории моделирования систем управления факультета ПМ-ПУ (зав. кафедрой проф. В. Ф. Демьянов).
Основные результаты опубликованы в работах [15,16,40], в изданиях из списка ВАК. Автор приносит глубокую благодарность своему научному руководителю профессору Людмиле Николаевне Поляковой и профессору Василию Николаевичу Малозёмову за постоянное внимание к моей работе и неоценимую помощь.
Строгая /г-отделимость и линейное программирование
Множество планов задачи (1.10) непусто (например, планом является вектор с компонентами w = О, 7 = 0, уі = с, Zj = с) и целевая функция ограничена снизу нулём. Значит, задача (1.10) имеет решение. По эквивалентности существует решение и у задачи (1.9), причём минимальные значения целевых функций у этих задач равны между собой. Это общее значение обозначим через /І. Отметим также, что если (if , 7 , {у }, izj}) решение задачи (1.10), то д = («4,7 ) решение задачи (1.9). 1.5.
Значит, /(go) = 0 при с = со- Гиперплоскость Дэ = {х \ {WQ,X) = 70} строго отделяет множество А от множества , причём ширина отделяющей полосы равна 2со На рис. 1.3 приведён пример строгого отделения. является наилучшей гиперплоскостью, приближённо отделяющей мно жество А от множества В (при данном значении параметра с).
Здесь, однако, имеется тонкость: нет гарантии, что компонента w вектора д отлична от нулевой. Разберёмся в этой ситуации.
Теорема 1.2. Для того чтобы задача (1.9) имела решение д = (w , 7 ) с ги = 0; необходимо и достаточно, чтобы выполнялось условие Доказательство. Необходимость. При w = О легко вычисляется экстремальное значение целевой функции у задачи линейного программирования (1.10). Действительно,
Такое же экстремальное значение имеет задача линейного программирования, двойственная к задаче (1.10). В силу разрешимости двойственной задачи совместна система т к
Принимая во внимание (1.15), заключаем, что все щ равны — и все Vj равны . Теперь формула (1.13) становится эквивалентной равенству (1.11). Достаточность. Запишем задачу, двойственную к (1.10): при ограничениях (1.13)-(1.15). В силу (1.11) набор щ = , и,- = является планом этой задачи. Значение целевой функции на нём равно 2с. Вместе с тем, на плане задачи (1.10) значение целевой функции также равно 2с. Отсюда следует, что план (1.16) задачи (1.10) с w = О является оптимальным.
Значит, на векторе до достигается минимум функции f(g). Гиперплоскость Щ = {х х\ + Х2 = 1} является наилучшей гиперплоскостью, приближённо отделяющей множество А от множества В.
Таким же свойством обладают вектор д\ = (it i,7i) с W\ = (0,с), 71 = и гиперплоскость #i = {х Ж2 = т } (см. рис. 1.4). 1.7. Особенность,отмеченная в примере 1.2, имеет общий характер. Теорема 1.3. При /І 0 у задачи (1.9) существует решение до = (щ),7о) cwoj O.
Доказательство. Допустим, что у решения д = (ад ,7 ) задачи (1.9) компонента w оказалась нулевой. Построим другое решение до = ( о,7о) с w0 jt О.
По теореме 1.2 выполняется соотношение (1.11) и /І = 2с. Возьмём произвольный ненулевой вектор р Є Шп и рассмотрим задачу линейного программирования
Вектор (1.16) удовлетворяет ограничениям задачи (1.17), то есть является её планом. Покажем, что этот план не может быть оптимальным.
В случае оптимальности плана (1.16) у задачи, двойственной к (1.17), должен существовать план с таким же (нулевым) значением целевой функции. Таким образом, должна быть совместной система
Но это противоречит условию (1.11) (напомним, что р ф Установлено, что план (1.16) задачи (1.17) с нулевым значением целевой функции не является оптимальным. Значит, существует план с отрицательным значением целевой функции. У такого плана должно быть w0 фО.
Теперь отметим, что план (1.22) задачи (1.17) удовлетворяет ограничениям задачи (1.10) и на нём целевая функция задачи (1.10) принимает наименьшее возможное значение, равное 2с (напомним, что /І = 2с). В силу эквивалентности задач (1.9) и (1.10) вектор до = ( о,7о) с Wo ф О будет решением задачи (1.9).
Замечание. В качестве ненулевого вектора р можно взять, например, любую ненулевую разность bj0 — сц,. В этом случае множество планов задачи, двойственной к (1.17), которое определяется условиями (1.19)- (1.21), будет непустым. Вместе с непустотой множества планов самой задачи (1.17) это гарантирует наличие у задачи (1.17) оптимального плана.
Пусть G — какое-нибудь решение задачи (2.6) и /i = F(G ). Если /і = О, то по теореме 2.2 множества со(А) и В строго (її — J)-отделимы, где J — множество индексов s Є 1 : /г, на которых ID = О. В частности, если G — подходящая матрица, то множества со(А) и В строго /г-отделимы. При /І 0 по теореме 2.1 строгое /г-отделение невозможно. Если соответствующая матрица G подходящая, то будем говорить, что она обеспечивает наилучшее приближённое h-отделение множеств со{А) и В.
Безградиентный метод локального поиска
Учитывая, что G2 — подходящая матрица, заключаем, что G2 — решение рассматриваемой задачи (см. рис. 4.4). Выбор параметра с = 0 не соответствует теории (по теории нужно брать с 0). При с = 0 очевидным решением задачи (3.1) является матрица G = О. Однако решение неединственно. Мы начинали вычисления с подходящей матрицы Go и пришли к подходящей матрице G2l которая реализует /г-отделение, правда, нестрогое.
Теперь вместо с = 0 положим с = . В качестве начального приближения возьмём ту же матрицу Go. Заполним таблицу 5 и таблицу 6. 2
Рассмотрим ещё один, безградиентный, метод решения задачи (4.1), максимально учитывающий её специфику. Описание метода потребует некоторой подготовки.
В пространстве M.n+l будем использовать равномерную норму векторов, В силу неотрицательности F(G) описанный процесс конечен. Через конечное число шагов получим почти локально оптимальную матрицу G . 5.5. Опишем общий шаг вычислительного процесса. В нём используются глобальные параметры є А, Є В И а.
Пусть имеется v-e приближение — матрица Gv со строками g, s Є 1 : h. Для получения очередного приближения Gv+\ выполняются следующие операции:
Замечание. Если цепочка S: обеспечивающая неравенство (5.27), отсутствует, то Gv — почти локально оптимальная матрица. 6. Численные эксперименты
В этом параграфе приводятся результаты численных экспериментов по применению метода градиентного типа (4) и безградиентного метода (5) к решению задачи /г-отделения двух множеств со(А) и В из Мп, где
Общей проблемой обоих методов является выбор начального приближения. Представляется естественным такой подход.
В множестве В\ := В берём произвольную точку bjx и с помощью гиперплоскости Н\ = \х\ {wl,x) = 7i} линейно отделяем её от со (А). Далее, в множестве 2 = {bj Є В\ {wl,bj) 71} берём произвольную точку bj2 и с помощью гиперплоскости Н 2 = {х \ (w2,x) =72} линейно отделяем её от со(А). Процесс продолжается до тех пор, пока не будет построена гиперплоскость Hh = {х {wh,x) = 7/1}, линейно отделяющая точку bjh Є By, от со(Л). Здесь Bh = {bj Є Bh_x I (wh-\bj) 7 1}. Матрицу Go со строками («;S,7S), s = 1,...,/г, можно взять в качестве начального приближения.
На самом деле, в описанном процессе на р-м шаге вместо одной точки bjp Є Вр можно брать несколько точек из Вр. Предельный случай выглядит так: множество В разбивается на h непересекающихся подмножеств и каждое подмножество, независимо, линейно отделяется от со(А).
Доказательство приведенных в этом Дополнении фактов имеется, например, в [3, глава 1]. А.6. Для решения задач линейного программирования разработаны эффективные численные методы. В пакете MATLAB задействованы два метода: метод внутренней точки (Large-Scale Algorithm) и вариант симплекс-метода (Medium-Scale Algorithm). По умолчанию используется метод внутренней точки. Программа реализована в виде функции Linprog. Описанию возможностей этой функции (с большим количеством примеров) посвящена работа [13].
При решении задач математической диагностики используются статистические методы [2,53] , методы математического программирования (линейного [12,38,41,51], билинейного [30], выпуклого [52]) и методы глобальной оптимизации [28]. Значительный вклад в развитие этого направления внесли М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр [1], В. Н. Вап-ник [2,53], А. Л. Горелик [4], Ю. И. Журавлёв [6], Ю. И. Неймарк [11], В. Н. Фомин [24], Я. 3. Цыпкин [25], В. А. Якубович [26]. Особо следует отметить О. Л. Мангасаряна. По его работам 1965-2014 годов [в частности, 41-47, 29, 30, 37] можно проследить за всеми этапами развития математической диагностики.
При решении конкретных задач математической диагностики возникает необходимость в построении правила, в соответствии с которым судят о принадлежности данной точки тому или другому множеству. Это правило называют диагностическим правилом. Чаще всего его реализуют в виде дискриминантной функции (функционала). С начала 90-х годов прошлого столетия в качестве дискриминантной активно используются недифферен цируемые функции. С их помощью удаётся, в частности, улучшить результаты в следующем направлении: в случае, когда выпуклые оболочки двух отделяемых множеств пересекаются, более точно выделить «смешанную полосу», содержащую точки как одного, так и другого множества.
Для решения негладких задач математической диагностики привлекаются методы недифференцируемой оптимизации [35, 36, 27, 5, 7]. Примечательно, что при их реализации важную роль играет линейное программирование. Отметим также работы [31,33,34,39,48-50], которые обогатили арсенал методов математической диагностики.
Данное исследование проводится в русле работ Беннет-Мангасаряна [29] и Асторино-Гаудиозо [27]. Изучается задача наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью нескольких гиперплоскостей. Используется недифферен-циремая дискриминантная функция с параметром. Параметр вводится для преодоления вычислительных трудностей, связанных с принципиальной неединственностью решения соответствующих экстремальных задач. Диссертация состоит из шести параграфов и четырёх дополнений. параметр (в [29] вместо с стоит единица), [и}+ = тах{0, и} — плюсиковая функция. Справедливо следующее утверждение. Теорема 1.1. Множества А и В строго линейно отделимы тогда и только тогда, когда существует вектор д , на котором /( ? ) = 0.
Задача (3) всегда имеет решение. Обозначим его (w ,7 ІУІ}? izj}) и пусть /І — минимальное значение целевой функции. Если /І = 0, то гиперплоскость Н , определяемая уравнением (w x) = 7 , строго отделяет множество А от множества В. При этом можно вычислить ширину отделяющей полосы.
При /І 0 множества А и не допускают строгого линейного отделения. В этом случае будем говорить, что указанная ранее гиперплоскость Н : является наилучшей гиперплоскостью, приближённо отделяющей множество А от множества В. Можно вычислить ширину «смешанной полосы», содержащей точки обоих множеств.
При /І 0 имеется тонкость: может оказаться, что w = О. Доказывается, что в этом случае у задачи (3) существует другое решение с w = О. Оно строится с помощью вспомогательной задачи линейного программирования.
Приводятся примеры строгого и наилучшего приближённого линейного отделения. Выясняется, что аддитивный параметр с играет роль нормирующего множителя.
В 2 переходим к основной задаче — отделению выпуклой оболочки одного конечного множества от другого конечного множества с помощью h гиперплоскостей (задача /г-отделения). Пусть множества А и В имеют вид (1). Обозначим со(А) выпуклую оболочку множества А. Введём функцию от матрицы [27] вместо с стоит единица). Матрицу G указанных размеров будем называть подходящей, если у неё все wa ненулевые. Справедливо следующее утверждение. Теорема 2.1. Выпуклая оболочка множества А и множество В строго h-отделимы тогда и только тогда, когда существует подходящая матрица G , на которой F(G ) = 0.
Учитывая, что F(G) 0 при всех G, заключаем, что задача строгого /г-отделения сводится к экстремальной задаче Итак, в 3 установлен принципиальный факт: задача /г-отделения сводится к конечному числу задач линейного программирования. Однако количество таких задач линейного программирования может быть большим. Это побуждает обратиться к итерационным методам, которые позволяют получить приближённое решение задачи /г-отделения с требуемой точностью.
Из общих соображений следует, что функция от матрицы F(G) дифференцируема по направлениям (в качестве которых также выступают матрицы). На этой основе в 4 строится метод «градиентного типа» для приближённого решения задачи /г-отделения (4). Опишем его принципальную схему.
