Автореферат (1149836), страница 2
Текст из файла (страница 2)
Обозначим co(A) выпуклую оболочку множества A.Введем функцию от матрицыmk s1X1 Xmax hw , ai i − γs + c + +min −hws , bj i + γs + c + .F (G) =m i=1 s∈1:hk j=1 s∈1:hЗдесь G — матрица размера h × (n + 1) со строкамиg s = (ws , γs ),s ∈ 1 : h,c > 0 — параметр. Матрицу G указанных размеров будем называть подходящей,7если у нее все ws ненулевые.Справедливо следующее утверждение.Теорема 2.1.
Выпуклая оболочка множества A и множество B строго hотделимы тогда и только тогда, когда существует подходящая матрица G∗ ,на которой F (G∗ ) = 0.Учитывая, что F (G) ≥ 0 при всех G, заключаем, что задача строгогоh-отделения сводится к экстремальной задачеF (G) →(4)min .G∈Rh,n+1При минимизации функции F (G) наибольшую трудность доставляет второеслагаемое (сумма минимумов). Оно делает функцию F (G) невыпуклой (к тому,что она негладкая).В § 3 показывается, что задача (4) с помощью «леммы о сумме минимумов» сводится к конечному числу задач линейного программирования.
Дляэтого вводятся индексные цепочки S = (s1 , s2 , . . . , sk ), где sj ∈ 1 : h при каждом j ∈ 1 : k. Каждой такой цепочке S сопоставляется экстремальная задачаmk1 X1 Xmax hws , ai i − γs + c + +−hwsj , bj i + γsj + c + → min,Gm i=1 s∈1:hk j=1эквивалентная задаче линейного программированияmk1X1 Xpi +qj → min,m i=1k j=1−hai , ws i + γs + pi ≥ c,(5)i ∈ 1 : m, s ∈ 1 : h;hbj , wsj i − γsj + qj ≥ c, j ∈ 1 : k;pi ≥ 0,i ∈ 1 : m;qj ≥ 0,j ∈ 1 : k.Задача (5) имеет решение при всех S. Выделим цепочку S∗ , на которой мини-8мальное значение целевой функции в задаче (5) принимает наименьшее значение. Обозначим {w∗s }, {γs∗ }, {p∗i }, {qj∗ } соответствующее решение задачи (5).В § 3 доказывается (теорема 3.1), что матрица G∗ , составленная из строк(w∗s , γs∗ ), s ∈ 1 : h, является решением задачи (4).Возможны такие случаи.1) F (G∗ ) = 0 и G∗ — подходящая матрица. Тогда система гиперплоскостей H∗s ,определяемых уравнениями hw∗s , xi = γs∗ , s ∈ 1 : h, строго отделяет co(A)от B.2) F (G∗ ) = 0, но матрица G∗ — неподходящая.
В этом случае справедливоутверждение (теорема 2.2): не все w∗s нулевые; если обозначить через Jмножество индексов ненулевых w∗s , то множества co(A) и B строго h−|J| -отделимы.3) F (G∗ ) > 0 и G∗ — подходящая матрица. По аналогии со случаем h = 1будем говорить, что система гиперплоскостей H∗s , s ∈ 1 : h, осуществляетнаилучшее приближенное h-отделение множества co(A) от B.В § 3 приведен пример строгого 2-отделения.Итак, в § 3 установлен принципиальный факт: задача h-отделения сводится к конечному числу задач линейного программирования.
Однако количество таких задач линейного программирования может быть большим. Этопобуждает обратиться к итерационным методам, которые позволяют получитьприближенное решение задачи h-отделения с требуемой точностью.Из общих соображений следует, что функция от матрицы F (G) дифференцируема по направлениям (в качестве которых также выступают матрицы).На этой основе в § 4 строится метод «градиентного типа» для приближенногорешения задачи h-отделения (4).
Опишем его принципальную схему.9Начнем с производной по направлению. По определениюF (G + tV ) − F (G).t→+0tF ′ (G, V ) = limДля того чтобы записать для F ′ (G, V ) явную формулу, введем обозначенияf (v, u) = hv, ui + c,!!ai−bjâi =, b̌j =,−11ϕ̂i (G) = max f (g s , âi ),ψ̌j (G) = min f (g s , b̌j ),s∈1:hs∈1:hψj (G) = ψ̌j (G) + .ϕi (G) = ϕ̂i (G) + ,Тогдаmk1 X1XF (G) =ϕi (G) +ψj (G).m i=1k j=1Положим далееR̂i (G) = s ∈ 1 : h | f (g s , âi ) = ϕ̂i (G) ,Řj (G) = s ∈ 1 : h | f (g s , b̌j ) = ψ̌j (G) .Теорема 4.1. Справедлива формулаmk1X ′1 X ′ϕ (G, V ) +ψ (G, V ),F (G, V ) =m i=1 ik j=1 j′гдеmax hv s , âi i,если ϕ̂i (G) > 0,s∈R̂(G) i sϕ′i (G, V ) =maxhv,âii + , если ϕ̂i (G) = 0,s∈R̂(G)i0,если ϕ̂i (G) < 0;10min hv s , b̌j i,если ψ̌j (G) > 0,s∈Řj (G) s′ψj (G, V ) =minhv,b̌ij + , если ψ̌j (G) = 0,s∈Ř(G)j0,если ψ̌j (G) < 0.В Дополнении C приводится доказательство этой теоремы.Переходим к описанию одного шага численного метода минимизации функции F (G).
Пусть имеется ν-е приближение Gν . Для определения направленияспуска из точки Gν решаем вспомогательную экстремальную задачуF ′ (G, V ) → min,(6)где минимум берется по матрицам V размера h × (n + 1), все элементы которыхограничены по модулю некоторой константой K > 0. Задача (6) сводится кнебольшому числу задач линейного программирования. Она имеет решение Vν .Если F ′ (Gν , Vν ) ≥ 0, то Gν — стационарная точка функции F (G). Вычисления прекращаются. В противном случае матрица Vν является направлением убывания функции F (G) из точки Gν .
Находим шаг tν > 0 в направлении Vν , обеспечивающий гарантированное уменьшение функции F (G). Полагаем Gν+1 = Gν + tν Vν , после чего вычисления повторяются. Описание принципиальной схемы метода «градиентного типа» для решения задачи (4) завершено.В § 4 приводится пример на применение данного метода к решению задачи3-отделения. Основное внимание уделяется организации вычислений.В § 5 предлагается еще один численный метод решения задачи (4), максимально усиливающий ее специфику.
Опишем общий шаг этого метода.Фиксируем положительные параметры точности εA , εB и σ.Пусть имеется ν-е приближение — матрица Gν со строками gνs , s ∈ 1 : h.Для получения очередного приближения Gν+1 выполняем следующие операции:111) Вычисляем F (Gν ).2) Формируем индексные множестваIν = i ∈ 1 : m | max f (gνs , âi ) > −εA ,s∈1:hJν = j ∈ 1 : k | min f (gνs , b̌j ) > −εB ,s∈1:hLνj = s ∈ 1 : h | f (gνs , b̌j ) = min f (gνp , b̌j ) ,p∈1:hj ∈ Jν .3) Перебираем индексные цепочки S = {sj }j∈Jν , sj ∈ Lνj , пока не найдетсяцепочка Ŝ = {ŝj }j∈Jν со следующим свойством: решение V̂ν экстремальнойзадачиQ̂(Gν + V ) :=1 X1 X ŝjϕi (Gν + V ) +f (gν + v ŝj , b̌j ) + → min,mki∈Iνj∈Jνгде минимум берется по матрицам V , все элементы которых ограничены помодулю некоторой константой K > 0, удовлетворяет неравенствуQ̂(Gν + V̂ν ) < F (Gν ) − σ.(7)4) Полагаем Gν+1 = Gν + t̂ν V̂ν , где t̂ν — точка минимума функции F (Gν + tV̂ν )на отрезке [0, 1].Если цепочка Ŝ, обеспечивающая неравенство (7), отсутствует, то Gν —почти локально оптимальная матрица.
В этом случае вычисления прекращаются.Доказывается, что описанный процесс конечен.В § 6 на примере задачи 4-отделения проводятся широкие экспериментыпо анализу численных методов, предложенных в § 4 и § 5. Обсуждается общаядля обоих методов проблема выбора начального приближения.В диссертации имеются четыре Дополнения.Дополнение A посвящено линейному программированию. Приводится12теорема существования решения и две теоремы двойственности. Делается замечание о практическом решении задач линейного программирования в средеMATLAB.В Дополнении B собраны многочисленные свойства плюсиковой функции.В Дополнении C выводится формула для производной по направлениюот функции матрицы F (G).В Дополнении D доказывается лемма о сумме минимумов.Все результаты из Дополнений активно используются в основном тексте.ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИПубликации в изданиях, входящих в перечень ВАК рецензируемых научных журналов:1.
Чернэуцану (Вздыхалкина) Е. К. Анализ задачи строгого hотделения двух множеств. Вестник СПбГУ. Сер. 10. 2012. No 4, c.85–91.2. Чернэуцану (Вздыхалкина) Е. К. Метод градиентного типа длярешения задачи строгого h-отделения // Вестник СПбГУ. Сер. 10.2013. No 2, c. 67–75.3. Malozemov V. N. and Cherneutsanu (Vzdykhalkina) E. K. Thebest linear separation of two sets // Springer Optimization and its ApplicationSpringer Sciense+Business Media.
New York, 2014. Vol. 87, pp. 175–183.Публикации в других изданиях:4. Cherneutsanu (Vzdykhalkina) E. On strict h-polyhedral separability of twosets // International Conference «Constructive Nonsmooth Analysis and RelatedTopics». Abstracts. SPb, 2012. P.33–34.5. Чернэуцану (Вздыхалкина) Е.
К. Наилучшее линейное отделение двух13множеств / Всероссийская молодежная школа-семинар «Дискретные моделии методы принятия решений»: Материалы школы-семинара (г. Новосибирск,21-23 июня 2013). Новосибирск: Изд-во ин-та математики, 2013. C. 329.6. Чернэуцану (Вздыхалкина) Е. К. Нахождение разделяющей гиперплоскости между двумя политопами / Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов.
СанктПетербург, 2010. С. 736–739.7. Чернэуцану (Вздыхалкина) Е. К. Строгая h-отделимость двух множестви линейное программирование / Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов. СанктПетербург, 2011. С. 259–265.8.
Чернэуцану (Вздыхалкина) Е. К. Численные эксперименты по строгойh-отделимости / Процессы управления и устойчивость: Труды 44-й международной научной конференции аспирантов и студентов. Санкт-Петербург, 2013.С. 88–93.9. Малозёмов В. Н., Чернэуцану (Вздыхалкина) Е. К. Численный методстрогого h-отделения // Семинар по дискретному гармоническому анализу игеометрического моделированию «DHA & CAGD». Избранные доклады. 15 октября 2011 г.(http://dha.spb.ru/PDF/hSepNumerical.pdf)14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
