Использование двойственного подхода для решения одной геометрической задачи
Рассматривается задача построения шара минимального объема с заданным центром, описанного вокруг пересечения одинаково ориентированных эллипсоидов. Приводятся условия, при выполнении которых применение двойственного подхода к квадратичной поставновке данной задачи позволяет найти ее точное решение....
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168422 |
| 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: | Использование двойственного подхода для решения одной геометрической задачи / О.А. Березовский, И.Э. Шулинок // Компьютерная математика. — 2016. — № 2. — С. 94-99. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-168422 |
|---|---|
| record_format |
dspace |
| spelling |
Березовский, О.А. Шулинок, И.Э. 2020-05-01T19:41:58Z 2020-05-01T19:41:58Z 2016 Использование двойственного подхода для решения одной геометрической задачи / О.А. Березовский, И.Э. Шулинок // Компьютерная математика. — 2016. — № 2. — С. 94-99. — Бібліогр.: 5 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168422 519.85 Рассматривается задача построения шара минимального объема с заданным центром, описанного вокруг пересечения одинаково ориентированных эллипсоидов. Приводятся условия, при выполнении которых применение двойственного подхода к квадратичной поставновке данной задачи позволяет найти ее точное решение. Розглядається задача побудови кулі мінімального об’єму з заданим центром, описаної навколо перетину однаково орієнтованих еліпсоїдів. Наведено умови, при виконанні яких застосування двоїстого підходу до квадратичної постановки даної задачі дозволяє знайти її точний розв’язок. The problem of constructing a ball with minimum volume and fixed center, which is described around the intersection of identically oriented ellipsoids, is considered. The conditions, under which the use of dual approach for solving the quadratic formulation of this problem allows us to find its exact solution, are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Использование двойственного подхода для решения одной геометрической задачи Застосування двоїстого підходу для розв’язання однієї геометричної задачі The use of duality approach for solving one geometrical problem 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 |
Березовский, О.А. Шулинок, И.Э. |
| topic |
Оптимизация вычислений |
| topic_facet |
Оптимизация вычислений |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Застосування двоїстого підходу для розв’язання однієї геометричної задачі The use of duality approach for solving one geometrical problem |
| description |
Рассматривается задача построения шара минимального объема с заданным центром, описанного вокруг пересечения одинаково ориентированных эллипсоидов. Приводятся условия, при выполнении которых применение двойственного подхода к квадратичной поставновке данной задачи позволяет найти ее точное решение.
Розглядається задача побудови кулі мінімального об’єму з заданим центром, описаної навколо перетину однаково орієнтованих еліпсоїдів. Наведено умови, при виконанні яких застосування двоїстого підходу до квадратичної постановки даної задачі дозволяє знайти її точний розв’язок.
The problem of constructing a ball with minimum volume and fixed center, which is described around the intersection of identically oriented ellipsoids, is considered. The conditions, under which the use of dual approach for solving the quadratic formulation of this problem allows us to find its exact solution, are given.
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/168422 |
| citation_txt |
Использование двойственного подхода для решения одной геометрической задачи / О.А. Березовский, И.Э. Шулинок // Компьютерная математика. — 2016. — № 2. — С. 94-99. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT berezovskiioa ispolʹzovaniedvoistvennogopodhodadlârešeniâodnoigeometričeskoizadači AT šulinokié ispolʹzovaniedvoistvennogopodhodadlârešeniâodnoigeometričeskoizadači AT berezovskiioa zastosuvannâdvoístogopídhodudlârozvâzannâodníêígeometričnoízadačí AT šulinokié zastosuvannâdvoístogopídhodudlârozvâzannâodníêígeometričnoízadačí AT berezovskiioa theuseofdualityapproachforsolvingonegeometricalproblem AT šulinokié theuseofdualityapproachforsolvingonegeometricalproblem |
| first_indexed |
2025-11-27T03:24:20Z |
| last_indexed |
2025-11-27T03:24:20Z |
| _version_ |
1850796881542643712 |
| fulltext |
94 Компьютерная математика. 2016, № 2
Оптимизация
вычислений
Рассматривается задача по-
строения шара минимального
объема с заданным центром,
описанного вокруг пересечения
одинаково ориентированных эл-
липсоидов. Приводятся условия,
при выполнении которых примене-
ние двойственного подхода к ква-
дратичной поставновке данной
задачи позволяет найти ее
точное решение.
О.А. Березовский, И.Э. Шулинок,
2016
УДК 519.85
О.А. БЕРЕЗОВСКИЙ. И.Э. ШУЛИНОК
ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННОГО
ПОДХОДА ДЛЯ РЕШЕНИЯ
ОДНОЙ ГЕОМЕТРИЧЕСКОЙ ЗАДАЧИ
Постановка задачи. Пусть задан набор
одинаково ориентированных эллипсоидов
(т. е. эллипсоидов, направления полуосей
которых совпадают)
{ : ( ) ( ) 1}T
i i i iE x x d A x d , 1,i m ,
где id – центр эллипсоида, iA – положи-
тельно определенная симметричная матрица.
Требуется найти шар минимального радиуса
с фиксированным центром в некоторой
заданной точке, содержащий пересечение
данного набора эллипсоидов { , 1, }iE i m .
Без ограничения общности далее будем
предполагать, что центр искомого
описанного шара находится в начале
координат, матрицы iA – диагональные
( ( , 1, , ),i ijA diag a j n где 0,ija 1, ,i m
1,j n ). Тогда рассматриваемая задача
может быть представлена в виде следующей
задачи математического программирования:
* min( )Tf x x (1)
при ограничениях
0T T
i i ix A x b x c , 1,i m , (2)
где 2 ,i i ib Ad 1T
i i i ic d A d , 1,i m .
В этой задаче минимальное значение
целевой функции *f равно квадрату радиуса
искомого шара со знаком минус. Вопрос,
рассматривающийся в данной работе –
в каких случаях можно гарантировать решение
ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННОГО ПОДХОДА ДЛЯ РЕШЕНИЯ...
Компьютерная математика. 2016, № 2 95
данной многоэкстремальной задачи за полиномиальное время? Один из возмож-
ных ответов можно получить, исследовав, когда двойственный подход [1 – 3]
дает точную оценку оптимального значения целевой функции задачи (1) – (2).
Вспомогательный результат. Для проведения этих исследований
воспользуемся предложенным в [4] достаточным условием точности
двойственной оценки для квадратичной экстремальной задачи общего вида
*
0min ( )f f x (3)
при ограничениях
( ) 0if x , ,LEi I (4)
( ) 0if x , ,EQi I (5)
где ( ) , {0}T T LE EQ
i i i if x x A x b x c i I I – произвольные квадратичные функции
в пространстве .nR
Чтобы сформулировать это условие, необходимо ввести следующие
обозначения:
( , ) ( ) ( ) ( )T TL x u x A u x b u x c u – функция Ланранжа задачи (3) – (5),
где 0
1
( ) ,
m
i i
i
A u A u A
0
1
( ) ,
m
i i
i
b u b u b
0
1
( )
m
i i
i
c u c u c
, | | | |LE EQm I I ;
D ( D ) – множество двойственных переменных ,mu R при которых
матрица ( )A u положительно (неотрицательно) определена;
{ : 0, }LE
iU u u i I ;
* *sup ( ( ) inf ( , ))
nx Ru D U
u L x u f
– двойственная оценка квадратичной
экстремальной задачи (3) – (4) [1];
*x и *u – вектора, в которых достигаются значения *f и * соот-
ветственно.
Пусть для каждого ( \ )u D D U определено множество индексов
( ) { : ( ) 0, {1,..., }}jJ u j u j n , где ( )j u , 1,j n , – собственные числа матри-
цы ( )A u функции Лагранжа задачи (3)–(5). И пусть ( )j u , 1,j n , –
собственные вектора, соответствующие собственным числам ( )j u , 1,j n .
В этих обозначениях справедлива
Теорема [4]. Если существуют такой вектор p и такое положительное
число 0 , что для любого (0, )
( \ )u D D U ( )j J u такое, что 0
1
( )( ) 0
m
T
j i i
i
u b u b p
, (6)
то * *.f Причем, если условие (6) выполняется при 0p , то вектор
* * 1 * *( ) ( ) ( ) / 2x x u A u b u является решением задачи (3) – (5).
О.А. БЕРЕЗОВСКИЙ, И.Э. ШУЛИНОК
96 Компьютерная математика. 2016, № 2
Достаточное условие получения точной оценки для задачи (1) – (2).
Используя приведенную теорему о достаточном условии точности двойственной
оценки, исследуем некоторые случаи, когда для рассматриваемой в данной
работе задачи (1) – (2) двойственный подход гарантирует нахождение
оптимального значения ее целевой функции, т. е. * *.f
Функция Лагранжа задачи (1) – (2) равна ( , ) ( ) ( ) ( ),T TL x u x A u x b u x c u
где
1
( ) ( 1 , 1,..., )
m
i ij
i
A u diag u a j n
,
1
( )
m
i i
i
b u u b
,
1
( ) .
m
i i
i
c u u c
Все собственные векторы матрицы ( )A u направлены по координатным осям
и не зависят от двойственных переменных, а собственные числа равны
1
( ) 1
m
j i ij
i
u u a
, 1,j n . Тогда для задачи (1) – (2)
1,...,n 1
( \ ) : min ( 1 ) 0; 0
m
i ijj i
D D U u u a u
.
Путем подстановки в неравенство условия (6) при 0p соответствующих
значений параметров задачи (1) – (2) имеем
1
( ) ( ) 0,
m
T T
j j i i
i
u b u e u b
где ( )j ju e , 1,j n , – собственные векторы матрицы ( ),A u je – n-мерный
вектор, j-ая компонента которого равна единице, а остальные равны нулю.
Таким образом, условие (6) при 0p для задачи (1) – (2) примет вид
1,...,n 1
: min ( 1 ) 0; 0
m
i ijj i
u u u a u
( )j J u такое, что
1
0
m
T
j i i
i
e u b
. (7)
Пусть для некоторого ( \ )u D D U равно нулю j -е собственное число
матрицы ( )A u :
1,...,n 1 1
min ( 1 ) 1 0.
m m
i ij i ijj i i
u a u a
Один из способов удовле-
творить условие (7) – потребовать, чтобы
1
0
m
T
i ij
i
e u b
было независимо от
значения вектора u . Другими словами, чтобы j -я координата конической
комбинации векторов { , 1, }ib i m никогда не принимала бы значение ноль. Это
возможно, когда j -е координаты всех векторов ib , 1, ,i m одного знака
(поскольку 0u ). Таким образом, обобщая сказанное на все {1,..., },j n
получаем, что условие (7) при 0p выполняется, если все векторы , 1, ,ib i m
расположены в одном открытом ортанте. Кроме того, также рассмотрим случай,
ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННОГО ПОДХОДА ДЛЯ РЕШЕНИЯ...
Компьютерная математика. 2016, № 2 97
когда среди этих ijb найдется i , такое что 0ijb . Тогда достаточно в нулевом
векторе p заменить j -ю компоненту на
1,...,
( max ),j iji m
p sign b
чтобы выполнилось
условие (6) теоремы (в случае, когда {1,..., }i m 0,ijb jp можно присвоить
любое значение, кроме нуля).
Принимая во внимание, что вектор ib и вектор, задающий центр эллипсоида
,iE противоположно направлены ( 1 1 2 22 2( ... )T
i i i i i i i in inb A d a d a d a d ), полу-
чаем справедливость следующего утверждения.
Утверждение 1. Если центры всех эллипсоидов расположены в одном
закрытом ортанте, то двойственная оценка задачи (1) – (2) точная. Если же они
расположены в одном открытом ортанте, то также получаем и точку решения
задачи * 1 * *( ) ( ) / 2.x A u b u
Частный случай задачи (1) – (2) для гомотетичных эллипсоидов.
Рассмотрим задачу построения шара минимального объема с заданным центром,
описанного вокруг пересечения гомотетичных эллипсоидов (т. е. с одинаковыми
с точностью до положительного множителя матрицами в соответствующих им
квадратичных формах). Соответствующая ей задача (1) – (2) упростится:
* min( )Tf x x (8)
при ограничениях
1 0T T
i ix A x b x c , 1,i m . (9)
Здесь, как и в задаче (1) – (2), без ограничения общности, предполагается, что
центр описанного шара находится в центре координат, 1 ( , 1, , )jA diag a j n –
диагональная матрица.
Функция Лагранжа задачи (8)–(9) равна ( , ) ( ) ( ) ( ),T TL x u x A u x b u x c u
где
1
( ) ( 1 , 1,..., )
m
j i
i
A u diag a u j n
,
1
( )
m
i i
i
b u u b
,
1
( )
m
i i
i
c u u c
. Собствен-
ные векторы матрицы ( )A u направлены по координатным осям и не зависят
от двойственных переменных, а собственные числа
1
( ) 1 ,
m
j j i
i
u a u
1, .j n
Для этой задачи
1,...,n 1
( \ ) : min ( 1 ) 0; 0
m
j ij i
D D U u a u u
min1,...,n 1 1
: ( 1 min 0; 0 : ( 1 0; 0 .
m m
j i j ij i i
u a u u u a u u
Для данной задачи множество индексов ( )J u для всех ( \ )u D D U
одинаково и состоит из единственного элемента min,j соответствующего
минимальному собственному числу матрицы 1.A Тогда условие (6) при 0p
для задачи (8) – (9) имеет вид
О.А. БЕРЕЗОВСКИЙ, И.Э. ШУЛИНОК
98 Компьютерная математика. 2016, № 2
min
1
: ( 1 0; 0
m
j i
i
u u a u u
min 0 min
1 1
( )( ) ( ) 0,
m m
T
j i i i i j
i i
u b u b u b
которое гарантировано выполняется, если minj -е компоненты всех векторов
, 1,ib i m , одного знака.
В случае, когда среди minijb найдется ,i такое что min 0,ijb достаточно
в нулевом векторе p заменить minj -ю компоненту на min min1,...,
( max ),j iji m
p sign b
чтобы выполнилось условие (6) теоремы.
Утверждение 2. Если координаты центров всех эллипсоидов, сответству-
ющие минимальному собственному числу, имеют один знак или равны нулю,
то двойственная оценка задачи (8) – (9) точная. Если же они строго одного
знака, то также получаем и точку решения задачи * 1 * *( ) ( ) / 2.x A u b u
Частный случай задачи (1) – (2) для шаров. В работе [5] рассмотрен еще
один частный случай задачи (1) – (2) – построение шара минимального объема
с заданным центром, описанного вокруг пересечения шаров:
* min( )Tf x x (10)
при ограничениях
0T T
i ix x b x c , 1, .i m (11)
В задаче (8) – (9) матрица
1
( ) ( 1 , 1,..., )
m
i
i
A u diag u j n
функции Лагран-
жа имеют собственные вектора, направленные по координатным осям, и все ее
собственные числа одинаковы:
1
( ) 1 ,
m
j i
i
u u
1, .j n Условие (6) при 0p
для задачи (10) – (11) имеет вид
1
: ( 1 0; 0
m
i
i
u u u u
1
0,
m
i i
i
u b
что означает 0 int( { , 1,..., }).ico b i m В случае, когда центр координат лежит на
границе { , 1,..., },ico b i m достаточно принять
1
m
i i
i
p u b
при 0u , чтобы
выполнилось условие (6) теоремы.
Утверждение 3 [5]. Если 0 int( { , 1,..., }),ico b i m то двойственная оценка
задачи (10) – (11) точная. Если же 0 { , 1,..., },ico b i m то кроме точной
двойственной оценки также получаем и точку решения задачи (10) – (11)
* 1 * *( ) ( ) / 2.x A u b u
Отметим, что достаточное условие точности двойственной оценки для
квадратичной экстремальной задачи общего вида, сформулированное в виде
вышеприведенной теоремы, можно применять и для исследования других задач.
ИСПОЛЬЗОВАНИЕ ДВОЙСТВЕННОГО ПОДХОДА ДЛЯ РЕШЕНИЯ...
Компьютерная математика. 2016, № 2 99
Например, с помощью этой теоремы в работе [4] были выделены случаи, когда
двойственный подход позволяет получить оптимальное значение целевой
функции и точку глобального экстремума одной специальной задачи
невыпуклой оптимизации, которая встречается при синтезе управления,
минимизирующего область локализации инвариантного множества семейства
нелинейных систем.
О.А. Березовський, І.Е. Шулінок
ЗАСТОСУВАННЯ ДВОЇСТОГО ПІДХОДУ ДЛЯ РОЗВ’ЯЗАННЯ
ОДНІЄЇ ГЕОМЕТРИЧНОЇ ЗАДАЧІ
Розглядається задача побудови кулі мінімального об’єму з заданим центром, описаної
навколо перетину однаково орієнтованих еліпсоїдів. Наведено умови, при виконанні яких
застосування двоїстого підходу до квадратичної постановки даної задачі дозволяє знайти її
точний розв’язок.
O.A. Berezovskyi, I.E. Shulinok
THE USE OF DUALITY APPROACH FOR SOLVING ONE GEOMETRICAL PROBLEM
The problem of constructing a ball with minimum volume and fixed center, which is described
around the intersection of identically oriented ellipsoids, is considered. The conditions, under which
the use of dual approach for solving the quadratic formulation of this problem allows us to find its
exact solution, are given.
1. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая
оптимизация. К.: Наук. думка, 1989. 208 с.
2. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. Dordrecht, Kluwer, 1998.
394 p.
3. Березовский О.А. О точности двойственных оценок для квадратичных экстремальных
задач. Кибернетика и системный анализ. 2012. № 1. С. 33 – 39.
4. Berezovskyi O.A. On Solving of a Special Optimization Problem Connected with Determina-
tion of Invariant Sets of Dynamical Systems. Journal of Automation and Information Sciences.
2015. 47 (5). P. 69 – 77.
5. Березовский О.А. Критерии точности SDP-релаксаций квадратичных экстремальных
задач. Кибернетика и системный анализ. 2016. № 6. С. 95 – 101.
Получено 26.07.2016
Об авторах:
Березовский Олег Анатольевич,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
Шулинок Ирина Эдуардовна,
кандидат физико-математических наук, научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
|