Квадратичные оптимизационные задачи компьютерной геометрии
Работа посвящена постановке и решению класса квадратичных оптимизационных задач компьютерной геометрии: поиск эллипсоида минимального объема, содержащего множество точек евклидового пространства, поиск минимального расстояния между эллипсоидами, построение гиперплоскости, разделяющей два эллипсоид...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/56125 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Квадратичные оптимизационные задачи компьютерной геометрии / А.И. Косолап // Штучний інтелект. — 2010. — № 1. — С. 70-75. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-56125 |
|---|---|
| record_format |
dspace |
| spelling |
Косолап, А.И. 2014-02-12T00:07:17Z 2014-02-12T00:07:17Z 2010 Квадратичные оптимизационные задачи компьютерной геометрии / А.И. Косолап // Штучний інтелект. — 2010. — № 1. — С. 70-75. — Бібліогр.: 10 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56125 519.85 Работа посвящена постановке и решению класса квадратичных оптимизационных задач компьютерной геометрии: поиск эллипсоида минимального объема, содержащего множество точек евклидового пространства, поиск минимального расстояния между эллипсоидами, построение гиперплоскости, разделяющей два эллипсоида. Предложены эффективные алгоритмы для решения этого класса задач. Робота присвячена постановці та розв’язку класу квадратичних оптимізаційних задач комп’ютерної геометрії: пошук еліпсоїду мінімального об’єму, що містить множину точок евклідового простору, пошук мінімальної відстані між еліпсоїдами, побудова гіперплощини, що розділяє два еліпсоїда. Запропоновані ефективні алгоритми для розв’язку цього класу задач. The paper is devoted to the statement and the solution of a class of quadratic optimizing problems in the computer geometry: the search of the minimum volume ellipsoid that contains the set of points of Euclidean space, the search of the minimum distance between ellipsoids, the construction of the hyperplane separating two ellipsoids. The effective algorithms for the solution of this class of problems are offered. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Квадратичные оптимизационные задачи компьютерной геометрии Квадратичні оптимізаційні задачі комп’ютерної геометрії Quadratic Optimization Problems of Computer Geometry 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 |
2010 |
| language |
Ukrainian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Квадратичні оптимізаційні задачі комп’ютерної геометрії Quadratic Optimization Problems of Computer Geometry |
| description |
Работа посвящена постановке и решению класса квадратичных оптимизационных задач компьютерной геометрии: поиск эллипсоида минимального объема, содержащего множество точек евклидового пространства, поиск минимального расстояния между эллипсоидами, построение гиперплоскости, разделяющей два эллипсоида. Предложены эффективные алгоритмы для решения этого класса задач.
Робота присвячена постановці та розв’язку класу квадратичних оптимізаційних задач комп’ютерної геометрії: пошук еліпсоїду мінімального об’єму, що містить множину точок евклідового простору, пошук мінімальної відстані між еліпсоїдами, побудова гіперплощини, що розділяє два еліпсоїда. Запропоновані ефективні алгоритми для розв’язку цього класу задач.
The paper is devoted to the statement and the solution of a class of quadratic optimizing problems in the computer geometry: the search of the minimum volume ellipsoid that contains the set of points of Euclidean space, the search of the minimum distance between ellipsoids, the construction of the hyperplane separating two ellipsoids. The effective algorithms for the solution of this class of problems are offered.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/56125 |
| citation_txt |
Квадратичные оптимизационные задачи компьютерной геометрии / А.И. Косолап // Штучний інтелект. — 2010. — № 1. — С. 70-75. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT kosolapai kvadratičnyeoptimizacionnyezadačikompʹûternoigeometrii AT kosolapai kvadratičníoptimízacíinízadačíkompûternoígeometríí AT kosolapai quadraticoptimizationproblemsofcomputergeometry |
| first_indexed |
2025-11-25T20:39:15Z |
| last_indexed |
2025-11-25T20:39:15Z |
| _version_ |
1850525285732057088 |
| fulltext |
«Искусственный интеллект» 1’2010 70
2К
УДК 519.85
А.И. Косолап
Днепропетровский национальный университет имени Олеся Гончара,
г. Днепропетровск, Украина
anivkos@ua.fm
Квадратичные оптимизационные задачи
компьютерной геометрии
Работа посвящена постановке и решению класса квадратичных оптимизационных задач компьютерной
геометрии: поиск эллипсоида минимального объема, содержащего множество точек евклидового пространства,
поиск минимального расстояния между эллипсоидами, построение гиперплоскости, разделяющей два
эллипсоида. Предложены эффективные алгоритмы для решения этого класса задач.
Введение
Компьютерная, или вычислительная, геометрия − это новое направление иссле-
дований, предметом которой является анализ и построение эффективных алгоритмов
решения геометрических задач [1]. Она рассматривает такие актуальные задачи, как:
триангуляцию, построение выпуклых оболочек, определение принадлежности одного
объекта другому, поиск их пересечения, разделение множеств, аппроксимацию и т.п.
Компьютерная геометрия используется в распознавании образов, инженерном проекти-
ровании, медицине, компьютерной графике, робототехнике, компьютерных играх и т.д.
Большинство рассматриваемых задач в этих областях являются оптимизационными,
для решения которых разработано большое число методов. Однако решение таких за-
дач в режиме реального времени требует разработки новых и эффективных алгоритмов.
В последние годы внимание исследователей в этой области привлекают такие
объекты, как эллипсоиды. Эллипсоиды имеют небольшое количество геометрических
параметров и эффективны для приближения широкого класса выпуклых объектов
при моделировании физических систем. Обнаружение столкновения или наложения
двух эллипсоидов является, таким образом, важной проблемой с приложениями в ком-
пьютерной графике, компьютерной мультипликации, виртуальном мире, робототех-
нике, CAD/CAM, вычислительной физике. Однако использование эллипсоидов огра-
ничивалось недостатком эффективных методов для обнаружения их разделения или
наложения. Рассмотрение эллипсоидов в n-мерном евклидовом пространстве является
стимулирующим фактором для разработки эффективных алгоритмов квадратичной
оптимизации.
Постановка задач и анализ последних результатов
Любой геометрический объект можно представить множеством точек }{ ix в n -
мерном евклидовом пространстве. Эти точки можно описать эллипсоидом минималь-
ного объема. Уравнение эллипсоида имеет вид
},1)()(|{)( 000 ≤−−= xxQxxxxE T
Квадратичные оптимизационные задачи компьютерной геометрии
«Штучний інтелект» 1’2010 71
2К
где точка 0x – центр эллипсоида, а Q – положительно определенная матрица. Известно,
что эллипсоид минимального объема, содержащий заданное множество точек, един-
ственный. Объем эллипсоида равен
,)det(
)det(
)( 2/11−== Q
Q
EVol ωω
где ω − объем единичного шара. Таким образом, задача построения эллипсоида, со-
держащего заданное множество точек { },ix сводится к решению следующей оптими-
зационной задачи:
},0,,...,1,1)()(|)min{det( 001 fQmixxQxxQ iTi =≤−−− (1)
где необходимо определить положительно определенную матрицу Q и вектор 0x .
Учитывая то, что функция )det( 1−Q является выпуклой, а множество всех положитель-
но определенных матриц образует выпуклый конус, задача (1) является задачей вы-
пуклой оптимизации. Однако условие положительной определенности матрицы не мо-
жет быть записано в явном виде, что создает трудности в решении задачи (1). Заменим
целевую функцию задачи (1) на эквивалентную )).log(det( 1−Q Градиент этой функции
равен Q . Это позволяет использовать для решения задачи (1) метод Франка-Вулфа, в
котором на каждой итерации решается линейная задача полуопределенной оптими-
зации
0 0min{ | ( ) ( ) 1, 1,..., , 0}.i T i
kQ Q x x Q x x i m Q× − − ≤ = f
В настоящее время разработаны прямо-двойственные методы внутренней точки для
решения линейных задач полуопределенной оптимизации [2]. Ниже рассматривают-
ся более простые алгоритмы решения задачи (1).
Если геометрический объект задан в виде многогранника },0,0|{ ≥≤ xAxx то
задача построения эллипсоида минимального объема, содержащего многогранник,
значительно усложняется, так как становится NP-сложной [3].
Для поиска минимального расстояния между двумя эллипсоидами разработан
алгоритм [4], в котором на каждой итерации строятся вписанные в эллипсоиды шары
максимального радиуса, касающиеся граничной точки эллипсоида. Новое приближе-
ние искомого отрезка находят на прямой, соединяющей центры шаров. Другие алго-
ритмы на каждой итерации решают вспомогательную квадратичную задачу поиска
минимального расстояния от точки *x до границы эллипсоида
}.1)()(|||*min{|| 002 ≤−−− xxQxxxx T (2)
В работе предлагается эффективный алгоритм для решения задачи (2).
Проблема классификации объектов − одна из наиболее важных в области искус-
ственного интеллекта. Разработано множество алгоритмов для построения гиперплос-
костей, разделяющих различные выпуклые объекты [5], [6]. Разделяющую гиперплоскость
легко построить, если найдено минимальное расстояние (отрезок) между эллипсоида-
ми. Она будет перпендикулярной минимальному отрезку и проходить через его середину.
Алгоритмы решения задач компьютерной геометрии
Рассмотрим задачу построения эллипсоида минимального объема, содержащего
заданное множество точек. Очевидно, что точки, принадлежащие внутренности их
Косолап А.И.
«Искусственный интеллект» 1’2010 72
2К
выпуклой оболочки, можно исключить при построении эллипсоида. Для исключения
таких точек решим последовательность задач линейного программирования
},0,1,|min{
)()()(
≥== ∑∑∑
∈∈∈
λλλλ
kIj
j
k
kIj
j
j
kIj
j xx
для ),(,...,1 kIk = где )(kI − множество индексов оставшихся точек. Если ,1}max{0 << jλ
то точку kx можно представить линейной комбинацией других точек, тогда такие точ-
ки исключаем из дальнейшего рассмотрения (обновляем множество индексов )(kI ).
Пусть число оставшихся точек равно .m
Разработан простой алгоритм решения задачи (1), когда оси эллипсоида совпа-
дают с осями координат [7]. В этом случае, задача (1) эквивалентна следующей задаче:
}.0,,...,1,1)(|)log(max{ 20
11
>=≤−∑∑
==
amixxaa j
n
j
i
jj
n
j
j (3)
Задача (3) преобразуется к двойственной
},0,1|))()(log(max{
1
2 ≥=−∑
=
zzezvzu
n
j
T
jj (4)
где e − вектор, состоящий из единиц, а
,,...,1,)()(
1
2 mjxzzu
m
i
i
jij ==∑
=
.,...,1,)(
1
njxzzv
m
i
i
jij ==∑
=
Для решения задачи (4) используем метод Франка-Вулфа [8]. Пусть *z − ее решение,
тогда искомый эллипсоид имеет вид
}.1
*))(*)((
*))((
{
1
2
2
≤
−
−
= ∑
=
n
j jj
jj
zvzun
zvx
xE
Для построения эллипсоида, в общем случае, преобразуем систему координат, выби-
рая новые координатные гиперплоскости методом наименьших квадратов
∑
=
=−
m
i
iT abxa
1
2 },1|||||)(min{
где bxaT = − искомая гиперплоскость. Следующую координатную гиперплоскость
найдем методом наименьших квадратов для проекции точек на пересечение преды-
дущих найденных координатных гиперплоскостей. Проекция точки ix на пересече-
ние гиперплоскостей }|{ bAxx = вычисляется по следующей формуле:
).()( 1 bAxAAAxx iTTi −−= −
После преобразования координат решаем задачу (4) и для найденного эллипсоида
производим обратное преобразование координат.
Разработана программа, реализующая данный алгоритм. Пример работы програм-
мы представлен на рис. 1 для 7 точек
}.8,3;2,1;5,2;1,4;6,4;6,1;3,7{ −−−−
Квадратичные оптимизационные задачи компьютерной геометрии
«Штучний інтелект» 1’2010 73
2К
Уравнение эллипсоида имеет вид
2 2
1 2 1 20,0103( 0,641) 0,0367( 0,997) 0,0064( 0,641)( 0,997) 1.x x x x+ + − + + − =
Рисунок 1 – Эллипсоид, содержащий точки
Задаче поиска минимального расстояния между двумя выпуклыми множества-
ми 1S и 2S посвящено много работ [9], [10]. Она формулируется следующим обра-
зом. Найти
}.,|||min{|| 21 SySxyx ∈∈−
Будем предполагать, что заданы два эллипсоида матрицами 1Q и 2Q с центрами
в точках 21, zz соответственно. Для поиска минимального расстояния между эллип-
соидами )( 1
1 zE и )( 2
2 zE рассмотрим алгоритм, предложенный в [4].
1. Находим точки 21, xx пересечения отрезка ],[ 21 zz с границами эллипсоидов
., 21 EE
2. Вычисляем градиенты 21, gg в точках 21, xx к эллипсоидам ., 21 EE Задача по-
иска минимального расстояния решена, если
,2,1,0)()( 12 ==−− ig
gg
egexx i
i
T
i
T
iT
тогда ее решение отрезок ],[ 21 xx ( e − вектор, состоящий из единиц).
Определяем центры новых шаров по формулам
2,1,
||||
=−= i
Q
gxz
i
iii
и переходим к шагу 1.
Из сходимости данного алгоритма [4] следует, что скалярные произведения
2,1,
||||||||
)(
*
*
=i
gg
gg
i
k
i
i
Tk
i
будут убывать, когда ∞→k , где *
ig − градиент в оптимальной точке. Это означает,
что скорость сходимости алгоритма можно увеличить, если на втором шаге выбирать
градиент в виде ,1−+ k
ik
k
i gg µ где .0→kµ
В других алгоритмах на каждой итерации решается только задача (2). Она может
быть решена методом Франка-Вулфа. Более простым является следующий алгоритм:
Косолап А.И.
«Искусственный интеллект» 1’2010 74
2К
1. Находим градиент )( 1
2 xg и решаем задачу
}.|max{ 22 ExxgT ∈ (5)
Ее решение достигается в точке
.*
2
1
22
2
1
2
2
gQg
gQzx
T −
−
+=
2. Проектируем точку 1x на гиперплоскость ,0*)(2 =− xxgT имеем
.
||||
)*(
2
2
1
21 g
g
xxgxx
T −
+=
Если точки x и *x не совпадают, то полагаем 2/*)(1 xxx += и переходим к
шагу 1.
3. В противном случае, проектируем исходную точку на гиперплоскость
.0*)(2 =− xxgT Если проекция px совпадает с точкой *x , то задача решена, иначе по-
лагаем 1 1(1 ) (0 1, 0)px x xα α α α= − + ≤ ≤ → и переходим к шагу 1.
На каждой итерации этого алгоритма расстояние между точкой 1x и границей
эллипсоида 2E убывает. Одновременно убывает расстояние между точкой касания
гиперплоскости эллипсоида и проекцией на эту гиперплоскость исходной точки. Поэто-
му в пределе будет найдено решение задачи (2).
Были проведены многочисленные эксперименты по сравнению эффективности
этих алгоритмов. Они показали, что скорость сходимости второго алгоритма выше.
В примере (рис. 2.)
2 2
1 1{ |1, 2( 2) 0,05( 3) 1},E x x x= − + − ≤
},10)3(420)3(|{ 21
2
2
2
12 ≤++++= xxxxxE
первый алгоритм потребовал более 300 итераций (нахождения шаров) для заданной
точности 0,00001,ε = а второй алгоритм потребовал 7 решений задачи (2).
Минимальный отрезок равен [1,348937, 0,13478;0,531722, 0,32035].− −
Рисунок 2 – Минимальный отрезок, соединяющий эллипсоиды
Квадратичные оптимизационные задачи компьютерной геометрии
«Штучний інтелект» 1’2010 75
2К
Рассмотрим задачу построения гиперплоскости, разделяющей два эллипсоида. Для
ее решения используем алгоритмы предыдущей задачи. Если ],[ 21 xx – кратчайший
отрезок между двумя эллипсоидами, то разделяющей гиперплоскостью будет следующая
.0)
2
()(
12
12 =
−
−−
xxxxx T
Эта гиперплоскость перпендикулярна отрезку ],[ 21 xx и проходит через его середину.
Выводы
Рассмотрены задачи компьютерной геометрии, которые относятся к квадратич-
ной оптимизации. Предложены эффективные алгоритмы для решения этого класса задач.
Их сходимость следует из сходимости используемых алгоритмов оптимизации. Разра-
ботано программное обеспечение, реализующее данные алгоритмы, и проведены чис-
ленные эксперименты. Эти эксперименты подтверждают эффективность предложенных
алгоритмов.
Литература
1. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос; пер. с англ. С.А. Ви-
чеса, М.М. Комарова; под. ред. Ю.М. Баяковского. – М. : Наука, 1989. – 480 с.
2. Todd M.J. Semidefinite optimization / M.J. Todd // Acta Numerica. – 2001. – № 10. – P. 515-560.
3. Goton J. Minimal ellipsoid circumscribing a polytope define by a system of linear inequalities / J. Goton,
H. Konno. – University of Tsukuba, 2004. – 12 p.
4. Lin A. On the distance between two ellipsoids / A. Lin, S.-P. Han // SIAM Journal of Optimization. –
2002. – № 13. – Р. 298-308.
5. Boyd S. Convex Optimization / S. Boyd, L. Vandenberghe. – Cambridge University Press. Cambridge.
UK. – 2004. – 730 р.
6. Wang W. An algebraic condition for the separation of two ellipsoids / W. Wang, J. Wang, M.-S. Kim //
Comp. Aided Geom. Design. – 2001. – № 18(6). – Р. 531-539.
7. Kumar P. Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids / P. Kumar, E.A. Yildirim //
J Optim Theory Appl. – 2008. – № 136. – P. 211-228.
8. Мину М. Математическое программирование / Мину М. – М. : Наука, 1990. – 488 с.
9. Cameron S. A comparison of two fast algorithms for computing the distance between convex polyhedral /
S. Cameron // IEEE Trans. Robot. Automat. – 1997. – Vol. 13, № 6. – Р. 915-920.
10. Jimenez P. 3D collision detection: A survey / Jimenez P., Thomas F., Torras C. // Computers and Gra-
phics. – 2001. – № 25(2). – Р. 269-285.
А.І. Косолап
Квадратичні оптимізаційні задачі комп’ютерної геометрії
Робота присвячена постановці та розв’язку класу квадратичних оптимізаційних задач комп’ютерної
геометрії: пошук еліпсоїду мінімального об’єму, що містить множину точок евклідового простору,
пошук мінімальної відстані між еліпсоїдами, побудова гіперплощини, що розділяє два еліпсоїда.
Запропоновані ефективні алгоритми для розв’язку цього класу задач.
A.I. Kosolap
Quadratic Optimization Problems of Computer Geometry
The paper is devoted to the statement and the solution of a class of quadratic optimizing problems in the
computer geometry: the search of the minimum volume ellipsoid that contains the set of points of Euclidean
space, the search of the minimum distance between ellipsoids, the construction of the hyperplane separating two
ellipsoids. The effective algorithms for the solution of this class of problems are offered.
Статья поступила в редакцию 01.12.2009.
|