Диссертация (1149837), страница 2
Текст из файла (страница 2)
Пусть имеется ν-е приближение 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-отделения. Основное внимание уделяется организации вычислений.§4 написан на основе работ [16, 23].4. В §5 предлагается ещё один численный метод решения задачи (4), максимально усиливающий её специфику.
Опишем общий шаг этого метода.Фиксируем положительные параметры точности εA , εB и σ.Пусть имеется ν-е приближение — матрица Gν со строками gνs ,s ∈ 1 : h. Для получения очередного приближения Gν+1 выполняем следующие операции:1) Вычисляем F (Gν ).102) Формируем индексные множества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ν —почти локально оптимальная матрица.
В этом случае вычисления прекращаются.Доказывается, что описанный процесс конечен.§5 написан на основе работы [9].5. В §6 на примере задачи 4-отделения проводятся широкие эксперименты по анализу численных методов, предложенных в §4 и §5. Обсуждаетсяобщая для обоих методов проблема выбора начального приближения.6. В диссертации имеются четыре Дополнения.11Дополнение A посвящено линейному программированию. Приводитсятеорема существования решения и две теоремы двойственности. Делается замечание о практическом решении задач линейного программированияв среде MATLAB.В Дополнении B собраны многочисленные свойства плюсиковой функции.В Дополнении C выводится формула для производной по направлениюот функции матрицы F (G).В Дополнении D доказывается лемма о сумме минимумов.Все результаты из Дополнений активно используются в основном тексте.7.
На защиту выносятся следующие результаты:• анализ задачи наилучшего линейного отделения как негладкой параметрической задачи;• анализ задачи наилучшего h-отделения как негладкой и невыпуклойпараметрической задачи;• разработка метода «градиентного типа» для решения задачи h-отделения;• разработка безградиентного метода h-отделения, максимально учитывающего специфику данной задачи.8. Отдельные результаты диссертации докладывались на приводимых ниже конференциях и семинарах:• на 40-й, 41-й, 42-й и 44-й Международных научных конференциях аспирантов и студентов «Процессы управления и устойчивость», СанктПетербург [17–20];12• на Международной конференции «Конструктивный негладкий анализи смежные вопросы», Санкт-Петербург, 2012 [32];• на Всероссийской молодёжной научной школе-семинаре «Дискретныемодели и методы принятия решений», Новосибирск, 2013 (диплом залучший доклад);• на Санкт-Петербургском городском семинаре «Дискретный гармонический анализ и геометрическое моделирование» [8–10, 13, 14, 21–23];• на семинарах кафедры математической теории моделирования системуправления факультета ПМ-ПУ (зав.
кафедрой проф. В. Ф. Демьянов).Основные результаты опубликованы в работах [15, 16, 40], в изданиях изсписка ВАК.Автор приносит глубокую благодарность своему научному руководителю профессору Людмиле Николаевне Поляковой и профессору ВасилиюНиколаевичу Малозёмову за постоянное внимание к моей работе и неоценимую помощь.13§ 1.Наилучшее линейное отделение двух множествНа линейном уровне исследуется задача наилучшего приближённого отделения двух конечных множеств. Эта задача сводится к задаче негладкойоптимизации, при анализе которой используется вся мощь теории линейного программирования.В идейном плане мы следуем работе [29].1.1.
Пусть в пространстве Rn заданы два конечных множестваkA = {ai }mi=1 и B = {bj }j=1 .Множества A и B называются строго отделимыми, если существуют ненулевой вектор w ∈ Rn и вещественное число γ, такие, чтоhw, ai i < γпри всех i ∈ 1 : m,(1.1)hw, bj i > γпри всех j ∈ 1 : k.(1.2)При выполнении условий (1.1) и (1.2) говорят также, что гиперплоскость H,определяемая уравнением hw, xi = γ, строго отделяет множество A отмножества B.1.2. Введём функциюmk1 X1 Xhw, ai i − γ + c + +−hw, bj i + γ + c + ,f (g) =m i=1k j=1(1.3)где g = (w, γ), g ∈ Rn+1 , c > 0 — параметр и [u]+ = max{0, u}. Ясно, чтоf (g) ≥ 0 при всех g.Теорема 1.1.
Множества A и B строго отделимы тогда и только тогда, когда существует вектор g∗ , на котором f (g∗ ) = 0.Д о к а з а т е л ь с т в о. Пусть f (g∗ ) = 0 на некотором векторе g∗ = (w∗ , γ∗ ).14Покажем прежде всего, что w∗ 6= O. В противном случае−γ∗ + cпри γ∗ ≤ −c,f (g∗ ) = (−γ∗ + c)+ + (γ∗ + c)+ =2cпри γ∗ ∈ [−c, c], γ∗ + cпри γ∗ ≥ c.Отсюда следует, что f (g∗ ) ≥ 2c.
Это противоречит условию f (g∗ ) = 0.Далее, условие f (g∗ ) = 0 гарантирует, что все слагаемыеhw∗ , ai i − γ∗ + cи+−hw∗ , bj i + γ∗ + cравны нулю. Это возможно лишь тогда, когда+hw∗ , ai i − γ∗ + c ≤ 0 при всех i ∈ 1 : m,(1.4)−hw∗ , bj i + γ∗ + c ≤ 0 при всех j ∈ 1 : k.(1.5)Остаётся отметить, что неравенства (1.4) и (1.5) обеспечивают выполнениеусловий строгой отделимости (1.1) и (1.2) с w = w∗ , γ = γ∗ .Докажем обратное утверждение. Пусть выполнены условия (1.1) и (1.2).Обозначимd := min hw, bj i − maxhw, ai i > 0,w∗ = ( 2cd )w,γ∗ =(1.6)i∈1:mj∈1:k1min hw∗ , bj i2 j∈1:kСогласно (1.6) и определению w∗+ maxhw∗ , ai i .i∈1:mmin hw∗ , bj i − maxhw∗ , ai i = 2c.i∈1:mj∈1:kИмеемmaxhw∗ , ai i = 2γ∗ − min hw∗ , bj i = 2γ∗ − 2c − maxhw∗ , ai i,i∈1:mi∈1:mj∈1:kтак чтоmaxhw∗ , ai i = γ∗ − c.i∈1:m15(1.7)Аналогичноmin hw∗ , bj i = 2γ∗ − maxhw∗ , ai i = 2γ∗ + 2c − min hw∗ , bj i,i∈1:mj∈1:kj∈1:kтак чтоmin hw∗ , bj i = γ∗ + c.j∈1:k(1.8)Положим g∗ = (w∗ , γ∗ ).
На основании (1.7) и (1.8) получим f (g∗ ) = 0.Теорема доказана.1.3. При доказательстве теоремы 1 описано преобразование вектораg= (w, γ), порождающего строго отделяющую гиперплоскостьH = x | hw, xi = γ , в вектор g∗ = (w∗ , γ∗ ), на котором f (g∗ ) = 0. Делов том, что на само́м векторе g значение f (g) может быть положительным(это зависит от параметра c).Пример 1.1. В качестве A и B возьмём одноточечные множества наплоскости R2 : A = {a}, B = {b}, где a = (0, 0) и b = (0, 2). Векторg = (w, γ) с компонентами w = (0, 1) и γ из интервала (0, 2) порождает прямую x2 = γ, строго отделяющую точку a от точки b (см. рис.
1.1).Рис. 1.1. Строгое отделение двух точекВместе с тем,f (g) = [−γ + c]+ + [−2 + γ + c]+ .На рис. 1.2 представлен график f (g) как функции от γ при c ∈ (0, 1].16Рис. 1.2. График функции f (g)Видим, что f (g) = 0 при γ ∈ [c, 2 − c]. При γ ∈ (0, c) ∪ (2 − c, 2) прямаяx2 = γ по-прежнему строго отделяет точку a от точки b, но f (g) > 0.1.4. Рассмотрим экстремальную задачуf (g) → min,(1.9)где f (g) — функция вида (1.3). Эта задача эквивалентна задаче линейногопрограммированияmk1 X1Xyi +zj → min,m i=1k j=1−hw, ai i + γ + yi ≥ c,(1.10)i ∈ 1 : m;hw, bj i − γ + zj ≥ c, j ∈ 1 : k;yi ≥ 0, i ∈ 1 : m;zj ≥ 0, j ∈ 1 : k.Множество планов задачи (1.10) непусто (например, планом являетсявектор с компонентами w = O, γ = 0, yi ≡ c, zj ≡ c) и целевая функцияограничена снизу нулём. Значит, задача (1.10) имеет решение.
По эквивалентности существует решение и у задачи (1.9), причём минимальныезначения целевых функций у этих задач равны между собой. Это общеезначение обозначим через µ. Отметим также, что если w∗ , γ∗ , {yi∗ }, {zj∗ } —решение задачи (1.10), то g∗ = (w∗ , γ∗ ) — решение задачи (1.9).171.5. При µ = 0 получим f (g∗ ) = 0. По теореме 1 вектор g∗ = (w∗ , γ∗ ) порождает гиперплоскость H = x ∈ Rn | hw∗ , xi = γ∗ , строго отделяющуюмножество A от множества B.Вектор g∗ можно привести к каноническому виду. Положимw0 = w∗ /kw∗ k,γ0 =1min hw0 , bj i2 j∈1:kc0 =1min hw0 , bj i2 j∈1:k+ maxhw0 , ai i ,i∈1:m− maxhw0 , ai i ,i∈1:mg0 = (w0 , γ0 ).Тогда при всех i ∈ 1 : mhw0 , ai i − γ0 + c0 = hw0 , ai i − maxhw0 , ai i ≤ 0,i∈1:mи при всех j ∈ 1 : k−hw0 , bj i + γ0 + c0 = −hw0 , bj i + min hw0 , bj i ≤ 0.j∈1:kЗначит, f (g0 ) = 0 при c = c0 .
Гиперплоскость H0 =x | hw0 , xi = γ0строго отделяет множество A от множества B, причём ширина отделяющейполосы равна 2c0 .На рис. 1.3 приведён пример строгого отделения.1.6. Как отмечалось в п. 1.4, задача (1.9) всегда имеет решение. Приµ > 0 по теореме 1.1 множества A и B не допускают строгого линейного отделения. В этом случае будем говорить, что гиперплоскостьH∗ = x | hw∗ , xi = γ∗ , порождаемая решением g∗ = (w∗ , γ∗ ) задачи (1.9),является наилучшей гиперплоскостью, приближённо отделяющей множество A от множества B (при данном значении параметра c).Здесь, однако, имеется тонкость: нет гарантии, что компонента w∗ вектора g∗ отлична от нулевой.
Разберёмся в этой ситуации.18Рис. 1.3. Пример строгого отделения двух множествТеорема 1.2. Для того чтобы задача (1.9) имела решение g∗ = (w∗ , γ∗ ) сw∗ = O, необходимо и достаточно, чтобы выполнялось условиеmk1X1 Xai =bj .m i=1k j=1(1.11)Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. При w∗ = O легко вычисляется экстремальное значение целевой функции у задачи линейного программирования (1.10).
Действительно,µ = f (g∗ ) = min [−γ + c]+ + [γ + c]+ = 2c.γТакое же экстремальное значение имеет задача линейного программирования, двойственная к задаче (1.10). В силу разрешимости двойственнойзадачи совместна система19cXmui +i=1−mXkXui ai +vj bj = O,(1.13)j=1mXui −i=11m,(1.12)j=1i=10 ≤ ui ≤= 2c,vjkXkXvj = 0,(1.14)j=10 ≤ vj ≤ k1 , j ∈ 1 : k.i ∈ 1 : m;(1.15)Из (1.12) и (1.14) следует, чтоmXkXui = 1,i=1vj = 1.j=1Принимая во внимание (1.15), заключаем, что все ui равны1mи все vj рав-ны k1 . Теперь формула (1.13) становится эквивалентной равенству (1.11).Д о с т а т о ч н о с т ь. Запишем задачу, двойственную к (1.10):XmkXcui +vj → maxi=1j=1при ограничениях (1.13)–(1.15). В силу (1.11) набор ui ≡1m,vj ≡1kявляетсяпланом этой задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
