Аналитическое выражение двойственной оценки для задачи размещения точек в шаре
Получено аналитическое выражение для двойственной оценки оптимального значения целевой функции квадратичной постановки задачи размещения точек в шаре. Этот результат справедлив также для оценки, получаемой в результате применения к данной постановке задачи SDP-релаксации. Отримано аналітичний вираз...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/111506 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Аналитическое выражение двойственной оценки для задачи размещения точек в шаре / О.А. Березовский, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 24-31. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-111506 |
|---|---|
| record_format |
dspace |
| spelling |
Березовский, О.А. Шулинок, Г.А. 2017-01-10T14:55:02Z 2017-01-10T14:55:02Z 2014 Аналитическое выражение двойственной оценки для задачи размещения точек в шаре / О.А. Березовский, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 24-31. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/111506 519.8 Получено аналитическое выражение для двойственной оценки оптимального значения целевой функции квадратичной постановки задачи размещения точек в шаре. Этот результат справедлив также для оценки, получаемой в результате применения к данной постановке задачи SDP-релаксации. Отримано аналітичний вираз для двоїстої оцінки оптимального значення цільової функції квадратичної постановки задачі розміщення точок у кулі. Цей результат справедливий також для оцінки, що отримується в результаті застосування до даної постановки задачі SDP-релаксації. We obtain the analytical expression for the dual bound of the optimal value for the quadratic formulation of the point-packing problem in the ball. This result is valid also for the bounds, obtained by invoking SDP-relaxation to this formulation of the problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Аналитическое выражение двойственной оценки для задачи размещения точек в шаре Аналітичний вираз двоїстої оцінки для задачі розміщення точок у кулі Analytical expression of the dual bound for the point-packing problem in the ball Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| spellingShingle |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре Березовский, О.А. Шулинок, Г.А. |
| title_short |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| title_full |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| title_fullStr |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| title_full_unstemmed |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| title_sort |
аналитическое выражение двойственной оценки для задачи размещения точек в шаре |
| author |
Березовский, О.А. Шулинок, Г.А. |
| author_facet |
Березовский, О.А. Шулинок, Г.А. |
| publishDate |
2014 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Аналітичний вираз двоїстої оцінки для задачі розміщення точок у кулі Analytical expression of the dual bound for the point-packing problem in the ball |
| description |
Получено аналитическое выражение для двойственной оценки оптимального значения целевой функции квадратичной постановки задачи размещения точек в шаре. Этот результат справедлив также для оценки, получаемой в результате применения к данной постановке задачи SDP-релаксации.
Отримано аналітичний вираз для двоїстої оцінки оптимального значення цільової функції квадратичної постановки задачі розміщення точок у кулі. Цей результат справедливий також для оцінки, що отримується в результаті застосування до даної постановки задачі SDP-релаксації.
We obtain the analytical expression for the dual bound of the optimal value for the quadratic formulation of the point-packing problem in the ball. This result is valid also for the bounds, obtained by invoking SDP-relaxation to this formulation of the problem.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/111506 |
| citation_txt |
Аналитическое выражение двойственной оценки для задачи размещения точек в шаре / О.А. Березовский, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 24-31. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT berezovskiioa analitičeskoevyraženiedvoistvennoiocenkidlâzadačirazmeŝeniâtočekvšare AT šulinokga analitičeskoevyraženiedvoistvennoiocenkidlâzadačirazmeŝeniâtočekvšare AT berezovskiioa analítičniivirazdvoístoíocínkidlâzadačírozmíŝennâtočokukulí AT šulinokga analítičniivirazdvoístoíocínkidlâzadačírozmíŝennâtočokukulí AT berezovskiioa analyticalexpressionofthedualboundforthepointpackingproblemintheball AT šulinokga analyticalexpressionofthedualboundforthepointpackingproblemintheball |
| first_indexed |
2025-11-27T02:17:25Z |
| last_indexed |
2025-11-27T02:17:25Z |
| _version_ |
1850793644442779648 |
| fulltext |
24 Теорія оптимальних рішень. 2014
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Получено аналитическое выра-
жение для двойственной оценки
оптимального значения целевой
функции квадратичной поста-
новки задачи размещения точек в
шаре. Этот результат справед-
лив также для оценки, получае-
мой в результате применения
к данной постановке задачи
SDP-релаксации.
О.А. Березовский,
Г.А. Шулинок, 2014
УДК 519.8
О.А. БЕРЕЗОВСКИЙ, Г.А. ШУЛИНОК
АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ
ДВОЙСТВЕННОЙ ОЦЕНКИ
ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ
ТОЧЕК В ШАРЕ
Задачи размещения и упаковки возникают
при оптимизации хранения и транспорти-
ровки товаров, при исследовании кристал-
лических или пористых структур, при проек-
тировании и компоновке различных техноло-
гических объектов и систем, в теории
надежности системы сигналов, при анализе
структуры нефтеносных пород, при модели-
ровании процессов в активной зоне ядерного
реактора и т. д. Предметом исследования
данной работы является задача размещения
m точек в шаре единичного радиуса так,
чтобы минимальное расстояние между ними
(равное
2
0x ) было максимальным [1, 2]:
* 2
0max ,f x (1)
2 2
0
1
( ) 0,
n
ik jk
k
x x x
1 ,i j m (2)
2
1
1 0,
n
ik
k
x
1, .i m (3)
Поскольку данная задача относится к
NP-трудным, становится актуальной оценка
глобального оптимума, например, путем
вычисления двойственной оценки [3, 4]
max
*
( ( , )) 0
, 0
inf ( , )
A u v
u v
u v
1
*sup ( , , ) ,
nmx R
L x u v f
(4)
где ( , , ) ( , ) ( )TL x u v x A u v x c u – функция
Лагранжа для задачи (1) – (3); u – вектор двой-
ственных переменных, компонента iju кото-
рого соответствует ограничению вида (2)
АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ ДВОЙСТВЕННОЙ ОЦЕНКИ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ...
Теорія оптимальних рішень. 2014 25
для i -ой и j -ой точек, 1 ;i j m v – вектор двойственных переменных для
ограничений (3); эффективное множество D двойственных переменных для
однородной квадратичной задачи ( , ) sup ( , , )
x
u v L x u v записано в виде
неположительности максимального собственного числа матрицы ( , )A u v
max (A( , )) 0.u v Свободный член функции Лагранжа
1
( ) ,
m
i
i
c u v
а матрица
( , )A u v представляет собой блочную диагональную матрицу, первый блок
которой состоит из одного элемента
, 1
1
m
ij
i j
j i
u
(соответствует переменной
0x ),
а остальные n блоков (для каждой k-ой координаты) одинаковы
1 2
1 1 12 11
1
12 12 2 2 22
2
1
1 2
1
k k mk
m
j mk
j
m
j mk
j
m
m m jm mmk
j
x x x
u v u ux
u u u v ux
u u u vx
. (5)
Вследствие однородности квадратичной задачи (1) – (3), решение внутрен-
ней задачи нахождения функции ( , ) sup ( , , )
x
u v L x u v в (4) при u D
тривиально:
max
max
, ( ( )) 0
( )
( ), ( ( )) 0
if A u
u
c u if A u
и вычисление двойственной оценки (4) для рассматриваемой задачи сводится
к решению задачи выпуклой недифференцируемой оптимизации
*
1
min( ),
n
m
i
u R
i
v
(6)
max ( ( , )) 0,A u v , 0,u v (7)
, 0.u v (8)
Утверждение 1. При
*N m точки минимума задачи (6) – (8) и задачи
max
,
10
min max 0; ( ( , )); , 1,
m
i i
u v
iu
v N A u v v i m
(9)
совпадают.
О.А. БЕРЕЗОВСКИЙ, Г.А. ШУЛИНОК
26 Теорія оптимальних рішень. 2014
Доказательство. Для доказательства нам понадобится результат, сформу-
лированный далее в теореме 1 (стр. 25, [5]). Рассмотрим задачу
0min ( ),f y (10)
( ) 0,if y , 1, ,i k (11)
,y M (12)
где ( ),if y 0, ,i k – непрерывные функции, nM R – некоторое множество.
Введем семейство задач, зависящее от вектора параметров ,kz R
0( ) inf{ ( ) : ( ) , 1, ; }.i iV z f y f y z i k y M
Если воспользоваться для учета ограничений (11) негладкой штрафной функ-
цией в форме функции максимума
0 1( ) ( ) max 0, ( ), , ( ) ,N ky f y N f y f y (13)
то справедлива
Теорема 1 (стр. 25, [5]). Пусть
0
( ) (0)
inf ,
t
V te V
L
t
где e – k-мерный
вектор, все компоненты которого равны единице, 1,t R и .N L Тогда точки
минимума исходной задачи (0)V и задачи inf ( ),N
y M
y
где ( )N y определяется
по формуле (13), совпадают.
Запишем функцию ( )V te для задачи (10) – (12)
max
1
( ) inf : ( ( , )) , , 1, ,
m
i i
i
V te v A u v t v t i m u M
max
1
inf : ( ( , ) ) , 0, 1, , ,
m
i i
i
v A u v tI t v t i m u M
где : 0 .M u u Исследуем ее, разбив интервал (0, ) возможных значе-
ний параметра t на два случая: (0,1) и [1, ).
1) в случае, когда 1,t первыми строкой и столбцом матрицы
( ( , ) )A u v tI можно пренебречь, так как
11
, 1
1 0
m
ij
i j
j i
A u t
.u M
Из неположительности других диагональных элементов матрицы ( ( , ) )A u v tI
(необходимое условие неположительной определенности матрицы)
( )k
iiA
1
0
j i m
ji ij i
j j i
u u v t
(под
( )k
ijA будем понимать ( , )i j -элемент k -го
блока матрицы ( ( , ) )A u v tI ) следует, что .vv te Но точка ( , ) (0 , )u vu v te
АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ ДВОЙСТВЕННОЙ ОЦЕНКИ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ...
Теорія оптимальних рішень. 2014 27
с максимально возможными значениями элементов вектора v является
допустимой и, следовательно,
1
( ) .
m
i
i
V te v mt
Тогда оценка штрафного
множителя
1 1
( ) (0) (0)
inf inf (0) ;
t t
V te V mt V
m V
t t
2) случай 0 1.t Сделаем замену переменных ,
1
ij
ij
u
u
t
1 ,i j m
,
1
i
i
v t
v
t
1, .i m Тогда элементы матрицы ( ( , ) )A u v tI примут вид
11
, 1 , 1 , 1
1 (1 ) 1 (1 ) 1 ,
1
m m m
ij
ij ij
i j i j i j
j i j i j i
u
A u t t t u
t
( )
1 1
(1 )
j i j im m
k
ii ji ij i ji ij i
j j i j j i
A u u v t t u u v
1
(1 ) (1 ) ,
1
j i m
ji ij i
j j i
v t
t t u u v
t
( ) (1 ) .k
ij ij ijA u t u
В новых переменных функция ( )V te примет вид
max
1
( ) inf (1 ) : (1 ) ( ( , )) 0,(1 ) 0, ,
m
i
i
V te t v t t A u v t v u M
где : (1 ) 0 .M u t u Учитывая, что рассматривается случай 1 0,t
max
1 1
( ) (1 ) inf : ( ( , )) 0,( , )
m m
ik
i i
V te t t v A u v u v M
(1 ) (0).mt t V
Тогда
0 1 0 1
( ) (0) (1 ) (0) (0)
inf inf (0) .
t t
V te V mt t V V
m V
t t
Таким образом,
*
0 0 1 1
( ) (0) ( ) (0) ( ) (0)
inf min inf , inf .
t t t
V te V V te V V te V
m L
t t t
.
С учетом теоремы 1 доказательство утверждения завершено.
Сформулируем основной результат данной работы.
О.А. БЕРЕЗОВСКИЙ, Г.А. ШУЛИНОК
28 Теорія оптимальних рішень. 2014
Утверждение 2. Двойственная оценка (4) задачи (1) – (3) равна
* 2
.
( 1)
m
m
Доказательство. Рассмотрим задачу (9), к которой, как показано выше,
сводится нахождение двойственной оценки задачи (1) – (3). Пусть имеем точку
* *( , ),u v причем
* 0,iju 1 .i j m Тогда для того, чтобы доказать, что
* *( , )u v является решением задачи (9), достаточно показать, что множество
субградиентов целевой функции задачи (9)
max
1
( , ) max 0; ( ( , )); , 1,
m
i i
i
u v v N A u v v i m
в этой точке содержит нулевой вектор (в случае * 0u ограничением можно
пренебречь и задачу (9) можно рассматривать как безусловную задачу
минимизации выпуклой недифференцируемой функции). Покажем, что это
условие выполняется для точки * *( , ),u v определенной следующим образом:
* 2
,
( 1)
iju
m m
1 ,i j m
* 2
,
( 1)
iv
m
1, .i m
Нетрудно видеть, что при этих значениях двойственных переменных
* *( , )A u v является отрицательно полуопределенной матрицей ранга ,n в кото-
рой ненулевые собственные числа равны
2
,
( 1)
k
m
1,k n (по одному
для каждого блока), а соответствующие им собственные вектора определяются
1
1 1 2(0 ) ,T nm
k n R где вектор-строки 0 m
l m R для всех ,l k
1,l n – нулевые, а при l k –
1 T m
k me R
m
( 0m и
me – нулевой и еди-
ничный m -мерные вектор-строки). Для наглядности приведем соответст-
вующий данной точке * *( , )u v вид функции Лагранжа постановки (1) – (3)
2
* *
1 1
2 2
( , , , )
( 1) ( 1)
n m
ik
k i
m
L z x u v x
m m m
.
Покажем, что в выбранной точке * *( , )u v существует нулевой субградиент
целевой функции ( , )u v задачи (9) –
* * ' * *0 ( , ) conv{ ( , )}.u v u v
Координаты субградиентов
' * *( , )u v определяются по формулам:
'
' * * * *
max( , ) ( ( , )) ,
ij
ij
u u
u v N A u v
'
' * * * *
max( , ) 1 ( ( , )) ,
i
i
v v
u v N A u v
АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ ДВОЙСТВЕННОЙ ОЦЕНКИ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ...
Теорія оптимальних рішень. 2014 29
где коэффициент , 0 1, введен для учета того, что
' '
* * * *
max maxmax{0, ( ( , ))} {0, ( ( , )) },A u v conv A u v
а субградиент функции максимального собственного числа матрицы
( , )A u v в точке
* *( , )u v
'
* * * *
max max( ( , )) conv( : ( ( , )))A u v p p A u v ,
( 1)/2,m m mp R где компоненты вектора p определяются из равенств
2 2 2
0
1
( 2 ),
ij ik ik jk jk
n
u x x x x
k
p s s s s s
2
1
.
i ik
m
v x
k
p s
(14)
Здесь
1{ , 1, 1} nm
ls l n mn R – любой вектор из набора собствен-
ных векторов матрицы
* *( , ),A u v соответствующих ее нулевым собственным
числам, а
ikxs – его координата, соответствующая переменной .ikx Другими сло-
вами, с учетом того, что собственное число равно нулю, s представляет собой
произвольный нормированный вектор, принадлежащий ортогональному
дополнению к подпространству conv( , 1, ),l l n определенному выше.
Определим вектор
( , ) 1i j nms R следующим образом: ( 1 2 )nm n его
компонент равны нулю, и только компоненты, соответствующие
ikx и jkx
равны
1
2n
и
1
2n
соответственно, 1, .k n Рассмотрим набор векторов,
состоящий из
( 1)
2
m m
векторов
( , ) S={ ,1 }i js i j m и вектора
0s
(1,0 )T
nm (ненулевая координата соответствует переменной
0x ). Для этого
набора легко проверить, что
1) все векторы нормированы (
0 1s ,
( , ) 1i js
( , )i js S ) и принадлежат
ортогональному дополнению к conv( , 1, )l l n (
( , )( , ) 0i j
ls
( , )i js S ,
0( , ) 0ls , 1,l n );
2) вектор
( , ) ,i jp вычисленный для
( , )i js S по формулам (14), имеет все
нулевые компоненты, кроме
( , )
1
2
2,
ij
n
i j
u
k
p
n
( , )
1
1 1
,
2 2li
n
i j
u
k
p
n
О.А. БЕРЕЗОВСКИЙ, Г.А. ШУЛИНОК
30 Теорія оптимальних рішень. 2014
1 ,l i
( , ) 1
,
2il
i j
up ,i l m ,l j
( , ) 1
,
2lj
i j
up 1 ,l j ,l i
( , ) 1
,
2jl
i j
up ,j l n
( , ) ( , )
1
1 1
;
2 2i j
n
i j i j
v v
k
p p
n
компоненты вектора
0 ,p
вычисленного для
0s по формулам (14), равны
0
( 1)/2,u m mp e
0 0 .v mp
Рассмотрим линейную комбинацию
( , )
0 ( , ) .
i j
i j
p S
p p p
Поскольку
( , )
( , )
( 1)/2
2
2
2i j
i j
u m m
p S
m
p e
и
( , )
( , ) 1
,
2i j
i j
v m
p S
m
p e
то при
2
2
2
m
справедливо
( , )
' * * 0 ( , )( , ) ( ) 0
ij ij ij ij
i j
i j
u u u u
p S
u v N p N p p
,
' * *( , ) 1 0
i iv vu v N p при
1
1
.
2
m
N
Итак, мы показали, что в точке
* *
( 1)/2
2 2
( , ) ( , ),
( 1) ( 1)
m m mu v e e
m т т
которая является внутренней точкой допустимого множества задачи (9) ( * 0u ),
справедливо
* * ' * *0 ( , ) conv{ ( , )}u v u v , т. е. она является точкой
минимума выпуклой задачи (9); значение функции ( , )u v в этой точке равно
* * *
1
2
( , ) .
( 1)
m
i
i
m
u v v
m
Доказательство завершено.
Следствие 1. Квадрат расстояния между точками в задаче о размещении
m точек в шаре единичного радиуса в n -мерном пространстве не превышает
2
.
( 1)
m
m
Следствие 2. Оценка, полученная с помощью SDP-релаксации задачи
(1) – (3), равна
2
( 1)
m
m
.
АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ ДВОЙСТВЕННОЙ ОЦЕНКИ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ...
Теорія оптимальних рішень. 2014 31
О.А. Березовський, Г.О. Шулінок
АНАЛІТИЧНИЙ ВИРАЗ ДВОЇСТОЇ ОЦІНКИ ДЛЯ ЗАДАЧІ РОЗМІЩЕННЯ ТОЧОК У КУЛІ
Отримано аналітичний вираз для двоїстої оцінки оптимального значення цільової функції
квадратичної постановки задачі розміщення точок у кулі. Цей результат справедливий також
для оцінки, що отримується в результаті застосування до даної постановки задачі
SDP-релаксації.
O.A. Berezovskyi, G.А. Shulinok
ANALYTICAL EXPRESSION OF THE DUAL BOUND FOR THE POINT-PACKING
PROBLEM IN THE BALL
We obtain the analytical expression for the dual bound of the optimal value for the quadratic
formulation of the point-packing problem in the ball. This result is valid also for the bounds,
obtained by invoking SDP-relaxation to this formulation of the problem.
1. Conway J.H. and Sloane N.J.A. Sphere Packings, Lattices and Groups (Second Edition). – NY:
Springer-Verlag, 1993. – 679 p.
2. Anstreicher K. On convex relaxations for quadratically constrained quadratic programming //
Mathematical programming. – 2012. – N 136 (2). – P. 233 – 251.
3. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая
оптимизация. – Киев: Наук. думка, 1989. – 208 с.
4. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht, Kluwer,
1998. – 394 p.
5. Пшеничный Б.Н. Метод линеаризации. – М.: Наука, 1983. – 136 с.
Получено 24.03.2014
|