Диссертация (Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР), страница 7
Описание файла
Файл "Диссертация" внутри архива находится в папке "Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР". PDF-файл из архива "Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 7 страницы из PDF
Знаk−1Pчит, x =xk ak ∈ cone a1 , . . . , ak−1 , что противоречит выбору k. Поэтомуi=1предположение неверно, и λ1 (x) = αk = λ2 (x).То, что ∀x ∈ Rm ⇒ λ1 (x) = λ2 (x), и означает, что определения 2.5 и 2.6эквивалентны.Наконец, определение чёткой конической оболочки можно непосредственно обобщить на нечёткий случай.Определение 2.7 [4]. Нечёткая коническая оболочка конечного числавекторов a1 , . . . , aq ∈ Rm со степенями уверенности α1 , . . . , αq ∈ [0; 1] — минимальный по включению выпуклый нечёткий конус с такой функцией принадлежности λ(x), что ∀k = 1, q ⇒ λ ak > αk , и λ(0) = 1.Утверждение 2.3.
Определения 2.5 и 2.7 эквивалентны.Доказательство. Пусть µ(x) — функция принадлежности в соответствии с определением 2.5, а λ(x) — с определением 2.7.38Так как µ(x) по утверждению 2.1 задаёт нечёткий выпуклый конус, причём ∀k = 1, q ⇒ µ ak > αk и µ(0) = 1, из определения 2.7 следует ∀x ∈Rm ⇒ λ(x) 6 µ(x).Если x ∈ Rm : µ(x) = 0, то и λ(x) = 0.
Для нулевого вектора λ(0) =µ(0) = 1.Рассмотрим случай x ∈ Rm \{0} : µ(x) > 0. Возьмём представление x скоэффициентами из Optrepµ x:x=qXγk ak .k=1В силу выпуклостиµ(x) =mink=1,q : γk 6=0αk 6mink=1,q : γk 6=0λ ak 6 λ(x).Таким образом, ∀x ∈ Rm ⇒ λ(x) = µ(x).В заключение точно так же перенесём ещё одно определение.Определение 2.8. Конечнопорожденный нечёткий конус — нечёткий конус, представимый в виде нечёткой конической оболочки конечного числавекторов.2.3Нечёткие двойственные конусыПерейдём теперь к рассмотрению двойственности конусов в нечётком случае.
Для начала дадим определение.Определение 2.9 [4]. Двойственный нечёткий конус к нечёткому множеству с функцией принадлежности λ(x) — нечёткое множество с функциейпринадлежностиµ(x) =inf(1 − λ(y)).my∈R : xy<0Отметим, что инфимум по пустому множеству считается равным 1, поэтому µ(0) = 1.Утверждение 2.4 [4]. Определение 2.9 корректно в том смысле, чтонечёткий двойственный конус — действительно нечёткий конус, причём всегда выпуклый и замкнутый.39Доказательство. В обозначениях определения 2.9 ∀α > 0, ∀x ∈ Rmµ(αx) =infy∈Rm : αxy<0(1 − λ(y)) =infy∈Rm : xy<0(1 − λ(y)) = µ(x),что доказывает корректность.Для доказательства выпуклости заметим, что для ∀x, y ∈ Rm , ∀α ∈ (0; 1)µ(αx + (1 − α)y) =infz∈Rm : (αx+(1−α)y)z<0> mininfz∈Rm : xz<0(1 − λ(z));infz∈Rm : yz<0(1 − λ(z)) >(1 − λ(z)) = min {µ(x); µ(y)},так как из (αx + (1 − α)y)z < 0 следует либо xz < 0, либо yz < 0.Обозначим функцию принадлежности замыкания нечёткого двойственного конуса за ψ.
Возьмём произвольный вектор x ∈ Rm и рассмотрим ψ(x) =sup α ∈ [0; 1] x ∈ cl {z ∈ Rm |µ(z) > α} . Предположим, что ψ(x) > µ(x).Взяв в качестве ε = ψ(x) − µ(x), по определению супремума получим, что∃α ∈ (µ(x); ψ(x)) : x ∈ cl {z ∈ Rm |µ(z) > α}. Это означает, что ∃{zn }∞n=1 →x : ∀n ∈ N ⇒ µ(zn ) > α. По определению 2.9 для каждого натурального nимеем α 6inf(1 − λ(y)), откуда α 6 1 − λ(y) для ∀y ∈ Rm : yzn < 0.my∈R : yzn <0Рассмотрим y ∈ Rm : xy < 0. Очевидно, что в силу zn → x, начиная с некоторого номера, yzn < 0.
А тогда α 6 1 − λ(y), и в силу произвольности выбораy справедливо α 6inf(1 − λ(y)) = µ(x), что противоречит выбору α.my∈R : xy<0Это означает, что нечёткий двойственный конус не может не быть замкнутым.Установим некоторые свойства двойственных нечётких конусов.Утверждение 2.5 [4]. Если нечёткие множества с функциями принадлежностей ϕ1 и ϕ2 связаны отношением включения, то есть, например,∀x ∈ Rm ⇒ ϕ1 (x) > ϕ2 (x), то для их двойственных конусов с функциямипринадлежности соответственно ψ1 и ψ2 справедливо встречное включение:∀x ∈ Rm ⇒ ψ1 (x) 6 ψ2 (x).Доказательство.ψ1 (x) =infy∈Rm : xy<0(1 − ϕ1 (y)) 6по определению.infy∈Rm : xy<0(1 − ϕ2 (y)) = ψ2 (x)40Прежде чем доказать свойство взаимодвойственности, рассмотрим вспомогательное утверждение.Утверждение 2.6.
∀x ∈ Rm : x 6∈ cone a1 , . . . , ap ⇒ ∃n ∈ Rm : na1 >0, . . . , nap > 0, nx < 0.Доказательство. Рассмотримinf1y∈cone {a ,...,ap }(y − x)2 .pПри y 2 > 4x2 имеем (y − x)2 = y 2 − 2xy + x2 > y 2 − 2 x2 y 2 + x2 >√√4x2 − 2 x2 · 4x2 + x2 = x2 = (0 − x)2 , так как функция f (t) = t − 2 atpс производной f 0 (t) = 1 − at имеет минимум при t = a, т. е. в нашем случаепри y 2 = x2 , а затем возрастает. Поэтомуinf1y∈cone {a ,...,ap }(y − x)2 =inf p1y∈cone {a ,...,a } : y 2 64x2(y−x).2На замкнутом ограниченном множестве непрерывная функция достигает своего минимального значения.
Пустьz ∈ cone a1 , . . . , ap : (z − x)2 =inf1y∈cone {a,...,ap }(y − x)2 .(2.2)Обозначим n = z − x.Предположим, что nz 6= 0. Тогда z 6= 0, и можно рассмотреть векторy = xz2 z.z(x − y)2 − (x − z)2 = −2xy + y 2 + 2xz − z 2 =xz(xz)2 2(xz)22= −2 2 xz + 4 z + 2xz − z = − 2 + 2xz − z 2 =zzz2z 2 − xz(xz)2 − 2(xz)z 2 + z 4=−==−z2z2(z(z − x))2(nz)2=−= − 2 < 0.z2z 1Если y ∈ cone a , .
. . , ap , то это противоречит тому, что на z достигаетсяинфимум. Значит, xz < 0. Но тогда (x − z)2 = x2 − 2xz + z 2 > x2 = (0 − x)2 ,что снова противоречит (2.2). Следовательно, предположение неверно, и nz =0. Тогда z 2 = (n + x)z = xz.41Отметим, что если xz = 0, то z = 0, а тогда n = −x, и nx = −x2 < 0.Предположим, что ∃u ∈ cone a1 , . . . , ap : nu < 0. Если xz = 0, то ∀α >0 ⇒ x(z + αu) = αxu = −αnu > 0.
Если xz > 0, а xu > 0, то ∀α > 0i ⇒xz ⇒x(z + αu) > xz > 0. Наконец, если xz > 0 и xu < 0, то ∀α ∈ 0; −xuxz (−xu) = 0. Далее, в силу nu < 0 векторx(z + αu) = xz − α(−xu) > xz − −xur2u 6= 0, и если z = 0, z + αu 6= 0. Если z 6= 0, то при 0 < α < z 2 получаемu22 2z + αur 6= 0, так как предположение z + αu = 0 ведёт к z = −αu, z = α u ,2α = z 2 . Таким образом, для достаточно малых положительных α векторu 1x(z + αu)p(z+αu)существуетипринадлежитconea,...,a, и поэтому(z + αu)206x(z + αu)(z + αu) − x(z + αu)22− (z − x)2 =(x(z + αu))2 2(x(z + αu))2− z 2 + 2zx ==2 −2(z + αu)(z + αu)(xz + αxu)2(xz)2 + 2α(xz)(xu) + α2 (xu)2222=−− z + 2z = z −=(z + αu)2(z + αu)2z 4 + z 2 · 2αuz + α2 z 2 u2 − z 4 − 2αz 2 (xu) − α2 (xu)2==(z + αu)22222 22αz (uz − ux) + α z u − (ux)==(z + αu)2α222 2.=2z (nu) + α z u − (ux)(z + αu)2Так как α > 0,22 222z (nu) + α z u − (ux)> 0.(2.3)Если z 2 u2 = (ux)2 , то z 6= 0, так как при z = 0 получаем ux = 0 иnu0, что противоречит выбору u.
Значит, z 6= 0, и 2z 2 (nu) + = −xu = α z 2 u2 − (ux)2 = 2z 2 (nu) < 0, что противоречит (2.3). Если z 2 u2 < (ux)2 ,2222 22 2то 2z (nu) + α z u − (ux) 6 α z u − (ux) < 0, что снова противоре2z 2 (−nu)чит (2.3). Наконец, если z u > (ux) , то z =6 0, и при 0 < α < 2 2z u − (ux)22 224222 22получаем 2z (nu) + α z u − (ux)< 2z 2 (nu) + 2z 2 (−nu) = 0, что снова противоречит (2.3) для достаточно малых α > 0. Таким образом, ∀u ∈cone a1 , . .
. , ap ⇒ nu > 0. В частности, na1 > 0, . . . , nap > 0.0 6 n2 = (z − x)2 = z 2 − 2xz + x2 = x2 − z 2 = x2 − xz = x(x − z) = −nx.Отсюда nx 6 0. Предположим, что nx = 0. Тогда n = 0 и z = x, чтоневозможно, так как z ∈ cone a1 , . . . , ap , а x 6∈ cone a1 , . . . , ap . Значит,nx < 0.Теперь можно показать свойство взаимодвойственности конечнопорожденных нечётких конусов.Утверждение 2.7. Нечёткий конус, который двойственен к двойственному к нечёткому конечнопорожденному конусу, совпадает с этим конусом.Доказательство. Пусть λ(x) — функция принадлежности некоторогонечёткого конечнопорожденного конуса.
Пусть µ(x) — функция принадлежности двойственного к нему конуса. Пусть ν(x) — функция принадлежностиконуса, двойственного к µ.Из определения 2.9 следует, что ∀x, y ∈ Rm : xy < 0 ⇒ µ(x) 6 1 − λ(y).Отсюда λ(y) 6 1 − µ(x). Переходя к инфимуму, получаем∀y ∈ Rm ⇒ λ(y) 6infx∈Rm : xy<0(1 − µ(x)) = ν(y).Пусть конус λ(x) порождён векторами a1 , . . .
, aq ∈ Rm со степенями уверенности α1 , . . . , αq , причём, не умаляя общности, 1 = α0 > α1 > α2 > . . . >αq > 0. По определению 2.6∀y ∈ Rm ⇒ λ(y) =maxk=0,q :αk .y∈cone {a1 ,...,ak }Тогда λ(y) принимает одно из значений α0 , . . . , αq , 0. Следовательно, в µ(x)при x 6= 0 выражение под инфимумом в определении 2.9 принимает лишьконечное число значений, а значит, инфимум достигается и равен одному изчисел 1 − α0 , .
. . , 1 − αq , 1. Аналогично получаем, что ν(y) может приниматьлишь значения α0 , . . . , αq , 0, в том числе и при y = 0.Предположим, что ∃u ∈ Rm : λ(u) < ν(u). Тогда ν(u) > 0, и следовательно, ∃p = 0, q : ν(u) = αp . Возьмём наибольшее из таких p. Так как λ(u) < αp ,u 6∈ cone a1 , . . . , ap .
По утверждению 2.6 ∃n ∈ Rm : na1 > 0, . . . , nap >430, nu < 0. Тогда ∀x ∈ cone a1 , . . . , ap ⇒ nx > 0.µ(n) =infx∈Rm :nx<0=(1 − λ(x)) =infminfx∈Rm :nx<01−maxk=0,q :minx∈R : nx<0 k=p+1,q : x∈cone {a1 ,...,ak }αk=x∈cone {a1 ,...,ak }1 − αk .Если p = q, то минимум берётся по пустому множеству, и µ(n) = 1 > 1 − αp .Если p < q, то ∀k = p + 1, q ⇒ αp > αk ⇒ 1−αk > 1−αp ⇒ µ(n) > 1−αp . Таккак nu < 0, то ν(u) 6 1 − µ(n) < αp .
Полученное противоречие показывает,что ∀u ∈ Rm ⇒ λ(u) = ν(u), и значит, эти конусы совпадают.Следующее утверждение пригодится при рассмотрении вопроса о существенности образующих нечёткого конуса.Утверждение 2.8. Если нечёткие конечнопорожденные конусы с функциями принадлежностей ϕ и ψ взаимодвойственны, то каким бы ни был ненулевой вектор z, существует образующая конуса с функцией принадлежностиϕ, на которой достигается инфимум для ψ(z) в определении 2.9.Доказательство. Обозначим образующие нечёткого конуса с функциейпринадлежности ϕ за g 1 , .