Полиэдрально-сферические конфигурации в задачах дискретной оптимизации

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Яковлев, С.В., Пичугина, О.С., Яровая, О.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы оптимизации и оптимальное управление
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/180647
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации / С.В. Яковлев, О.С. Пичугина, О.В. Яровая // Проблемы управления и информатики. — 2019. — № 1. — С. 27-40. — Бібліогр.: 46 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-180647
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1806472025-02-23T20:10:22Z Полиэдрально-сферические конфигурации в задачах дискретной оптимизации Поліедрально-сферичні конфігурації в задачах дискретної оптимізації Polyhedral spherical configurations in discrete optimization problem Яковлев, С.В. Пичугина, О.С. Яровая, О.В. Методы оптимизации и оптимальное управление Выделен класс полиэдрально-сферических конфигураций как вписанных в гиперсферу конечных точечных конфигураций. Предложены подходы к определению параметров конфигураций. Рассмотрены свойства задач оптимизации на полиэдрально-сферических конфигурациях, сформулированы теоремы о существовании выпуклых продолжений для функций и оценку их минимумов. Результаты конкретизированы для класса квадратичных функций, заданных на перестановочных конфигурациях. Виділено клас поліедрально-сферичних конфігурацій як вписаних в гіперсферу скінченних точкових конфігурацій. Запропоновано підходи до визначення параметрів конфігурацій. Розглянуто властивості задач оптимізації на поліедрально-сферичних конфігураціях, сформульовано теореми про існування опуклих продовжень для функцій і оцінку їх мінімумів. Результати конкретизовані для класу квадратичних функцій, заданих на переставних конфігураціях. A class of polyhedral-spherical configurations as finite point configurations inscribed into a hypersphere is defined. Approaches to the determination of configuration parameters are proposed. The properties of optimization problems on polyhedral-spherical configurations are considered, theorems on the existence of convex extensions of functions and estimates of their lower bounds are formulated. The results are extended to the class of quadratic functions defined on permutation configurations. 2019 Article Полиэдрально-сферические конфигурации в задачах дискретной оптимизации / С.В. Яковлев, О.С. Пичугина, О.В. Яровая // Проблемы управления и информатики. — 2019. — № 1. — С. 27-40. — Бібліогр.: 46 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180647 519.85 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление
spellingShingle	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление Яковлев, С.В. Пичугина, О.С. Яровая, О.В. Полиэдрально-сферические конфигурации в задачах дискретной оптимизации Проблемы управления и информатики
description	Выделен класс полиэдрально-сферических конфигураций как вписанных в гиперсферу конечных точечных конфигураций. Предложены подходы к определению параметров конфигураций. Рассмотрены свойства задач оптимизации на полиэдрально-сферических конфигурациях, сформулированы теоремы о существовании выпуклых продолжений для функций и оценку их минимумов. Результаты конкретизированы для класса квадратичных функций, заданных на перестановочных конфигурациях.
format	Article
author	Яковлев, С.В. Пичугина, О.С. Яровая, О.В.
author_facet	Яковлев, С.В. Пичугина, О.С. Яровая, О.В.
author_sort	Яковлев, С.В.
title	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации
title_short	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации
title_full	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации
title_fullStr	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации
title_full_unstemmed	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации
title_sort	полиэдрально-сферические конфигурации в задачах дискретной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Методы оптимизации и оптимальное управление
url	https://nasplib.isofts.kiev.ua/handle/123456789/180647
citation_txt	Полиэдрально-сферические конфигурации в задачах дискретной оптимизации / С.В. Яковлев, О.С. Пичугина, О.В. Яровая // Проблемы управления и информатики. — 2019. — № 1. — С. 27-40. — Бібліогр.: 46 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT âkovlevsv poliédralʹnosferičeskiekonfiguraciivzadačahdiskretnojoptimizacii AT pičuginaos poliédralʹnosferičeskiekonfiguraciivzadačahdiskretnojoptimizacii AT ârovaâov poliédralʹnosferičeskiekonfiguraciivzadačahdiskretnojoptimizacii AT âkovlevsv políedralʹnosferičníkonfíguracíívzadačahdiskretnoíoptimízacíí AT pičuginaos políedralʹnosferičníkonfíguracíívzadačahdiskretnoíoptimízacíí AT ârovaâov políedralʹnosferičníkonfíguracíívzadačahdiskretnoíoptimízacíí AT âkovlevsv polyhedralsphericalconfigurationsindiscreteoptimizationproblem AT pičuginaos polyhedralsphericalconfigurationsindiscreteoptimizationproblem AT ârovaâov polyhedralsphericalconfigurationsindiscreteoptimizationproblem
first_indexed	2025-11-25T00:12:54Z
last_indexed	2025-11-25T00:12:54Z
_version_	1849719075222061056
fulltext	© С.В. ЯКОВЛЕВ, О.С. ПИЧУГИНА, О.В. ЯРОВАЯ, 2019 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 27 УДК 519.85 С.В. Яковлев, О.С. Пичугина, О.В. Яровая ПОЛИЭДРАЛЬНО-СФЕРИЧЕСКИЕ КОНФИГУРАЦИИ В ЗАДАЧАХ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Ключевые слова: дискретная оптимизация, конфигурация, полиэдр, гиперсфе- ра, выпуклое продолжение, оценка минимума. Введение Задачи комбинаторной и дискретной оптимизации занимают особое мес- то в теории сложных систем, поскольку позволяют отобразить дискретный характер параметров и процессов функционирования систем. Вопросам клас- сификации таких задач и современным методам их решения посвящены рабо- ты отечественных и зарубежных ученых [1–10]. При формализации широкого класса практических задач используется понятие комбинаторной конфигура- ции как отображения абстрактного множества произвольной природы в ко- нечное множество определенной структуры при выполнении заданного набо- ра ограничений [11]. Важное место в комбинаторной оптимизации занимают подходы, в которых объекты отображаются в арифметическое евклидово пространство с последую- щим использованием алгебро-топологических и тополого-метрических свойств полученных конечных точечных конфигураций [12–15]. Настоящая работа по- священа выделению класса полиэдрально-сферических конфигураций как впи- санных в гиперсферу конечных множеств арифметического евклидова простран- ства, которые также называют конечными точечными конфигурациями. С одной стороны, это позволило воспользоваться свойствами задач оптимизации на ги- персфере [16, 17]. С другой, удалось распространить и конкретизировать из- вестные теоретические результаты [18–20] для класса оптимизационных задач на различных классах комбинаторных конфигураций и получить их специфиче- ские свойства. 1. Основные направления исследования полиэдрально-сферических конфигураций Пусть nRE  — конечное множество точек арифметического евклидова пространства. Обозначим mJ множество первых m натуральных чисел, т.е. }....,,1{ mm J Множество E представим в виде },,{}...,,{ 1 m jm jxxxE J (1) где Em card — мощность ,E .),...,,( 1 m j n jj jxxx J В дальнейшем положим 1.>m Пусть EP conv — выпуклая оболочка множества ,E т.е. многогранник, множество вершин которого обозначим .vert P Введем следующие определения. Определение 1. Множество ,nRE  точки которого удовлетворяют заданным условиям  на их взаимное расположение, назовем точечной конфигурацией и обозначим ).,( E 28 ISSN 0572-2691 Задавая определенным образом систему ограничений , получим различные классы точечных конфигураций. Определение 2. Конечную точечную конфигурацию nRE назовем полиэд- рально-сферической, если существуют такие n n R )...,,( 1 и ,0r что для всех точек Ex выполняется условие .rx  (2) Выбор термина «полиэдрально-сферическая конфигурация» определяется представлением множества E как пересечения многогранника EP conv и ги- персферы ),( rS  , т.е. ),,( rSPE   (3) где }.:{),( rxRxrS n  Для полиэдрально-сферической конфигурации используем такое же обозна- чение, что и для конечной точечной конфигурации ,E поскольку эти множества совпадают при выполнении (3). Заметим, что множество точек полиэдрально-сферической конфигурации E совпадает со множеством вершин своей выпуклой оболочки (многогранника ).P В работе [18] впервые введено понятие вершинно-расположенного множества, удовлетворяющего указанному свойству. Определение 3. Конечное множество nRE  назовем вершинно-расположен- ным, если .convvert EE  Размерностью полиэдрально-сферической конфигурации E именуем мини- мальную размерность линейного многообразия пространства ,nR содержащего .E Полиэдрально-сферическую конфигурацию E размерности m обозначим .mE Базисом полиэдрально-сферической конфигурации mE определим совокупность любых m аффинно-независимых точек этой конфигурации. Полиэдрально-сфе- рическую конфигурацию nm RE  назовем полномерной, если .nm  Таким образом, полиэдрально-сферическая конфигурация nRE  предста- вима в виде (1), и для всех точек Ex существуют такие nR и ,0r что вы- полняется равенство (2). Точку nR назовем центром полиэдрально-сфери- ческой конфигурации ,E а 0r — ее радиусом. Центр  и радиус r назовем параметрами полиэдрально-сферической конфигурации. Чтобы подчеркнуть, ка- кими параметрами задается конкретная конфигурация, используем обозначе- ние ).,( rE  В общем случае одна и та же полиэдрально-сферическая конфигура- ция может иметь различные параметры, поскольку равенство (2) может выпол- няться при различных  и .r Выберем минимальное значение 0ˆ r и такое ,ˆ nR что для всех точек Ex выполняется условие .̂ˆ rx  (4) Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 29 Полиэдрально-сферическую конфигурацию ,E для представления которой ис- пользуется минимальный радиус ,r̂ обозначим ).ˆ,ˆ(ˆ rE  Ясно, что для полномер- ной полиэдрально-сферической конфигурации представление )ˆ,ˆ(ˆ rE  единственно. Исследование полиэдрально-сферических конфигураций предполагает рас- смотрение и решение следующих задач. Прежде всего, требуется идентифициро- вать, является ли заданная точечная конфигурация nRE  полиэдрально-сфе- рической. Такую задачу назовем задачей структурной идентификации. Для поли- эдрально-сферической конфигурации ),( rE  определим ее параметры, в том числе минимальный радиус (задача параметрической идентификации). Различные ограничения на взаимное расположение точек полиэдрально-сфе- рических конфигураций позволяют выделять их специальные классы (задача классификации). Представляет интерес задача аналитического описания полиэдрально-сфери- ческой конфигурации. С одной стороны, параметрическая идентификация ),( rE  определяет и ее аналитическое описание в виде уравнения гиперсферы и системы линейных неравенств, описывающих многогранник. С другой стороны, суще- ствуют методы непрерывного представления дискретных множеств в виде иных аналитических зависимостей [15, 21, 22]. Важнейшим направлением исследований является рассмотрение задач опти- мизации на полиэдрально-сферических конфигурациях. Данный класс задач отно- сится к задачам дискретной оптимизации. Классические методы дискретного про- граммирования, такие как методы ветвей и границ, методы отсечений, методы ветвей и отсечений, основаны, как правило, на использовании двух особенностей конечных точечных конфигураций — их разложение по параллельным плоско- стям и получение оценок выпуклых функций с помощью решения полиэдральных релаксационных задач. Однако разложение по параллельным плоскостям — дале- ко не единственный способ декомпозиции конечных точечных конфигураций на попарно непересекающиеся подмножества. Например, любая конечная точечная конфигурация разлагается по семейству вложенных гиперсфер, что позволяет ис- пользовать как традиционную полиэдральную, так и сферическую релаксации дискретных задач [23–26]. 2. Свойства полиэдрально-сферических конфигураций Простейшим примером полиэдрально-сферической конфигурации является множество вершин симплекса. Напомним, что n-симплексом в пространстве nR называется многогранник, являющийся выпуклой оболочкой 1n точек, которые не лежат в )1( n -мерной плоскости. Множество вершин симплекса является пол- номерной полиэдрально-сферической конфигурацией ),ˆ,ˆ(ˆ rE  а ее параметры r̂,̂ представлены в [27]. Для описания полиэдрально-сферических конфигураций воспользуемся по- нятием мультимножества. Обозначим J множество натуральных чисел. Определение 4. Мультимножеством Â на множестве A назовем упорядо- ченную пару },,{ ~ kAA  где .: JAk При этом множество A называют осно- вой мультимножества ,Â а число J)(ak — кратностью элемента .Aa Пусть элементами основы мультимножества }~...,,~{ ~ 1 maaA  являются дей- ствительные числа, а }....,,{ 1 laaA Обозначим )}(...,,)({) ~ ( 1 lakak=Ak вектор кратностей элементов мультимножества .Â Над мультимножествами определены операции объединения, пересечения, дополнения и др. В частности, объединени- 30 ISSN 0572-2691 ем мультимножеств Â и B̂ называется мультимножество, состоящее из всех элементов, которые присутствуют хотя бы в одном из мультимножеств и крат- ность которых равна максимальной кратности соответствующих элементов в объ- единяемых мультимножествах. Рассмотрим множество E вида (1). Точке ,),...,,( 1 m j n jj jxxx J поставим в соответствие мультимножество },{)( n j i j ixxG J ее координат. Назовем )( jxG индуцирующим мультимножеством точки .nj REx  Сформируем мультимножество  m j jGG 1  как объединение мультимножеств . ),( m jj JjxGG  Представим мультимножество G в виде },...,,{ 1  ggG 11 ,   Jkgg kk , его основу обозначим },,{  JieA i где . , 11   Jiee ii Назовем G индуци- рующим мультимножеством множества .nRE  Теорема 1. Если индуцирующие мультимножества )( jxG точек ,nj REx  ,mj J совпадают, то E — полиэдрально-сферическая конфигурация, макси- мальная размерность которой равна .1n С учетом способа формирования мультимножества G имеет место следую- щее следствие данной теоремы. Следствие 1. Если индуцирующее мультимножество G полиэдрально-сфери- ческой конфигурации содержит n элементов, то E — полиэдрально-сферическая конфигурация, максимальная размерность которой равна .1n Определение 5. Полиэдрально-сферическую конфигурацию ,E удовлетворя- ющую условиям теоремы 1, назовем перестановочной. Индуцирующее мультимножество перестановочной конфигурации имеет вид }....,,{ 1 nni ggigG  J (5) Заметим, что перестановочная конфигурация, порожденная заданным муль- тимножеством ,G определена не единственным образом. Например, все не одно- точечные подмножества множества E могут быть перестановочными конфигу- рациями, порожденными этим же мультимножеством. Могут также существовать и надмножества множества ,E обладающие этим же свойством. Выделим из се- мейства перестановочных конфигураций, порожденных мультимножеством ,G ту, что является подмножеством каждой из них. Назовем такую конфигурацию базовой перестановочной конфигурацией, порожденной мультимножеством ,G и обозначим ее .GE Имеет место следующее представление: }.}...,,{:{ 1 GxxRxE n n G  Представление GE как полиэдрально-сферической конфигурации )ˆ,ˆ(ˆ rEG  минимального радиуса имеет параметры .ˆ,)ˆ...,,ˆ(ˆ,)ˆ(ˆ / 1 000 2/1 1 2 0 ngRgr n i i n n i i                     Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 31 В дальнейшем основное внимание уделим исследованию базовой перестано- вочной конфигурации .GE Для произвольной перестановочной конфигурации GEE  предлагаемые ниже результаты требуют соответствующих уточнений и обобщений. Выпуклой оболочкой перестановочной конфигурации GE является описыва- емый системой [28] так называемый общий перестановочный многогранник GG EEP conv)(  ,, 111     i i i i n i i n i i gxgx (6) где ,card  а суммирование проводится по всевозможным подмноже- ствам . nJ Теорема 2. Если основа индуцирующего мультимножества равна },,{ 21 ggA ,21 gg  то ),( rEE  — полиэдрально-сферическая конфигурация с параметрами . 2 ,R)...,,(, 2 21 000 12 gg n gg r n     (7) Если E — полномерная конфигурация, удовлетворяющая условиям теоремы 2, то выражения (7) задают ).ˆ,ˆ(ˆ rEG  Частным случаем такой полиэдрально-сфери- ческой конфигурации является булево множество .}1,0{ n nB  Параметры такой конфигурации при минимальном радиусе имеют значения , 2 1 ...,, 2 1 ˆ, 2 ˆ nR n r        а ее выпуклой оболочкой является единичный гиперкуб }.,10{ conv)( ninn ixBBP J Пусть nRE  — полиэдрально-сферическая конфигурация. Очевидно, что любое подмножество EE  также является полиэдрально-сферической конфи- гурацией. Рассмотрим семейство },{ ki iL J многообразий пространства ,nR та- ких что .,,,, jijiEELEEEE mjiii Ji i k   J Такое представление задает разложение полиэдрально-сферической конфи- гурации по семейству },{ ki iE J полиэдрально-сферических конфигураций меньшей мощности. Наиболее распространенным является разложение nRE  по линейным много- образиям. Прежде всего, это связано с достаточно простым способом определения параметров ),( i i r полиэдрально-сферических конфигураций }.),,({ ki i i irE J Действительно, рассмотрим разложение конфигурации n i i i RrE  ),( по семей- ству гиперплоскостей },{ ki iT J вида .0 1   i n j jij bxa 32 ISSN 0572-2691 Тогда n i i i RrE  ),( будет иметь параметры , 1 2 0 i n j i jiji barr    ),...,,( 1 i n ii  ,)( 11 020    n t iti n t titj i j aba ., nk ji JJ  Если для E использовано представление ),(ˆ 0 0 rE  минимального радиуса, то данные формулы задают представления , ),,(ˆ ki i ii JirEE  минимальных радиусов полиэдрально-сферических конфигураций, полученных в результате разложения E по гиперплоскостям, в том случае если их размерности на единицу меньше размерности E . 3. Экстремальные свойства функций на полиэдрально-сферических конфигурациях Сформулируем задачу оптимизации функции 1n RR  : на множестве точек полиэдрально-сферической конфигурации nRE  в следующей постановке: min,)(  x ,Dx (8) где множество допустимых решений D задается системой ограничений ,Ex (9) , ,0)( ki ix J (10) ,\ ,0)( kmi ix JJ (11) а функции ,),(),( mi ixx J определены на .E Решение задачи (8)–(11) сводится к определению такой точки ,Dx  что ),(min) x(x Dx    Задача (8)–(11) является задачей математического программирования. При этом ограничения (9) называют прямыми, а (10), (11) — функциональными. Свойства задачи (8)–(11) определяются выбором прямых ограничений (9) и аналитическим видом функций ,),(),( mi ixx J в описании области допусти- мых решений .D Заметим, что множество ,D как подмножество ,E является полиэдрально-сфе- рической конфигурацией. Формирование прямых и функциональных ограничений в задаче (8)–(11) является условным. Действительно, полиэдрально-сферическая конфигурация )( G,E задается системой ограничений  , определяющих способ формирования точек этой конфигурации. Поэтому, включая некоторые из ограничений (10), (11) в систему  , можно изменять структуру множества ,Ε а значит, и прямые ограничения задачи. Отметим некоторые важные свойства задач оптимизации на полиэдрально-сфе- рических конфигурациях. Пусть функция )(x задана на ).,( rEE  Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 33 Определение 6. Выпуклую функцию ),( ~ x определенную на выпуклом мно- жестве ,ΕX  назовем выпуклым продолжением функции )(x на ,X если )()( ~ xx  для любых .Ex Если функция )( ~ x сильно выпукла на X с параметром ,0  то такое продолжение назовем сильно выпуклым. Для функций )(x и ),( ~ x совпадающих на множестве ,X используем обозначение ).()( ~ xx Е  На полиэдрально-сферическую конфигурацию распространяются свойства выпуклых продолжений для функций, заданных на вершинно-расположенных множествах. Поэтому утверждение следующей теоремы является следствием со- ответствующих результатов теории выпуклых продолжений [18, 19]. Теорема 3. Для любой функции 1: RE  существует дифференцируемое выпуклое продолжение )( ~ x на . conv EP  Теорема 4. Для любой функции 1: RE  и для любого 0  существует дифференцируемое сильно выпуклое продолжение )( ~ x на .P Теорема 5. Для любой выпуклой функции )()( 2 nRCx  и для любого 0 существует сильно выпуклое продолжение с параметром 0 на выпуклый ком- пакт ),,( rEX  которое имеет вид ).()()( ~ 22 rxxx  (12) Подходы к построению выпуклых продолжений для функций, заданных на гиперсфере, рассмотрены в [29]. Сформулируем следующие теоремы, утверждения которых позволяют полу- чить достаточные условия и оценки минимума функций, заданных на полиэд- рально-сферических конфигурациях. Доказательства теорем следуют из свойств выпуклых функций, заданных на вершинно-расположенных множествах [20]. Теорема 6. Пусть функция 1: ~ RX  является выпуклым дифференцируе- мым продолжением функции 1: RE  на выпуклое множество .PX  Тогда для любого Xx ~ ),),~( ~ (min)~),~( ~ ()~( ~ )(min xxxxxx PxEx   где )(' x — градиент функции )(x в точке .x Точку Xx ~ можно выбрать как решение задачи выпуклого программи- рования ).( ~ minarg~ xx Рx   (13) С другой стороны, поскольку в условиях теоремы 4 множество X является про- извольным выпуклым надмножеством множества ,P то в случае, если ,),( XrS  в качестве точки Xx ~ можно рассматривать решение задачи оптимизации на гиперсфере ).( ~ minarg~ ),( xx rSx   (14) Рассмотрим класс сильно выпуклых функций с параметром .0 34 ISSN 0572-2691 Теорема 7. Пусть функция )( ~ x является сильно выпуклым продолжением функции )(x на .P Тогда ,min)( ~ )(min 2 yxyx ExEx   где ).( ~ minarg* yy Py   Теорема 8. Пусть функция )( ~ x является сильно выпуклым с параметром  дифференцируемым продолжением функции )(x на выпуклое замкнутое множе- ство .ЕХ  Тогда для любого Xy .)( ~ 2 1 min 2 )( ~ 4 1 )( ~ )(min 2 yyxyyx ExEx       Применим приведенные выше результаты для исследования класса задач дискретной оптимизации на полиэдрально-сферических конфигурациях ).,( rEE  Осуществим эквивалентные преобразования задачи (8)–(11). Для этого пред- ставим ограничения–равенства в виде .\ ,0)( ,0)( kmi i JJix x   (15) Для функций ,),(),( mi ixx J и ,\ ),( kmi JJix  стоящих в левых ча- стях ограничений–неравенств (15), построим выпуклые продолжения на выпуклое множество . conv EX  Соответственно, ),()( ~ xx E  , ),()(~ mi E i Jixx  .\ ),()(~ 2 mkmkmi E i JJixx   C учетом приведенных выше результатов о существовании выпуклых про- должений для функций, заданных на полиэдрально-сферических конфигурациях, сформулируем следующую теорему, устанавливающую связь общей задачи опти- мизации на полиэдрально-сферических конфигурациях с задачей оптимизации выпуклой функции на соответствующей конфигурации, подчиненной выпуклым функциональным ограничениям. Теорема 9. Пусть E — полиэдрально-сферическая конфигурация. Тогда ),( ~ minarg)(minarg ~ xx GxGx   где },\,0)(, ,0)(:{= kmiki JJixJixExG  }.,0)(~:{= ~ 2 kmi JixExG  Аналогичные эквивалентные постановки можно сформулировать для диффе- ренцируемых и сильно выпуклых продолжений функций .),(),( mi ixx J Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 35 С теоретической точки зрения теоремы 3–5 обосновывают существование выпуклых, сильно выпуклых и дифференцируемых продолжений для произволь- ных функций, заданных на полиэдрально-сферических конфигурациях. Особый интерес представляет теорема 9, поскольку позволяет привлечь аппарат теории выпуклого программирования для решения вспомогательных задач, возникающих в различных алгоритмах дискретной оптимизации. При этом возникает задача по- строения искомых продолжений ),( ~ x решение которой зависит от вида исход- ной функции )(x и класса рассматриваемых полиэдрально-сферических конфи- гураций. 4. Построение выпуклых продолжений для некоторых функций на полиэдрально-сферических конфигурациях Приведенные ниже результаты расширяют полученные в работах [24–26, 29] свойства сферически расположенных множеств на класс полиэдрально-сфери- ческих конфигураций. Пусть на полиэдрально-сферической конфигурации ),( rE  задана квадра- тичная функция ),,(),()( xbxCxx  (16) где nnijcC  ][ — невырожденная симметричная nn -матрица, а b — n-мерный вектор. Рассмотрим задачу минимизации функции )(x на ),( rE  в виде ).(minarg ),( xx rEx    (17) Для квадратичной функции )(x можно усилить утверждения теоремы 3 и конкретизировать вид выпуклого продолжения )( ~ x на все пространство .nR Теорема 10. Пусть на полиэдрально-сферической конфигурации ),( rE  задана квадратичная функция )(x вида (16). Тогда существует выпуклое про- должение dxbxxСx ~ ), ~ (), ~ ()( ~  функции )(x на ,nR где nnijcC  ]~[ ~ — симметричная положительно-полуопре- деленная матрица, b ~ — n-мерный вектор, d ~ — константа. Построение выпуклого продолжения в nR для класса квадратичных функций ),(x заданных на ),,( rE  основывается на следующих эквивалентных преобра- зованиях: ;<1,2)( 2 1 2 1 2 , 1 1 22 ),( njirxxxxxx n k k n jik k n k kkkji rE ji                     .2 2 1 2 1 1 2 ),( 2 rxxx n k k n ik k n k kkk rE i        Осуществляя в соответствии с приведенными выражениями такие преобразо- вания для функции (16), имеем 36 ISSN 0572-2691 ).()()( ~ 22 0 : rxccxx ij ji ii сi ii             Обозначим . 0 : ij ji ii сi cc ii    Тогда для функции dxbxxСx ~ ), ~ (), ~ ()( ~  имеем ),(= ~ ,2 ~ , ~ 22 rdbbIСС  (18) где I — единичная матрица. При этом в соответствии c теоремой 5 для любого 0 квадратичная функ- ция 2 )( ~  xx будет сильно выпуклой с параметром не меньше  . Выделение класса полиэдрально-сферических конфигураций позволяет кон- кретизировать утверждения теорем 6–8. Рассмотрим перестановочную конфигу- рацию GE и соответствующий перестановочный многогранник GG EEP conv)(  , описываемый системой линейных уравнений и неравенств (6). Тогда имеют место следующие утверждения, вытекающие из теорем 6–8 с учетом свойств перестано- вочных конфигураций. Теорема 11. Пусть )( ~ x — сильно выпуклое продолжение с параметром 0 функции )(x на )( GEP и ).( ~ minarg )( * x=x GEPx   Тогда ,)()( ~ )(min 1 2        n i i Ex gxxx i G где последовательность ,},...,,{ 1 nin J ji  ,,, jiJji n  такова, что .... 1      n xx Теорема 12. Пусть )( ~ x — дифференцируемое сильно выпуклое продолже- ние с параметром 0 функции )(x на ).( GEP Тогда для любой точки )(~ GEPx имеет место оценка , )~( )~()~),~( ~ ()~( ~ )(min 11 2 i n i n i i Ex g x x gxxxxx i i G         где последовательность ,},...,,{ 1 nin J ji  ,,, jiJji n  такова, что .~2 )~( ...~2 )~( 1 1 n n x x x x x x           Теорема 13. Для того чтобы )...,,( 1   nxxx была точкой минимума функции )(x на ,GE достаточно, чтобы существовали такое дифференцируемое выпуклое продолжение )( ~ x на )( GEP и такая последовательность ,},...,,{ 1 nin J ji  ,,, jiJji n  что ...., )( ~ ... )( ~ 1 1               n n xx x x x x Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 37 Осуществим конкретизацию теорем 11–13 для задачи оптимизации (17) квад- ратичной функции )(x на перестановочной конфигурации .GE Теорема 14. Для того чтобы )...,,( 1   nxxx была точкой минимума функ- ции )(x вида (16) на перестановочной конфигурации ),ˆ,ˆ(ˆ rEG  порожденной ин- дуцирующим мультимножеством G вида (5), достаточно, чтобы существовала такая последовательность ,},...,,{ 1 nin J ji  ,,, jiJji n  что ,...,, ~~ )()~~( 111 11 1         njjjji xxJjbbggccg njj n i ii (19) где матрица nnijcC  ]~[ ~ и вектор ) ~ ...,, ~ ( ~ 1 nbbb  определяются выражениями (18), а ,ˆ / 1 0 ng n i i            .)ˆ(ˆ 2/1 1 2 0            n i igr Следствие 2. Пусть последовательность ,},...,,{ 1 nin J ji  ,, nJji  ,ji  такова, что n bb   ~ ... ~ 1 и система неравенств (19) совместна. Тогда ре- шение задачи (17) для перестановочной конфигурации ),( rEG  с параметрами ,)...,,( 00 nR ,/ 1 0 ng n i i            2/1 1 2 0)(            n i igr имеет вид )....,,( 1 n aax    Следствие 3. Пусть ),()( xCxx  и последовательность ,},...,,{ 1 nin J ji  ,, nJji  ,ji  такова, что .,,,~...~ 11 jiJjJicc nnjj ii    Тогда решение задачи (17) для перестановочной конфигурации ),( rEG  представимо в виде )....,,( 1 n aax    Другие свойства полиэдрально-сферических конфигураций, в частности пути трансформации произвольных конечных точечных конфигураций в полиэдраль- но-сферические, исследованы в работах [30, 31]. Такой подход позволяет приме- нять полученные в данной статье свойства полиэдрально-сферических конфигу- раций к решению комбинаторных задач общего вида. Заключение Описанные в настоящей работе результаты являются теоретической основой для разработки новых подходов к решению задач дискретной оптимизации, осно- ванных на исследовании структуры конечных точечных конфигураций и свойств функций, заданных на таких конфигурациях. Структура полиэдрально-сферичес- ких конфигураций, кроме основного требования принадлежности гиперсфере, определяется характерными ограничениями для различных специальных классов дискретных множеств. В качестве примеров укажем множества перестановок с повторениями и без них, перестановок со знаком, четных и нечетных перестано- вок, булево множество, множества булевых матриц, специальные множества раз- мещений и др. Распространение приведенных результатов на указанные классы позволяет получить новые свойства соответствующих задач дискретной оптими- зации. При этом представляет интерес рассмотрение дополнительных линейных и нелинейных ограничений [32]. 38 ISSN 0572-2691 Смежным направлением исследований является решение оптимизационных задач геометрического проектирования [12], связанных с отображением и преоб- разованием геометрической информации при синтезе сложных систем. В рабо- тах [33, 34] введено конфигурационное пространство геометрических объектов. Это позволило выделить комбинаторную структуру задач размещения, упаковки, компоновки и покрытия как отображения конечного множества геометрических объектов на соответствующее конфигурационное пространство [35, 36] и предло- жить эквивалентные математические модели задач геометрического проектирова- ния как задач комбинаторной оптимизации [37–40]. Другие практические приложения основаны на возможности формулировки исходной задачи в форме (8)–(11), что непосредственно связано с отображением дискретных объектов на пространство их параметров. Этот процесс на сегодняш- ний день недостаточно формализован и требует разработки специальных подхо- дов. В частности, такой подход реализован при решении задач балансировки масс вращающихся частей [41], проектировании чипов в радиоэлектронике [42], кла- стерном анализе [43, 44]. Представляет также интерес применение свойств полиэдрально-сферических конфигураций в генетических алгоритмах комбинаторной оптимизации при ре- шении вспомогательных задач [45, 46]. С.В. Яковлев, О.С. Пічугіна, О.В. Ярова ПОЛІЕДРАЛЬНО-СФЕРИЧНІ КОНФІГУРАЦІЇ В ЗАДАЧАХ ДИСКРЕТНОЇ ОПТИМІЗАЦІЇ Виділено клас поліедрально-сферичних конфігурацій як вписаних в гіперсферу скінченних точкових конфігурацій. Запропоновано підходи до визначення па- раметрів конфігурацій. Розглянуто властивості задач оптимізації на поліед- рально-сферичних конфігураціях, сформульовано теореми про існування опук- лих продовжень для функцій і оцінку їх мінімумів. Результати конкретизовані для класу квадратичних функцій, заданих на переставних конфігураціях. Ключові слова: дискретна оптимізація, конфігурація, поліедр, гіперсфера, опукле продовження, оцінка мінімуму. S.V. Yakovlev, O.S. Pichugina, O.V. Yarovaya POLYHEDRAL SPHERICAL CONFIGURATIONS IN DISCRETE OPTIMIZATION PROBLEMS A class of polyhedral-spherical configurations as finite point configurations inscribed into a hypersphere is defined. Approaches to the determination of configuration pa- rameters are proposed. The properties of optimization problems on polyhedral- spherical configurations are considered, theorems on the existence of convex exten- sions of functions and estimates of their lower bounds are formulated. The results are extended to the class of quadratic functions defined on permutation configurations. Keywords: discrete optimization, configuration, polyhedron, hypersphere, convex extension, bound of a minimum. 1. Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Heidelberg; New York : Springer, 2018. 698 p. https://doi.org/10.1007/978-3-662-56039-6. 2. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mi- neola : Dover Publications, 2013. 528 p. https://doi.org/10.1007/978-3-662-56039-6 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 1 39 3. Pardalos P.M., Du D-Z., Graham R.L. (Eds.) Handbook of combinatorial optimization. New York : Springer, 2013. 3409 p. https://doi.org/10.1007/978-1-4419-7997-1. 4. Schrijver A. Combinatorial optimization: polyhedra and efficiency. Springer Science and Busi- ness Media, 2002. 2024 p. 5. Burkard R.E. Quadratic assignment problems. Handbook of combinatorial optimization. 2013. Vol. 5, N 1. P. 2741–2814. https://doi.org/10.1007/978-1-4419-7997-1_22. 6. Sergienko I.V., Shilo V.P. Modern approaches to solving complex discrete optimization prob- lems. Journal of Automation and Information Sciences. 2016. Vol. 48, N 1. P. 15–24. https:// doi.org/10.1615/JAutomatInfScien.v48.i1.30. 7. Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741. https://doi. org/10.1007/s10559-009-9134-0. 8. Згуровский М.З., Павлов А.А. Труднорешаемые задачи комбинаторной оптимизации в планировании и принятии решений. К. : Наук. думка, 2016. 115 с. 9. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations. Journal of Automation and Infor- mation Sciences. 2008. Vol. 40, N 6. P. 27–42. https://doi.org/10.1615/JAutomatInfScien.v40.i12.30. 10. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization prob- lems. Springer Optimization Methods and its Applications. 2017. Vol. 130. P. 239–250. https:// doi.org/10.1007/978-3-319-68640-0_11. 11. Berge C. Principes de combinatoire. Paris : Dunod, 1968. 146 p. 12. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. К. : Наук. думка, 1986. 268 с. 13. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. К. : Ін-т си- стемн. дослідж. освіти, 1993. 188 с. 14. Стоян Ю.Г., Яковлев С.В., Пичугина О.С. Евклидовы комбинаторные конфигурации. Харь- ков : Константа, 2017. 404 с. 15. Пичугина О.С., Яковлев С.В. Непрерывные функциональные представления в задачах дис- кретной оптимизации. Харьков : Золотая миля, 2018. 312 c. 16. Ferreira O.P., Iusem A.N., Németh S.Z. Concepts and techniques of optimization on the sphere. TOP. 2014. Vol. 22, N 3. Р. 1148–1170. https://doi.org/10.1007/s11750-014-0322-3. 17. Gräf M., Hielscher R. Fast global optimization on the torus, the sphere, and the rotation group. SIAM J. Optim. 2015. Vol. 25, N 1. Р. 540–563. http://doi.org/10.1137/130950070. 18. Yakovlev S.V. The theory of convex continuations of functions on vertices of convex polygons. Computational Mathematics and Mathematical Physics. 1994. Vol. 34, N 7. P. 959–965. https://dl.acm.org/citation.cfm?id=196926. 19. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Springer Optimization Methods and its Applications. 2017. Vol. 130. P. 567–584. http://doi.org/10.1007/ 978-3-319-68640-0_27. 20. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics. 1989. Vol. 25, N 3. P. 385–391. http://dx.doi.org/10.1007/BF01069996. 21. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in combina- torial optimization. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 921–930. http://doi.org/10.1007/s10559-016-9894-2. 22. Pichugina O.S., Yakovlev S.V. Functional and analytic representations of the general permuta- tions. Eastern-European Journal of Enterprise Technologies. 2016. Vol. 1, N 4. P. 27–38. http:// doi.org/10.15587/1729-4061.2016.58550. 23. Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer optimization. Cybernetics and Systems Analysis. 1993. Vol. 29, N 5. P. 727–734. https://doi.org/10.1007/BF01125802. 24. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in .nR Cybernetics and Systems Analysis. 1991. Vol. 27, N 4. P. 562–567. http://dx.doi.org/10. 1007/BF01130367. 25. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhe- dral-spherical sets. Cybernetics and Systems Analysis. 2018. Vol. 54, N 1. P. 385–391. https:// doi.org/10.1007/s10559-018-0011-6. 26. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: theory and applications. In 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). Pro- ceedings, 2017. P. 1167–1175. https://doi.org/10.1109/UKRCON.2017.8100436. https://doi.org/10.1007/978-1-4419-7997-1 https://www.scopus.com/record/display.uri?eid=2-s2.0-85007046876&origin=recordpage https://doi.org/10.1007/978-1-4419-7997-1_22 https://www.scopus.com/authid/detail.uri?origin=AuthorProfile&authorId=7006221914&zone= https://www.scopus.com/authid/detail.uri?origin=AuthorProfile&authorId=7006221914&zone= https://www.scopus.com/authid/detail.uri?origin=AuthorProfile&authorId=35085165300&zone= https://www.scopus.com/authid/detail.uri?origin=AuthorProfile&authorId=35085604400&zone= https://www.scopus.com/record/display.uri?eid=2-s2.0-70350337920&origin=resultslist&sort=plf-f&src=s&sid=4a62c507eaef419fa0cf039d92af160c&sot=autdocs&sdt=autdocs&sl=18&s=AU-ID%2835085165300%29&relpos=7&citeCnt=12&searchTerm= https://www.scopus.com/record/display.uri?eid=2-s2.0-70350337920&origin=resultslist&sort=plf-f&src=s&sid=4a62c507eaef419fa0cf039d92af160c&sot=autdocs&sdt=autdocs&sl=18&s=AU-ID%2835085165300%29&relpos=7&citeCnt=12&searchTerm= https://doi.org/10.1615/JAutomatInfScien.v40.i12.30 https://doi.org/10.1007/s11750-014-0322-3 http://doi.org/10.1137/130950070 https://dl.acm.org/citation.cfm?id=196926 http://doi.org/10.1007/978-3-319-68640-0_27 http://doi.org/10.1007/978-3-319-68640-0_27 http://dx.doi.org/10.1007/BF01069996 http://doi.org/10.1007/s10559-016-9894-2 https://doi.org/10.1007/BF01125802 http://dx.doi.org/10.1007/BF01130367 http://dx.doi.org/10.1007/BF01130367 https://doi.org/10.1007/s10559-018-0011-6 https://doi.org/10.1007/s10559-018-0011-6 https://doi.org/10.1109/UKRCON.2017.8100436 40 ISSN 0572-2691 27. Schneider P., Eberly D.H. Geometric tools for computer graphics. Amsterdam : Morgan Kauf- mann, 2002. 1056 p. 28. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комби- наторная теория многогранников). М. : Наука, 1981. 344 с. 29. Stoyan Y.G., Yakovlev S.V., Emets O.A., Valuiskaya O.A. Construction of convex continuations for functions defined on hypersphere. Cybernetics and Systems Analysis. 1998. Vol. 34, N 2. P. 176–184. https://doi.org/10.1007/BF02742066. 30. Yakovlev S., Pichugina O., Yarovaya O. On polyhedral-spherical configurations: modelling and optimization. In 2018 International Conference on Innovations in Engineering, Technology and Sciences (ICIETS). Proceedings, Karnataka, India, 2018. P. 100–105. 31. Yakovlev S., Pichugina O., Yarovaya O. On optimization problems on the polyhedral-spherical configurations with their properties. In 2018 IEEE First International Conference on System Analysis and Intelligent Computing (SAIC 2018). Proceedings, Kyiv, 2018. P. 94–100. http:// dx.doi.org/10.1109/SAIC.2018.8516801. 32. Yakovlev S.V., Valuiskaya O.A. Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukrainian Mathematical Journal. 2001. Vol. 53, N 9. P. 1535–1545. https://doi.org/10.1023/A:1014374926840. 33. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726. https://doi.org/10.1007/s10559-018-0073-5. 34. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their formali- zation. Journal of Automation and Information Sciences. 2018. Vol. 50, N 5. P. 73–84. https://doi.org/10.1615/JAutomatInfScien.v50.i9.30. 35. Yakovlev S.V. The method of artificial space dilation in problems of optimal packing of geomet- ric objects. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 725–731. https://doi. org/10.1007/s10559-017-9974-y. 36. Yakovlev S., Kartashov O. System analysis and classification of spatial configurations. In 2018 IEEE First International Conference on System Analysis and Intelligent Computing (SAIC 2018) Proceedings, Kyiv, 2018. P. 90–93. https://doi.org/10.1109/SAIC.2018.8516760. 37. Combinatorial configurations in balance layout optimization problems. I.V. Grebennik, A.A. Kovalenko, T.E. Romanova, I.A. Urniaieva, S.B. Shekhovtsov. Cybernetics and Systems Analysis. 2018. Vol. 54, N 2. P. 221–231. https://doi.org/10.1007/s10559-018-0023-2. 38. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications. 2010. Vol. 43, N 5. P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003. 39. Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungari- ca. 1989. Vol. 53, N 3. P. 253–262. https://doi.org/10.1007/BF01953365. 40. Shekhotsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in design of control and monitoring systems. Avtomatica I Telemekhanika. 1989. N 5. P. 160–168. 41. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distri- buted masses. Energomashinostroenie. 1982. N 2. P. 4–5. https://www.osti.gov/etdeweb/ biblio/6490782. 42. Pichugina O. Placement problems in chip design: modeling and optimization. In 2017 IEEE 4th International Scientific-Practical Conference Problems of Infocommunications Science and Technology. Proceedings, Kharkiv, 2017. P. 465–473. https://doi.org/10.1109/INFOCOMMST.2017. 8246440. 43. Farzad B., Pichugina O., Koliechkina L. Multi-layer community detection. In 2018 International Conference on Control, Artificial Intelligence, Robotics and Optimization (ICCAIRO) — Pro- ceedings, Prague, 2018. P. 101–108. 44. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cybernetics and Systems Analysis. 2008. Vol. 43, N 3. P. 333–340. https://doi.org/10.1007/s10559-008-9007-y. 45. Yakovlev S., Kartashov O., Yarovaya O. On class of genetic algorithms in optimization problems on combinatorial configuration. In 2018 IEEE XIІI International Scientific and Technical Confer- ence on Computer Sciences and Information Technologies (CSIT 2018). Proceedings, Lviv, 2018. P. 374–377. https://doi.org/10.1109/STC-CSIT.2018.8526. 46. Yakovlev S., Kartashov O., Pichugina O., Koliechkina L. The Genetic Algorithms in Opt i- mization Problem on Combinatorial Configurations. In 2018 International Conference on Innovations in Engineering, Technology and Sciences (ICIETS). Proceedings, Karnataka, India, 2018. P. 106–111. Получено 15.05.2018 https://doi.org/10.1007/BF02742066 https://doi.org/10.1023/A:1014374926840 https://doi.org/10.1007/s10559-018-0073-5 https://doi.org/10.1615/JAutomatInfScien.v50.i9.30 https://doi.org/10.1109/SAIC.2018.8516760 https://doi.org/10.1007/s10559-018-0023-2 https://doi.org/10.1016/j.comgeo.2009.12.003 https://doi.org/10.1007/BF01953365 https://www.osti.gov/etdeweb/biblio/6490782 https://www.osti.gov/etdeweb/biblio/6490782 https://doi.org/10.1109/INFOCOMMST.2017.8246440 https://doi.org/10.1109/INFOCOMMST.2017.8246440 https://doi.org/10.1007/s10559-008-9007-y http://dx.doi.org/10.1109/STC-CSIT.2018.8526746

Полиэдрально-сферические конфигурации в задачах дискретной оптимизации

Institution

Ähnliche Einträge