close

Вход

Забыли?

вход по аккаунту

?

Анализ задачи строгого h-ОТДЕЛЕНИЯ двух множеств.

код для вставкиСкачать
Сер. 10. 2012. Вып. 4
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
УДК 519.8
Е. К. Чернэуцану
АНАЛИЗ ЗАДАЧИ СТРОГОГО h-ОТДЕЛЕНИЯ ДВУХ МНОЖЕСТВ∗)
1. Пусть в Rn заданы два конечных множества
A = {ai }m
i=1
и B = {bj }kj=1 .
Следуя [1], назовем выпуклую оболочку множества A и множество B строго h-отделимыми, если существует h гиперплоскостей вида
'
(
Hs = x ∈ Rn | ws , x = γs , s ∈ 1 : h, ,
ws = O,
таких, что выполняются неравенства
ws , ai − γs < 0
ws , bj − γs > 0
∀ i ∈ 1 : m, ∀ s ∈ 1 : h;
для каждого j ∈ 1 : k
и некоторого s ∈ 1 : h.
На рис. 1 приведен пример строгого 2-отделения.
w1
w2
Рис. 1. Пример строгого 2-отделения
Поставленную задачу можно формализовать так (см. [1, 2]):
m
k
s
1
1 max w , ai − γs + c + +
min −ws , bj + γs + c + → min .
F (G) :=
G
m i=1 s∈1:h
k j=1 s∈1:h
(1)
Чернэуцану Екатерина Константиновна – аспирант кафедры математической теории моделирования систем управления факультета прикладной математики–процессов управления Санкт-Петербургского государственного университета. Научный руководитель: доктор физико-математических наук,
проф. Л. Н. Полякова. Количество опубликованных работ: 4. Научные направления: выпуклый анализ,
методы оптимизации. E-mail: katerinache@yandex.ru.
∗) Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 12-01-00752-a).
c Е. К. Чернэуцану, 2012
85
Здесь G – матрица размера h × (n + 1) со строками
s ∈ 1 : h;
g s = (ws , γs ),
c > 0 – параметр, [u]+ = max{0, u}. В работе [1] задача (1) исследовалась только
при c = 1. Матрицу G указанных размеров будем называть подходящей, если у нее
все ws отличны от нулевого вектора.
Справедливо следующее утверждение.
Теорема 1. Выпуклая оболочка множества A и множество B строго h-отделимы
тогда и только тогда, когда существует подходящая матрица G∗ , такая, что
F (G∗ ) = 0.
Д о к а з а т е л ь с т в о. Достаточность практически очевидна. Действительно,
пусть F (G∗ ) = 0 для некоторой подходящей матрицы G∗ со строками (w∗s , γs∗ ). Тогда
w∗s , ai − γs∗ −c < 0 при всех i ∈ 1 : m и всех s ∈ 1 : h,
w∗s , bj − γs∗ c > 0 при каждом j ∈ 1 : k и некотором s ∈ 1 : h.
(2)
Эти соотношения и определяют строгую h-отделимость.
Необходимость доказывается по той же схеме, что и в работах [1, 2].
2. В задаче (1) функция F (G) минимизируется по всем матрицам G размера
h × (n + 1). Как показано в [3], задача (1) всегда имеет решение, однако оптимальная матрица, вообще говоря, может не быть подходящей. В этой связи представляет
интерес следующее утверждение (см. [1, 2]).
Теорема 2. Пусть F (G∗ ) = 0. В этом случае
1) у матрицы G∗ не все w∗s равны нулевому вектору;
2) если w∗s = O на множестве
S ⊂ 1 : h, то выпуклая оболочка множества A
и множество B строго h − |S| -отделимы.
3. По определению F (G) 0 на всех матрицах G. Особенность задачи (1) заключается в том, что может существовать подходящая матрица G∗ , которая строго отделяет co(A) от B в смысле (2), но при этом F (G∗ ) > 0.
Пример. Рассмотрим на плоскости R2 множества A и B, содержащие по одной
точке a = (0, 0) и b = (0, 2) соответственно. Речь пойдет, естественно, об 1-отделении.
Положим w1 = (0, 1), а в качестве γ1 возьмем любое число из интервала (0, 2). В этом
случае прямая x2 = γ1 строго отделяет точку a от точки b (рис. 2).
x2
2
b
γ1
0
a
x1
Рис. 2. Строгое 1-отделение
Вместе с тем
F (G) = [−γ1 + c]+ + [−2 + γ1 + c]+ .
На рис. 3 представлен график F (G) как функции от γ1 .
86
F
0
2−c
c
2
γ1
Рис. 3. График F (G) как функции от γ1
Видно, что F (G) достигает своего минимального значения, равного нулю, на парах
(w1 , γ1 ) при γ1 ∈ [c, 2 − c]. При γ1 ∈ (0, c) ∪ (2 − c, 2) пара (w1 , γ1 ) по-прежнему строго
отделяет точку a от точки b, но в этом случае F (G) > 0. Наконец, только при c = 1
условие F (G) = 0 выполняется на единственной паре вида (w1 , γ1 ), у которой γ1 = 1.
4. Как показано в [3], задача (1) сводится к конечному числу задач линейного программирования. Доказательство этого утверждения опирается на лемму о сумме минимумов. Напомним ее формулировку.
Пусть
k
min p(j, s).
M=
j=1
s∈1:hj
На рис. 4 схематично представлено индексное множество, на котором определена функция p(j, s).
j
s
0
Рис. 4. Схематичное представление функции p(j, s)
Обозначим через Π множество всех цепочек S = (s1 , s2 , . . . , sk ), где sj ∈ 1 : hj
при каждом j ∈ 1 : k. Выделим в Π цепочку S ∗ = (s∗1 , s∗2 , . . . , s∗k ), элементы которой
удовлетворяют условиям
s∗j ∈ 1 : hj ,
p(j, s∗j ) = min p(j, s).
s∈1:hj
Введем функцию
P (S) =
k
p(j, sj ).
j=1
Ясно, что M = P (S ∗ ).
87
Лемма (о сумме минимумов). Справедливо равенство
(3)
M = min P (S).
S∈Π
Д о к а з а т е л ь с т в о. При каждом S ∈ Π имеем
P (S) =
k
p(j, sj ) j=1
k
j=1
min p(j, s) = M,
s∈1:hj
т. е. P (S) M при всех S ∈ Π. Вместе с тем, как отмечалось, P (S ∗ ) = M , причем S ∗ ∈
Π. Приходим к равенству (3). Лемма доказана.
Перепишем формулу (3) в развернутом виде
k
j=1
min p(j, s) = min
s∈1:hj
S∈Π
k
p(j, sj ).
j=1
Таким образом, лемма показывает, как правильно переставлять знаки
Теперь задачу (1) можно переписать следующим образом:
inf F (G) = min inf
G
S∈Π G
и min.
m
k
01 3
1 −wsj , bj + γsj + c + ,
max ws , ai − γs + c + +
m i=1 s∈1:h
k j=1
'
(
где Π = S = (s1 , . . . , sk ) | sj ∈ 1 : h, j ∈ 1 : k . Приходим к конечному числу
экстремальных задач вида
m
k
s
1 1 −wsj , bj + γsj + c + → inf ,
max w , ai − γs + c + +
G
m i=1 s∈1:h
k j=1
(4)
соответствующих различным S ∈ Π. В свою очередь, задача (4) эквивалентна задаче
линейного программирования
m
k
1 1
pi +
qj → inf,
m i=1
k j=1
−ai , ws + γs + pi c,
i ∈ 1 : m, s ∈ 1 : h;
bj , w − γsj + qj c,
sj
pi 0,
i ∈ 1 : m;
(5)
qj 0,
j ∈ 1 : k;
j ∈ 1 : k.
Каждая задача вида (5) имеет решение, поскольку множества их планов непусты
и целевые функции ограничены снизу нулем. Отсюда следует, что и задача (1) имеет
значение задачи (5)
решение. Его порождает то S ∗ ∈ Π, при котором экстремальное
принимает наименьшее значение. Обозначим через {w∗s }, {γs∗ }, {p∗i }, {qj∗ } соответствующее решение задачи (5). Тогда матрица G∗ , составленная из строк (w∗s , γs∗ ), s ∈ 1 : h,
является решением задачи (1).
5. Рассмотрим пример строгого отделения двух множеств. Пусть на плоскости заданы множества A и B, состоящие соответственно из точек
a1 = (−2, 0), a2 = (2, 0), a3 = (0, 2), a4 = (0, 1);
88
b1 = (0, 3), b2 = (3, 0), b3 = (−3, 0).
Очевидно, что (A) ∩ B = ∅ (рис. 5).
b1
b3
b2
Рис. 5. Множества A и B
Решим задачу строгой 2-отделимости. В данном случае
n = 2, m = 4, k = 3, h = 2.
Положим c = 1. Выясним, как выглядит задача (5) при S = (1, 1, 2). Выпишем вектор
неизвестных
z = (w11 , w21 , γ1 , w12 , w22 , γ2 , p1 , p2 , p3 , p4 , q1 , q2 , q3 )
и матрицу ограничений
⎡
2
0
1
⎢−2 0
1
⎢
⎢ 0 −2 1
⎢
⎢ 0 −1 1
⎢
⎢
2
⎢
D=⎢
−2
⎢
⎢
0
⎢
⎢
0
⎢
⎢0
3
−1
⎢
⎣3
0 −1
−3
⎤
1
1
1
1
0
0
−2
−1
1
1
1
1
1
1
1
1
1
0
1
−1
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥.
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
1
Задача (5) примет вид
1
1
pi +
qj → inf,
4 i=1
3 j=1
4
3
(6)
Dz e,
pi 0,
i ∈ 1 : 4;
qj 0,
j ∈ 1 : 3.
Решением данной задачи является вектор
z = (111.22, 112.00, 272.91, −78.15, 27.35, 192.16, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00).
89
Минимальное значение целевой функции равно нулю. Строгое 2-отделение множеств A
и B при S = (1, 1, 2) выглядит так, как показано на рис. 6.
b1
b3
b2
Рис. 6. Строгое 2-отделение множеств A и B при S = (1, 1, 2)
Отметим, что задание вектора индексов S = (1, 1, 2) соответствует разбиению множества B на два подмножества {b1 , b2 }∪{b3 }, которые согласованно отделяются от множества A с помощью двух прямых
w1 , x = γ1
и w2 , x = γ2 .
Существуют еще два разбиения множества B на два подмножества:
{b1 , b3 } ∪ {b2 }
и {b2 , b3 } ∪ {b1 }.
Им соответствуют векторы S = (1, 2, 1) и S = (2, 1, 1).
Результат строгого 2-отделения при S = (1, 2, 1) показан на рис. 7.
b1
b3
b2
Рис. 7. Строгое 2-отделение при S = (1, 2, 1)
Этот случай симметричен случаю S = (1, 1, 2).
При S = (2, 1, 1) строгой 2-отделимости нет (рис. 8).
90
b1
b3
b2
Рис. 8. Отделимость при S = (2, 1, 1)
Решением задачи, аналогичной (6), является вектор
z = (0.00, −112.02, −1.00, 0.00, 111.87, 273.78, 2.00, 2.00, 0.00, 0.00, 0.00, 0.00, 0.00).
Минимальное значение целевой функции равно единице.
6. В общем случае задание вектора S ∈ Π соответствует разбиению множества B,
состоящего из k векторов, на h подмножеств. Число таких разбиений и определяет
количество задач линейного программирования вида (5), к решению которых сводится
решение задачи (1).
Если заранее известно, что множества A и B строго h-отделимы, то решение задачи (1) можно упростить. После разбиения множества B на h подмножеств следует
независимо решать задачи линейного отделения каждого из этих подмножеств от множества A (см. [4]). В случае успешного отделения совокупность разделяющих гиперплоскостей образует решение задачи (1).
Литература
1. Astorino A., Gaudioso M. Polyhedral separability througt successive LP // JOTA. 2002. Vol. 112,
N 2. P. 265–293.
2. Малоземов В. Н., Чернэуцану Е. К. Строгая h-отделимость двух множеств // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD): избр. докл.
18 декабря 2010 г. 6 с. (URL: http://dha.spb.ru/reps10.shtml#1218).
3. Чернэуцану Е. К. Строгая h-отделимость и линейное программирование // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD): избр. докл.
29 января 2011 г. 7 с. (URL: http://dha.spb.ru/reps11.shtml#0129).
4. Малоземов В. Н., Чернэуцану Е. К. О математической диагностике (линейная модель) // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD):
избр. докл. 17 апреля 2010 г. 5 с. (URL: http://dha.spb.ru/reps10.shtml#0417).
Статья рекомендована к печати проф. В. Ф. Демьяновым.
Статья принята к печати 21 июня 2012 г.
Документ
Категория
Без категории
Просмотров
5
Размер файла
269 Кб
Теги
анализа, отделения, множества, строгого, задачи, двух
1/--страниц
Пожаловаться на содержимое документа