Диссертация (1149837), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Дополнение D), пока не найдётся цепочка Ŝ = {ŝj }j∈Jν , на которой решение V̂νэкстремальной задачи1 X1 X ŝjQ̂(Gν + V ) :=ϕi (Gν + V ) +f (gν + v ŝj , b̌j ) + → minV ∈Ωmki∈Iνj∈Jνудовлетворяет неравенствуQ̂(Gν + V̂ν ) < F (Gν ) − σ.(5.27)4) В качестве очередного приближения берётся матрицаGν+1 = Gν + t̂ν V̂ν ,где t̂ν — точка минимума функции F (Gν + tV̂ν ) на отрезке [0, 1].З а м е ч а н и е. Если цепочка Ŝ, обеспечивающая неравенство (5.27), отсутствует, то Gν — почти локально оптимальная матрица.55§ 6.Численные эксперименты6.1. В этом параграфе приводятся результаты численных экспериментовпо применению метода градиентного типа (§4) и безградиентного метода(§5) к решению задачи h-отделения двух множеств co(A) и B из Rn , гдеA = {ai }mi=1 ,B = {bj }kj=1 .Общей проблемой обоих методов является выбор начального приближения.Представляется естественным такой подход.В множестве B1 := B берём произвольную точку bj1 и с помощью гиперплоскости H1 = x | hw1 , xi = γ1 линейно отделяем её от co(A).

Далее, вмножестве B2 = bj ∈ B1 | hw1 , bj i < γ1 берём произвольную точку bj2 ис помощью гиперплоскости H2 = x | hw2 , xi = γ2 линейно отделяем еёот co(A). Процесс продолжается до тех пор, пока не будет построена гиперплоскость Hh = x | hwh , xi = γh , линейно отделяющая точку bjh ∈ Bhот co(A). ЗдесьBh = bj ∈ Bh−1 | hwh−1 , bj i < γh−1 .Матрицу G0 со строками (ws , γs ), s = 1, . . . , h, можно взять в качественачального приближения.На самом деле, в описанном процессе на p-м шаге вместо одной точкиbjp ∈ Bp можно брать несколько точек из Bp . Предельный случай выглядит так: множество B разбивается на h непересекающихся подмножеств икаждое подмножество, независимо, линейно отделяется от co(A).566.2.

Рассмотрим конкретный пример. Пусть на плоскости заданы множества A и B, состоящие соответственно из точек (см. рис. 6.1.)a1 = (−3, 0), a2 = (−2, 0), a3 = (−2, −3), a4 = (0, 2), a5 = (0, 1),a6 = (1, 1), a7 = (2, 0), a8 = (2, 4), a9 = (3, 1), a10 = (4, −2);b1 = (−6, 0), b2 = (−3.5, −1), b3 = (−3, 2), b4 = (−3, −3.5),b5 = (−2, −5), b6 = (−1, 5), b7 = (1, 5), b8 = (2, −5),b9 = (3, 8), b10 = (4, −5), b11 = (5, 2), b12 = (6, −2).Рис. 6.1.

Множества A и BДля h-отделения этих множеств при h = 4 воспользуемся сначала методомградиентного типа.Построим начальное приближение. Возьмём точку b6 и линейно отделимеё от множества A (см. § 1). Получим векторg1 = (w1 , γ1 ) = (−0.53, 0.85, 3.27),57определяющий гиперплоскость, линейно отделяющую точку b6 от множества A (см. рис. 6.2).Рис. 6.2. Линейное отделение одной точкиАналогично отделим точки b2 , b8 и b12 . Получим соответственно векторы(см. рис. 6.3)g2 = (w2 , γ2 ) = (−0.98, −018, 3.29),g3 = (w3 , γ3 ) = (0.18, −0.98, 3.99),g4 = (w4 , γ4 ) = (0.99, −0.11, 5.18).58Рис. 6.3.

