Диссертация (1149837), страница 8
Текст из файла (страница 8)
Описаниювозможностей этой функции (с большим количеством примеров) посвящена работа [13].81ДОПОЛНЕНИЕ BСвойства плюсиковой функцииИмеются в виду свойства функции [x]+ = max{0, x}.1) x ≤ [x]+ ≤ |x|2) [x + y]+ ≤ [x]+ + [y]+Д о к а з а т е л ь с т в о. Согласно 1) имеемx + y ≤ [x]+ + [y]+ .Вместе с тем, 0 ≤ [x]+ + [y]+ . Значит,[x + y]+ = max{0, x + y} ≤ [x]+ + [y]+ .3) [x]+ − [y]+ ≤ |x − y|;Д о к а з а т е л ь с т в о.
Имеемx = y + (x − y) ≤ [y]+ + |x − y|,так что [x]+ ≤ [y]+ + |x − y|. Аналогично [y]+ ≤ [x]+ + |y − x|. Из двухпоследних неравенств следует требуемое.4) [cx]+ = c[x]+ при c > 0.Д о к а з а т е л ь с т в о. При x ≤ 0 равенство принимает вид 0 = 0, апри x > 0 соответственно cx = cx.5) max[xs ]+ = [max xs ]+ .s∈1:hs∈1:hД о к а з а т е л ь с т в о. Если max xs ≤ 0, то утверждение очевидноs∈1:h(0 = 0). В противном случае и левая и правая части доказываемогосоотношения равны max xs .s∈1:h826) min [xs ]+ = [min xs ]+ .s∈1:hs∈1:hД о к а з а т е л ь с т в о. Если min xs > 0, то обе части доказываемогоs∈1:hсоотношения равны min xs .
В противном случае утверждение очевидноs∈1:h(0 = 0).7) max[xs + ys ]+ ≤ max[xs ]+ + max[ys ]+ .s∈1:hs∈1:hs∈1:hД о к а з а т е л ь с т в о следует из свойства 2).8) max[xs ]+ − max[ys ]+ ≤ max |xs − ys |.s∈1:hs∈1:hs∈1:hД о к а з а т е л ь с т в о. Воспользоваться отмеченным ранее неравенством[xs ]+ ≤ [ys ]+ + |xs − ys |.9) min [xs ]+ ≤ min [ys ]+ + max |xs − ys |.s∈1:hs∈1:hs∈1:hД о к а з а т е л ь с т в о.
В случае min xs ≤ 0 утверждение в силу свойs∈1:hства 6) очевидно (в левой части стоит ноль). Пусть все xs положительны. Тогда[xs ]+ = xs = ys + (xs − ys ) ≤ [ys ]+ + max |xs − ys |.s∈1:hОтсюда следует, чтоmin [xs ]+ ≤ [ys ]+ + max |xs − ys |s∈1:hs∈1:hи[ys ]+ ≥ min [xs ]+ − max |xs − ys |.s∈1:hs∈1:hВзяв в левой части минимум по s ∈ 1 : h, придём к неравенству, которое равносильно требуемому.10) min [xs ]+ − min [ys ]+ ≤ max |xs − ys |.s∈1:hs∈1:hs∈1:hД о к а з а т е л ь с т в о основано на свойстве 9).8311) При c > 0 справедливо неравенствоmax[c − xs ]+ + min [c + xs ]+ ≥ 2c.s∈1:hs∈1:hРавенство достигается только тогда, когда величина x∗ = min xs приs∈1:hнадлежит отрезку [−c, c].Д о к а з а т е л ь с т в о. Очевидно, что функция [c − x]+ монотонно убывает (не строго), поэтомуmax[c − xs ]+ = [c − x∗ ]+ .s∈1:hАналогично, функция [c + x]+ монотонно возрастает (не строго), поэтомуmin [c + xs ]+ = [c + x∗ ]+ .s∈1:hОстаётся учесть, что[c − x∗ ]+ + [c + x∗ ]+ ≥ 2c,причём равенство достигается только тогда, когда x∗ ∈ [−c, c](см.
рис. B).Рис. B. График функции y = [c − x]+ + [c + x]+84ДОПОЛНЕНИЕ CПроизводные по направлениюC.1. Возьмём конкретную функциюf (v, u) = hv, ui + c,u, v ∈ Rn+1 ,и точку ba ∈ Rn+1 . Составим новые функцииϕ(G)b= max f (g s , ba) и ϕ(G) = ϕ(G)b.+s∈1:hЗдесь G — матрица со строками g 1 , . . . , g h . Нас интересует производнаяфункции ϕ(G) по направлению V , которая обозначается ϕ′ (G, V ) и определяется следующим образом:ϕ(G + tV ) − ϕ(G).t→+0tϕ′ (G, V ) = limОбозначимbR(G)= s ∈ 1 : h | f (g s , ba) = ϕ(G)b.Теорема C.1.
Для производной по направлению ϕ′ (G, V ) справедливаформулаmax hv s , bai,bs∈R(G)′ϕ (G, V ) =max hv s , bai + ,bs∈R(G)0,если ϕ(G)b> 0,если ϕ(G)b= 0,если ϕ(G)b< 0.(C.1)(C.2)(C.3)C.2. Для доказательства этой теоремы нам потребуется одно вспомогательное утверждение.85Лемма.
При фиксированных G и V и малых t > 0 выполняется равенствоmax f (g s + tv s , ba) = max f (g s + tv s , ba).s∈1:hbs∈R(G)Д о к а з а т е л ь с т в о. Достаточно проверить, что в условиях леммыmin f (g s + tv s , ba) > max f (g s + tv s , ba).bs∈R(G)ОбозначимЯсно, что εb > 0. Имеемbs∈/ R(G)(C.4)εb = ϕ(G)b− max f (g s , ba).bs∈/ R(G)f (g s + tv s , ba) − f (g s , ba) = thv s , bai,поэтому при малых t > 0 будет выполнятся неравенство s εbf (g + tv s , b∀s ∈ 1 : h.a) − f (g s , ba) ≤4(C.5)bПри s ∈/ R(G)согласно определению εb и (C.5) получаемf (g s + tv s , ba) = f (g s , ba) + f (g s + tv s , ba) − f (g s , ba) ≤ εb3bεb− ,≤ ϕ(G)b− εb + = ϕ(G)44bв то время как при i ∈ R(G) sεbssf (g + tv , ba) ≥ f (g , ba) + f (g + tv , ba) − f (g , ba) ≥ ϕ(G)b− .4sssНа основании двух последних неравенств приходим к (C.4).Лемма доказана.C.3.
Обратимся к доказательству теоремы. Рассмотрим три случая.1) ϕ(G)b> 0. По непрерывности функции ϕ(G)bи определению плюсико-вой функции при малых t > 0 имеемϕ(G + tV ) = ϕ(Gb + tV ).86В силу леммы"#ϕ(G + tV ) − ϕ(G) 1=max f (g s + tv s , ba) − max f (g s , ba) =bbtt s∈R(G)s∈R(G)1a) − f (g s , ba) = max hv s , bai.(C.6)= max f (g s + tv s , bbbt s∈R(G)s∈R(G)bМы воспользовались тем, что при s ∈ R(G)значения f (g s , ba) равны междусобой.
Из (C.6) следует (C.1) (даже без предельного перехода).2) ϕ(G)b= 0. По лемме и свойству 5) плюсиковой функции (см. Допол-нение B) при малых t > 0 имеемa) + = max f (g s + tv s , ba) + ,max f (g s + tv s , bs∈1:hпоэтомуbs∈R(G)ϕ(G + tV ) = max f (g s + tv s , ba)s∈1:hПо свойству 4) плюсиковой функции+= max f (g s + tv s , ba) + .bs∈R(G)ϕ(G + tV ) − ϕ(G) 1= max f (g s + tv s , ba) + =btt s∈R(G)f (g s + tv s , ba) − f (g s , ba)= max hv s , bai + .= maxbbts∈R(G)s∈R(G)+(C.7)Мы воспользовались тем, что в данном случае ϕ(G) = 0 и f (g s , ba) = 0 приbвсех s ∈ R(G).Из (C.7) следует (C.2) (и опять без предельного перехода).3) ϕ(G)b< 0. По непрерывности при малых t > 0 будет ϕ(Gb + tV ) < 0.Формула (C.3) очевидна, поскольку по определению плюсиковой функциии ϕ(G), и ϕ(G + tV ) при малых t > 0 равны нулю.Теорема доказана.C.4.
Возьмём ещё одну точку b̌ ∈ Rn+1 и рассмотрим функцииψ̌(G) = min f (g s , b̌), ψ(G) = ψ̌(G) + .s∈1:hОбозначимŘ(G) = s ∈ 1 : h | f (g s , b̌) = ψ̌(G) .87Теорема C.2. Для производной по направлению ψ ′ (G, V ) справедливаформулаmin hv s , b̌i,если ψ̌(G) > 0,s∈Ř(G) s′ψ (G, V ) =hv,b̌i, если ψ̌(G) = 0,min+s∈Ř(G)0,если ψ̌(G) < 0.Д о к а з а т е л ь с т в о аналогично доказательству теоремы C.1. Нужновоспользоваться свойствами 4) и 6) плюсиковой функции (см. Дополнение B) и равенствомmin f (g s + tv s , b̌) = min f (g s + tv s , b̌),s∈1:hs∈Ř(G)справедливым при малых t > 0.88ДОПОЛНЕНИЕ DЛемма о сумме минимумовПустьM=kXj=1min p(s, j).s∈1:hjНа рис. D схематично представлено индексное множество, на котором определена функция p(s, j).Рис.
D. Двухиндексное множествоОбозначим через Π множество всех цепочек S = (s1 , s2 , . . . , sk ), гдеsj ∈ 1 : hj при каждом j ∈ 1 : k. Выделим в Π цепочку S ∗ = (s∗1 , s∗2 , . . . , s∗k ),элементы которой удовлетворяют условиямs∗j ∈ 1 : hj ,p(s∗j , j) = min p(s, j).s∈1:hjВведём функциюP (S) =kXp(sj , j).j=1∗Ясно, что M = P (S ).Лемма о сумме минимумов. Справедливо равенствоM = min P (S).S∈Π89(D.1)Д о к а з а т е л ь с т в о. При каждом S ∈ Π имеемP (S) =kXp(sj , j) ≥j=1kXj=1min p(s, j) = M,s∈1:hjтак что P (S) ≥ M при всех S ∈ Π. Вместе с тем, как отмечалось,P (S ∗ ) = M , причём S ∗ ∈ Π. Приходим к равенству (D.1).Перепишем формулу (D.1) в развёрнутом видеkXj=1min p(s, j) = minS∈Πs∈1:hjkXp(sj , j).j=1Таким образом, лемма показывает, как правильно переставлять местамиPзнаки « » и «min».90СПИСОК ЛИТЕРАТУРЫ1.
Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потнциальныхфункций в теории обучения машин. М.: Наука, 1970.2. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука, 1974.3. Гавурин М. К., Малозёмов В. Н. Экстремальные задачи с линейнымиограничениями. Л.: Изд-во ЛГУ, 1984.4. Горелик А. Л., Скрипкин В. А. Методы распознования. 4-е изд.
М.: Высшая школа, 2004.5. Демьянов В. Ф. Идентификация точек двух выпуклых множеств //Вестник СПбГУ. Сер. 1. 2001. Вып. 3 (№ 17), с. 14–20.6. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознования и классификации // Проблемы кибернетики: Вып. 33. М.: Наука,1978. С. 5–68.7. Зубова O. A. Идентификация нескольких множеств в многомерномпространстве // Вестник СПбГУ. Сер. 10.
2007. № 4, c. 17–22.8. Малозёмов В. Н., Чернэуцану Е. К. О математической диагностике(линейная модель) // Семинар «DHA & CAGD». Избранные доклады.17 апреля 2010 г. (http://dha.spb.ru/PDF/LinMod.pdf)9. Малозёмов В. Н., Чернэуцану Е. К. Численный метод строгого hотделения // Семинар «DHA & CAGD». Избранные доклады.
15 октября 2011 г. (http://dha.spb.ru/PDF/hSepNumerical.pdf)9110. Малозёмов В. Н., Чернэуцану Е. К. Наилучшее линейное отделениедвух множеств // Семинар «DHA & CAGD». Избранные доклады. 6 октября 2012 г. (http://dha.spb.ru/PDF/LinSep.pdf)11. Неймарк Ю. И., Баталова З. С. и др. Распознавание образов и медицинская диагностика. М.: Наука, 1972.12. Первозванский А. А. Распознавание абстрактных образов, как задача линейного программирования // Известия АН СССР, Техническаякибернетика.
1965. № 4, с. 41–44.13. Сергеев А. Н., Соловьёва Н. А., Чернэуцану Е. К. Решение задач линейного программирования в среде MATLAB // Семинар «DHA & CAGD».Программные реализации. 12 февраля 2011 г.(http://dha.spb.ru/PDF/MatLabLP.pdf)14. Соловьёва Н. А., Чернэуцану Е. К. Решение задач квадратичного программирования в среде MATLAB // Семинар «DHA & CAGD».
Программные реализации. 12 февраля 2011 г.(http://dha.spb.ru/PDF/MatLabQP.pdf)15. Чернэуцану Е. К. Анализ задачи строгого h-отделения двух множеств. Вестник СПбГУ. Сер. 10. 2012. № 4, c. 85-–91.16. Чернэуцану Е. К. Метод градиентного типа для решения задачи строгого h-отделения // Вестник СПбГУ.
Сер. 10. 2013. № 2,c. 67—75.17. Чернэуцану Е. К., Лебедев Д. М. Кусочно-линейные функции, допускающие минимальное разложение / Процессы управления и устойчи-92вость: Труды 40-й международной научной конференции аспирантов истудентов. Санкт-Петербург, 2009. С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
