Полиэдрально-сферические конфигурации: особенности и применение

Оксана Сергеевна Пичугина

Анотація


В статье рассмотрены конечные точечные конфигурации, расположенные на гиперсфере (полиэдрально-сферические конфигурации, PSCs) и исследованы их алгебро-топологичес­кие и тополого-метрические свойства.

Поставлены следующие задачи: определение, является ли конечная точечная конфигурация полиэдрально сферической; определение центра и радиуса сферы, описанной вокруг PSC ; определение центра и радиуса PSC, т.е. центра и радиуса описанной сферы минимального радиуса; поиск возможных способов редукции задач, поставленных на PSCs, в частности, их декомпозиции на полиэдрально-сферические подконфигурации. Выделены, исследованы особенности и решены поставленные задачи для трех классов PSCs — симплексных, перестановочных и двухуровневых по координатам, в частности, установлена их связь с базовыми множествами евклидовых комбинаторных конфигураций перестановок и булевых векторов.

Также исследованы свойства PSCs общего вида, в частности, исследован вопрос определения центра и радиуса PSCs, образованных в результате теоретико-множественных операций над точечными конфигурациями, среди которых есть PSCs. Важной отличительной особенностью PSCs является то, что они совпадают со множеством вершин своей выпуклой оболочки, то есть относятся к классу вершинно расположенных. Соответственно, они образуются в пересечении гиперсферы со своей выпуклой оболочкой. Это позволяет при оптимизации на них применять теорию выпуклых продолжений к функциям, заданным на PSCs. В частности, можно считать, что как целевая функция, так и функциональные ограничения задач оптимизации выпуклые и гладкие. А это, в свою очередь, открывает широкие перспективы создания методов типа ветвей и границ, использующие, с одной стороны, при ветвлении - структурные особенности специальных классов PSCs, а с другой - оценки, получаемые в результате решения выпуклых полиэдральных релаксационных задач либо сферических релаксационных задач с выпуклыми целевыми функциями и функциональными ограничениями.

В статье широко освещены вопросы разложений PSCs по выпуклым поверхностям, в частности, по семейству вложенных гиперсфер и параллельным плоскостям. С задачей декомпозиции тесно связана задача декомпозиции PSCs на полиэдрально-сферические подконфигурации, решение которой также предложено в данной работе.

Полученные результаты имеют самостоятельный теоретический интерес, а также применимы в вычислительных алгоритмах, реализующих полиэдрально-сферические методы решения задач оптимизации на PSCs.


Повний текст:

PDF (Русский)

Посилання


Pardalos P.M. Handbook of combinatorial optimization / P.M. Pardalos,

D-Z. Du, R.L. Graham. — New York : Springer, 2013. — 3409 p.

Korte B. Combinatorial Optimization: Theory and Algorithms / B. Korte, J. Vygen. — Heidelberg ; New York : Springer, 2012. — 660 p.

Papadimitriou C. H. Combinatorial Optimization: Algorithms and Complexity / C. H. Papadimitriou, K. Steiglitz. — Dover Publications Inc., 2013. — 528 p.

Grande F. On k-level matroids: geometry and combinatorics / F. Grande Doctor of Natural Sciences Dissertation. — Berlin : Institut für Mathematik und In-formatik, Freie Universität Berlin, 2015. — 122 p.

Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования / Ю. Г. Стоян, С. В. Яковлев. — К. : Наук. дум-ка, 1986. — 268 с.

Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації / Ю. Г. Стоян, О. О. Ємець. — К. : Ін-т системн. дослідж. освіти, 1993. — 188 с.

Стоян Ю. Г. Евклидовы комбинаторные конфигурации: монография / Ю. Г. Стоян, С. В. Яковлев, О. С. Пичугина. — Харьков : Константа, 2017. — 404 с.

Пичугина О. С. Непрерывные функциональные представления в задачах дискретной оптимизации : монография / О. С. Пичугина, С. В. Яковлев. — Харьков : Коллегиум, 2018. — 312 с.

Pichugina O. Optimization on Polyhedral-Spherical Sets: Theory and Applica-tions / O. Pichugina, S. Yakovlev // In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON). — 2017. — P. 1167–1175.

Stoyan Y. G. Quadratic optimization on combinatorial sets in / Y. G. Stoyan, S. V. Yakovlev, O. V. Parshin // Cybernetics and Systems Analysis. — 1991. — Vol. 27(4). — P. 562–567.

Yakovlev S. V. Properties of Combinatorial Optimization Problems Over Poly-hedral-Spherical Sets / S. V. Yakovlev, O. S. Pichugina // Cybernetics and Sys-tems Analysis. — 2018. — Vol. 54 (1). — P. 99–109.

Пичугина О. С. Поверхностные и комбинаторные отсечения в задачах евклидовой комбинаторной оптимизации / О. С. Пичугина // Мат. та комп. модел. Сер. Фіз.-мат. науки. — 2016. — Вип. 13. — C. 144–160.

Пичугина О. С. Методы глобальной оптимизации на перестановочном многограннике в комбинаторных задачах на вершинно расположенных множествах / О. С. Пичугина, С. В. Яковлев // Мат. та комп. модел. Сер. Фіз.-мат. науки. — 2017. — Вип. 15. — C. 152–158.

Яковлев С. В. Задачи оптимизации на евклидовых комбинаторных конфигурациях и их свойства / С. В. Яковлев, О. С. Пичугина // Пит. прикл. ма-тем. і матем. модел. — 2017. — Вип. 17. — С. 278–263.

Schneider P. Geometric Tools for Computer Graphics /. P. Schneider, D. H. Eberly. — Amsterdam: Morgan Kaufmann, 2002. — 1056 p.

Pichuginа O. Convex extensions and continuous functional representations in optimization, with their applications / O. Pichuginа, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. — 2016. — Vol. 4 (2). — P. 129–152.

Yakovlev S. V. The Method of Artificial Space Dilation in Problems of Optimal Packing of Geometric Objects / S. V. Yakovlev // Cybernetics and Systems Analysis. — 2017. — Vol. 53 (5). — P. 825–832.

Pichugina O. S. Continuous Representations and Functional Extensions in Combinatorial Optimization / O. S. Pichugina, S. V. Yakovlev // Cybernetics and Systems Analysis. — 2016. — Vol. 52 (6). — P. 921–930.