Линейное отделение четырёх точекТеперь в качестве начального приближения G0 возьмем матрицу со строками g1 , g2 , g3 , g4 , так что (см. рис. 6.4)−0.53 0.85−0.98 −0.18G0 =  0.18 −0.980.99 −0.11593.273.29.3.995.18Рис. 6.4. Начальное приближение G0Будем решать задачу строгого 4-отделения методом градиентного типапри c = 0.5 (см. п. 4.3).Заполним таблицу 7 и таблицу 8.Таблица 7: Вычисление функций ϕi (G0 )i12345678910f (g01 , âi )−1.17−1.71−4.24−1.08−1.93−2.46−3.84−0.99−3.53−6.60f (g02 , âi )0.16−0.82−0.28−3.15−2.97−3.95−4.75−6.46−5.92−6.36f (g03 , âi )−4.04−3.86−0.91−5.46−4.47−4.29−3.12−6.87−3.92−0.79f (g04 , âi )−7.67−6.67−6.35−4.89−4.79−3.79−2.69−2.12−1.80−0.49ϕ̂i (G0 )0.16−0.82−0.28−1.08−1.93−2.46−2.69−0.99−1.80−0.49R̂i (G0 ){2}{2}{2}{1}{1}{1}{4}{1}{4}{4}ϕi (G0 )0.1600000000060Таблица 8: Вычисление функций ψj (G0 )j123456789101112f (g01 , b̌j )0.572.750.485.136.94−0.990.089.07−1.3910.144.758.66f (g02 , b̌j )−2.110.161.190.200.923.705.674.858.186.829.069.33f (g03 , b̌j )5.594.157.011.60−0.059.599.22−0.7911.80−1.165.541.42f (g04 , b̌j )11.659.068.888.297.147.205.223.173.541.180.92−0.49ψ̌j (G0 )−2.110.160.480.20−0.05−0.990.08−0.79−1.39−1.160.92−0.49Řj (G0 ){2}{2}{1}{2}{3}{1}{1}{3}{1}{3}{4}{4}ψj (G0 )00.160.480.20000.080000.920Значение целевой функции F (G0 ) равно 0.17.

Производная по направлению V функции F (G) при G = G0 принимает вид:1 21 21214′hv , b̌2 i + hv , b̌3 i + hv , b̌4 i + hv , b̌7 i + hv , b̌11 i .F (G0 , V ) = hv , â1 i +1012Решаем задачу линейного программированияF ′ (G0 , V ) → min,V ∈Ωгде в качестве Ω возьмём множество (4 × 3)-матриц V , все элементы которых по модулю не превосходят 10 (K = 10). Очевидно, что решением этойзадачи является матрица−10 10 −10−10 −10 −10V0 = ; 00010 10 −10при этом F ′ (G0 , V0 ) = −22.67.Получили направление наискорейшего убывания V0 функции F (G) приG = G0 . Минимум функции F (G0 + tV0 ) на луче t > 0 достигается приt0 = 0.008, поэтому (см. рис. 6.5)−0.61 0.93 3.19−1.06 −0.26 3.21G1 := G0 + t0 V0 = . 0.18 −0.98 3.991.07 −0.02 5.1061Рис.

6.5. Первое приближение G1Повторяем процесс. Заполним таблицу 9 и таблицу 10.Таблица 9: Вычисление функций ϕi (G1 )i12345678910f (g01 , âi )−0.85−1.47−4.24−0.84−1.77−2.38−3.92−0.83−3.61−6.99f (g02 , âi )0.48−0.580.20−3.23−2.97−4.03−4.83−6.94−6.16−6.44f (g03 , âi )−4.04−3.86−0.91−5.46−4.47−4.29−3.12−6.87−3.92−0.79f (g04 , âi )−7.82−6.75−6.67−4.65−4.62−3.55−2.45−1.48−1.40−0.25ϕ̂i (G0 )0.48−0.580.20−0.84−1.77−2.38−2.45−0.83−1.40−0.25R̂i (G0 ){2}{2}{2}{1}{1}{1}{4}{1}{4}{4}ϕi (G0 )0.4800.20000000062Таблица 10: Вычисление функций ψj (G1 )j123456789101112f (g01 , b̌j )0.012.470.0015.097.09−1.54−0.329.55−1.8710.774.909.22f (g02 , b̌j )−2.67−0.271.03−0.390.273.946.074.538.976.669.549.56f (g03 , b̌j )5.594.157.011.60−0.059.599.22−0.7911.80−1.165.541.42f (g04 , b̌j )12.049.338.878.737.626.804.653.322.581.170.28−0.89ψ̌j (G0 )−2.67−0.270.001−0.39−0.05−1.54−0.32−0.79−1.87−1.160.28−0.89Řj (G0 ){2}{2}{1}{2}{3}{1}{1}{3}{1}{3}{4}{4}ψj (G0 )000.00100000000.280Вычисляем F (G1 ) = 0.09.

