Диссертация (1149837), страница 5
Текст из файла (страница 5)
Переходим к вычислению производных понаправлению. Имеемϕ′i (G1 , V ) ≡ 0 при i = 1, 4;ϕ′2 (G1 , V ) = maxhv s , â2 i;s∈1:2ϕ′3 (G1 , V ) = hv 1 , â3 i + ;ψj′ (G1 , V ) ≡ 0 при j = 1, 2, 3;ψ4′ (G1 , V ) = hv 3 , b̌4 i + .Производная по направлению V функции F (G) при G = G1 принимаетвид′F (G1 , V ) =14ns1maxhv , â2 i + hv , â3 is∈1:243+3+ hv , b̌4 i o+.Задача (4.4) при K = 10 сводится к задаче линейного программирования14при ограниченияхt1 + t2 + t3 → min s v (α) ≤ 10,α ∈ 1 : 3, s ∈ 1 : 3;t1 ≥ hv 1 , â2 i,t1 ≥ hv 2 , â2 i,t2 ≥ hv 1 , â3 i,t3 ≥ hv 3 , b̌4 i,t2 ≥ 0,t3 ≥ 0.Для решения последней задачи использовалась программа из MATLAB [13].Получили матрицу−10 −1010V1 = −10 −1010 ;−5.43 −7.1 −5.43при этом F ′ (G1 , V1 ) = −12.5. Минимум функции F (G1 + tV1 ) на луче t > 0достигается при t1 = 0.01, поэтому1.40.4 2.6G2 := G1 + t1 V1 = −0.61.4 3.6 ,−0.55 −1.57 3.45и F (G2 ) = 0.
Учитывая, что G2 — подходящая матрица, заключаем, что G2 —решение рассматриваемой задачи (см. рис. 4.4).4.5. Выбор параметра c = 0 не соответствует теории (по теории нужнобрать c > 0). При c = 0 очевидным решением задачи (3.1) является матрица G = O. Однако решение неединственно. Мы начинали вычисленияс подходящей матрицы G0 и пришли к подходящей матрице G2 , котораяреализует h-отделение, правда, нестрогое.Теперь вместо c = 0 положим c = 21 .
В качестве начального приближениявозьмём ту же матрицу G0 . Заполним таблицу 5 и таблицу 6.44Рис. 4.4. Матрица G2 — решение задачи при c = 0Таблица 5: Вычисление функций ϕi (G0 )i1234f (g01 , âi )−5.5−1.5−0.5−2.5f (g02 , âi )−3.5−0.5−4.5−2.5f (g03 , âi )−3.5−6.5−2.5−4.5ϕ̂i (G0 )−3.5−0.5−0.5−2.5R̂i (G0 ){2, 3}{2}{1}{1, 2}ϕi (G0 )0000Таблица 6: Вычисление функций ψj (G0 )j1234f (g01 , b̌j )5.51.5−0.54.5f (g02 , b̌j )2.51.53.56.5f (g03 , b̌j )6.57.55.52.5ψ̌j (G0 )2.51.5−0.52.5Řj (G0 ){2}{1, 2}{1}{3}ψj (G0 )2.51.502.5По последним строкам таблицы 5 и таблицы 6 находим значение целевойфункции: F (G0 ) = 1.625. Далее имеем1.5 0.5 2.5G1 = −0.5 1.5 3.5.−0.5 −1.5 3.5Непосредственно проверяется, что F (G1 ) = 0.5.
(см. рис. 4.5).45Рис. 4.5. Подходящая матрица G1Повторяем процесс, и на следующем шаге получаем матрицу1.2 0.3 2.8G2 = −0.8 1.2 3.5;−0.8 −1.8 3.2при этом F (G2 ) = 0 (см. рис. 4.6). Значит, подходящая матрица G2 осуществляет строгое 3-отделение.Рис. 4.6. Матрица G2 — решение задачи при c =4612§ 5.Безградиентный метод локального поиска5.1. Рассмотрим ещё один, безградиентный, метод решения задачи (4.1),максимально учитывающий её специфику. Описание метода потребует некоторой подготовки.В пространстве Rn+1 будем использовать равномерную норму векторов,kvk = max v(α),α∈1:n+1и согласованную с ней норму матриц G,n+1X s g (α).kGk = maxs∈1:hα=1Очевидно, что для любой строки g s матрицы G и любого вектора v ∈ Rn+1выполняется неравенство shg , vi ≤ kGk · kvk,s ∈ 1 : h.(5.1)Возьмём два параметра точности εA > 0 и εB > 0.
С каждой матрицей Gсвяжем индексные множества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:hПоложимε = min{εA /CA , εB /CB },гдеCA = max kâi k,CB = max kb̌j k.i∈1:mj∈1:kЛемма 5.1. Для любой матрицы G выполняется равенство1 X1XF (G + V ) =ϕi (G + V ) +ψj (G + V )mki∈Ij∈Jпри условии, что kV k ≤ ε.47(5.2)Д о к а з а т е л ь с т в о. Нужно проверить, что при указанных Vϕi (G + V ) = 0, если i ∈/ I;ψj (G + V ) = 0, если j ∈/ J.(5.3)По определению функции f имеемf (g s + v s , âi ) = f (g s , âi ) + hv s , âi i.Далее (см.
Дополнение B, свойство 5))hiss.ϕi (G + V ) = max f (g , âi ) + hv , âi is∈1:h+(5.4)По определению множества I при i ∈/ I и s ∈ 1 : h выполняется неравенствоf (g s , âi ) ≤ −εA ,поэтому согласно (5.1) при всех s ∈ 1 : hf (g s , âi ) + hv s , âi i ≤ −εA + kV kCA ≤ 0.На основании (5.4) и определения плюсиковой функции получаем первоеравенство из (5.3).Аналогично (см. Дополнение B, свойство 6))hiss.ψj (G + V ) = min f (g , b̌j ) + hv , b̌j is∈1:h+(5.5)При j ∈/ J существует индекс s ∈ 1 : h, на которомf (g s , b̌j ) ≤ −εB .На том же индексе s имеемf (g s , b̌j ) + hv s , b̌j i ≤ −εB + kV kCB ≤ 0.Отсюда и из (5.5) следует второе равенство из (5.3).Лемма доказана.Отметим, что в формулировке леммы 5.1 окрестность kV k ≤ ε одинаковадля всех матриц G.485.2.
Обозначимlj = min f (g s , b̌j ).s∈1:hС матрицей G свяжем индексные множестваLj = s ∈ 1 : h | f (g s , b̌j ) = lj ,j ∈ J.Они соответствуют множествам Řj (G), введённым в п. 4.2, Lj = Řj (G).Имеемmin f (g s , b̌j ) + = min f (g s , b̌j ) + = [lj ]+ =s∈Ljs∈Lj= min f (g s , b̌j ) + = min f (g s , b̌j ) + = ψj (G).s∈1:hs∈1:hПоложив в (5.2) V = O, получимF (G) =1X1 Xϕi (G) +min f (g s , b̌j ) + .mks∈Řj (G)i∈Ii∈JЛемма 5.2. Для каждой матрицы G найдётся такое число εG ∈ (0, ε],чтоF (G + V ) =1X1 Xϕi (G + V ) +min f (g s + v s , b̌j ) +mks∈Řj (G)i∈Ij∈Jпри условии, что kV k ≤ εG .Д о к а з а т е л ь с т в о. В силу леммы 5.1 достаточно проверить, что приj ∈ J и малых kV kmin f (g s + v s , b̌j ) = min f (g s + v s , b̌j ).s∈Ljs∈1:hПустьmin f (g s , b̌j ) = lj + ∆j ,s∈L/ jгде ∆j > 0.
Положимj ∈ J,∆ εG = min ε, min 3CjB .j∈J49(5.6)При kV k ≤ εG и s ∈/ Lj имеемf (g s + v s , b̌j ) = f (g s , b̌j ) + hv s , b̌j i ≥ lj + ∆j − kV kCB ≥ lj + 23 ∆j . (5.7)В то же время при тех же V и s ∈ Ljf (g s + v s , b̌j ) = lj + hv s , b̌j i ≤ lj + 13 ∆j .(5.8)На основании (5.7) и (5.8) заключаем, что при kV k ≤ εG выполняетсяравенство (5.6).Лемма доказана.5.3. Зафиксируем матрицу G0 со строками g0s , s ∈ 1 : h, константу K > εи рассмотрим экстремальную задачу1X1 Xϕi (G0 + V ) +min0 f (g0s + v s , b̌j ) + → min, (5.9)Q(G0 + V ) :=V ∈Ωmks∈Lji∈I0j∈J0где индексные множества I0 , J0 и L0j соответсвуют матрице G0 .
Множествопланов Ω определим так: s v (α) ≤ K,α ∈ 1 : n + 1, s ∈ 1 : h.В частности, матрица V , у которой kV k ≤ K, является планом задачи (5.9).Действительно,n+1n+1XX s s v (p) ≤ maxv (p) = kV k ≤ K.kv (α)k ≤sp=1s∈1:hp=1Отметим, что по лемме 5.2Q(G0 + V ) = F (G0 + V ), если kV k ≤ εG0 .(5.10)Вместе с тем, L0j ⊂ 1 : h, поэтомуψj (G0 + V ) ≤ min0 f (g0s + v s , b̌j ) + .s∈LjОтсюда и из леммы 5.1 следует, чтоF (G0 + V ) ≤ Q(G0 + V ), если kV k ≤ ε.50(5.11)Обозначим через Q0 минимальное значение целевой функции в задаче (5.9). Согласно (5.10)Q0 ≤ Q(G0 ) = F (G0 ).(5.12)Теорема 5.1.
При выполнении условияQ0 = F (G0 )(5.13)матрица G0 является точкой локального минимума функции F (G) вида (4.1).Д о к а з а т е л ь с т в о. На основании (5.10), условия ε < K и равенства(5.13) при kV k ≤ εG0 имеемF (G0 + V ) = Q(G0 + V ) ≥ Q0 = F (G0 ).Это и означает, что G0 — точка локального минимума функции F (G).5.4. Если матрица G0 не является точкой локального минимума функции F (G), то согласно (5.12) выполняется неравенство F (G0 ) > Q0 .
Насамом деле, мы ориентируемся на приближённые вычисления, поэтому будем считать, чтоF (G0 ) − Q0 > σ,где σ — наперёд заданный положительный параметр точности. Последнеенеравенство перепишем в видеQ0 < F (G0 ) − σ.(5.14)Матрице G0 сопоставим совокупность индексных множеств S = {sj }j∈J0 ,где sj ∈ L0j . Эту совокупность обозначим Π0 . По лемме о сумме минимумов(см. Дополнение D и п. 3.2) величина Q0 допускает представлениеn1 X o1 X sjsjϕi (G0 + V ) +f (g0 + v , b̌j ) + .Q0 = min minS∈Π0 V ∈Ω mki∈I0j∈J051(5.15)На основании (5.14) и (5.15) можно утверждать, что существует индексноемножество Ŝ = {ŝj }j∈J0 из Π0 , такое, чтоn1 X o1 X ŝjŝjϕi (G0 + V ) +f (g0 + v , b̌j ) + < F (G0 ) − σ.minV ∈Ω mki∈I0(5.16)j∈J0Рассмотрим вспомогательную задачу1 X1 X ŝjQ̂(G0 + V ) :=ϕi (G0 + V ) +f (g0 + v ŝj , b̌j ) + → min .
(5.17)V ∈Ωmki∈I0j∈J0Ясно, что Q̂(G0 + V ) ≥ Q(G0 + V ) при любых V . Важным моментом является то, что в силу определения множеств L0j справедливы равенстваQ̂(G0 ) = Q(G0 ) = F (G0 ).(5.18)Задача (5.17) эквивалентна задаче линейного программирования1X1 Xξi +ηj → min,mki∈I0(5.19)j∈J0ξi − hv s , âi i ≥ f (g0s , âi ),i ∈ I0 , s ∈ 1 : h;ŝηj − hv ŝj , b̌j i ≥ f (g0j , b̌j ), j ∈ J0 ;ξi ≥ 0,i ∈ I0 ;−K ≤ v s (α) ≤ K,ηj ≥ 0,j ∈ J0 ;α ∈ 1 : n + 1, s ∈ 1 : h.Эта задача имеет решение, поскольку множество её планов непусто и целевая функция ограничена снизу нулём.
По эквивалентности задача (5.17)также имеет решение. Обозначим его V̂ . Положим Ĝ = G0 + V̂ . Согласно (5.16), Q̂(Ĝ) < F (G0 ) − σ. С учётом (5.18) получаемQ̂(Ĝ) − Q̂(G0 ) < −σ.(5.20)Матрицу V̂ мы воспринимаем как направление спуска. Разберёмся с шагом спуска. Положим52t̂ =1,если kV̂ k ≤ ε,ε/kV̂ k, если kV̂ k > ε,и введём матрицу G1 = G0 + t̂ V̂ . Очевидно, что t̂ ∈ (0, 1]. Более того,t̂ ≥ε.(n + 1)K(5.21)Действительно, при kV̂ k ≤ ε неравенство (5.21) очевидно (посколькуε < K). Пусть kV̂ k > ε. По условию, V̂ ∈ Ω, поэтомуn+1X s v̂ (α) ≤ (n + 1)K.kV̂ k = maxs∈1:hα=1Отсюда и из определения t̂ следует (5.21).Имеем kt̂ V̂ k ≤ ε. Согласно (5.11)F (G1 ) ≤ Q(G1 ).(5.22)ДалееПокажем, чтоQ(G1 ) ≤ Q̂(G1 ) = Q̂ G0 + t̂(Ĝ − G0 ) .Q̂ G0 + t̂(Ĝ − G0 ) ≤ Q̂(G0 ) + t̂ Q̂(Ĝ) − Q̂(G0 ) .(5.23)(5.24)Воспользуемся соотношениямиf g0s + t̂(ĝ s − g0s ), u = f t̂ ĝ s + (1 − t̂ )g0s , u == t̂ f (ĝ s , u) + (1 − t̂ )f (g0s , u),из которых следует, что (см.
Дополнение B, свойства 2) и 4))hisssf g0 + t̂(ĝ − g0 ), u≤ t̂ f (ĝ s , u) + + (1 − t̂ ) f (g0s , u) + .+(5.25)Подставив в (5.25) âi и b̌j вместо u и применив операции взятия максимумаи суммирования, придём к неравенствуQ̂ G0 + t̂(Ĝ − G0 ) ≤ t̂ Q̂(Ĝ) + (1 − t̂ )Q̂(G0 ),53равносильному (5.24). По существу, установлена выпуклость функции Q̂(G)вида1 X ŝj1 Xϕi (G) +f (g , b̌j ) + .Q̂(G) =mki∈I0j∈J0На основании (5.22), (5.23), (5.24), (5.18), (5.20) и (5.21) получаемF (G1 ) ≤ Q(G1 ) ≤ Q̂(G0 ) + t̂ Q̂(Ĝ) − Q̂(G0 ) ≤εσ≤ F (G0 ) − t̂σ ≤ F (G0 ) −.(n + 1)KЗначит,F (G0 ) − F (G1 ) ≥εσ.(n + 1)K(5.26)Отметим, что неравенство (5.26) сохранится, если вместо t̂ взять точкуминимума функции F (G0 + tV̂ ) на отрезке [0, 1].К матрице G1 можно применить те же рассуждения, что и к матрице G0 .Ввести индексные множества I1 , J1 , L1j , функцию Q(G1 + V ) с минимальным на Ω значением Q1 .
ЕслиF (G1 ) − Q1 ≤ σ,то G1 — по определению почти локально оптимальная матрица. Вычисления прекращаются. В противном случае с помощью функции Q̂(G1 + V )строим новую матрицу G2 , такую, чтоF (G1 ) − F (G2 ) ≥εσ.(n + 1)KДалее процесс повторяется. Строится последовательность матриц {Gν },для которойF (Gν ) − F (Gν+1 ) ≥εσ.(n + 1)KВ силу неотрицательности F (G) описанный процесс конечен. Через конечное число шагов получим почти локально оптимальную матрицу G∗ .545.5. Опишем общий шаг вычислительного процесса. В нём используютсяглобальные параметры εA , εB и σ.Пусть имеется ν-е приближение — матрица Gν со строками gνs , s ∈ 1 : h.Для получения очередного приближения Gν+1 выполняются следующиеоперации:1) Вычисляется значение 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 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