Производная по направлению V функции F (G)при G = G1 принимает вид1 21 2214′hv , â1 i + hv , â3 i +hv , b̌2 i + hv , b̌3 i + hv , b̌11 i .F (G1 , V ) =1012Решаем задачу линейного программированияF ′ (G1 , V ) → min,V ∈Ωгде в качестве Ω возьмём множество (4 × 3)-матриц V , все элементы которых по модулю не превосходят 10 (K = 10). Очевидно, что решением этойзадачи является матрица−10 10V1 =  010при этом F ′ (G1 , V1 ) = −21.67.10 −1010 10;0010 −10Получили направление наискорейшего убывания V1 функции F (G) приG = G1 . Минимум функции F (G1 + tV1 ) на луче t > 0 достигается приt1 = 0.005, поэтому−0.66 0.98 3.14−1.01 −0.21 3.26G2 := G1 + t1 V1 =  0.18 −0.98 3.991.12 0.02 5.0563и F (G2 ) = 0.02.

Учитывая, что G2 — подходящая матрица, заключаем,что G2 — решение рассматриваемой задачи (см. рис. 6.6).Рис. 6.6. Решение G26.3. Теперь рассмотрим решение данного примера при тех же начальныхусловиях с помощью безградиентного метода (см. §5).Положим c = 0.5, εA = 0.1, εB = 0.1 и σ = 0.0001. Строим начальноеприближение как в п. 6.2.

Получим−0.5333 0.8460 3.2735−0.9837 −0.1801 3.2869G0 =  0.1837 −0.9830 3.99150.9944 −0.1055 5.1832и F (G0 ) = 0.1706.64Формируем индексные множестваI0 = i ∈ 1 : m | max f (gνs , âi ) > −εA ,s∈1:hJ0 = j ∈ 1 : k | min f (gνs , b̌j ) > −εB ,s∈1:hL0j = s ∈ 1 : h | f (gνs , b̌j ) = min f (gνp , b̌j ) ,p∈1:hj ∈ Jν .Имеем (см. таблицу 7 и таблицу 8)I0 = {1},J0 = {2, 3, 4, 5, 7, 11},L02 = {2}, L03 = {1}, L04 = {2}, L05 = {3}, L07 = {1}, L011 = {4}.Решаем задачу линейного программирования вида (5.19).

Запишем вектор неизвестныхz = ξ1 , η2 , η3 , η4 , η5 , η7 , η11 , v 1 (1), v 1 (2), v 1 (3),v 2 (1), v 2 (2), v 2 (3), v 3 (1), v 3 (2), v 3 (3), v 4 (1), v 4 (2), v 4 (3) ,матрицу ограничений1111 1D=11113 0 13 0 13 0 1-3.5 -1 -1-3 2 -1-3 -3.5 -1-2 -5 -11 5 -115 2 -1301и вектор правой части ограниченийb = −1.1736, 0.1642, −4.0426, −7.6664,0.1638, 0.4816, 0.2054, −0.0561, 0.0768, 0.9222 .65Тогда задача линейного программирования (5.19) примет вид110 ξ1+112 (η2+ η3 + η4 + η5 + η7 + η11 ) → min,Dz ≥ b,ξi ≥ 0,i ∈ I0 ;ηj ≥ 0,−10 ≤ v s (α) ≤ 10,j ∈ J0 ;α ∈ 1 : 3, s ∈ 1 : 4.Решением этой задачи является матрица0.0012 0.0070 −0.00310.0025 −0.0071 0.0006V0 = ,0.0053 −0.0066 0.00090.0050 0.0037 −0.0040при этом выполняется неравенство (см. п. 5.5)Q̂(G0 + V0 ) < F (G0 ) − σ,где Q̂(G0 + V0 ) = 0.1698 и σ = 0.0001.В качестве очередного приближения берём матрицу (см.

рис. 6.7)−0.5101 0.9859 3.2113−0.9340 −0.3225 3.2988G1 := G0 + t0 V0 = , 0.2892 −1.1150 4.00991.0952 −0.0314 5.1041где t0 = 30 — точка минимума функции F (G0 + tV0 ) при t0 > 0. Значениецелевой функции F (G1 ) равно 0.0546.66Рис. 6.7. Первое приближение G1Повторяем процесс. Формируем индексные множестваI1 = {1, 3},J1 = {2, 3, 11},L12 = {2}, L13 = {1}, L111 = {4}.Решаем задачу линейного программирования вида (5.19).

Характеристики

Список файлов диссертации