Оптимізація на загальній множині перестановок зі знаком
A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They in...
Gespeichert in:
| Datum: | 2017 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2017
|
| Schlagworte: | |
| Online Zugang: | http://journal.iasa.kpi.ua/article/view/103892 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
Institution
System research and information technologies| _version_ | 1856543222393733120 |
|---|---|
| author | Pichugina, Oksana S. |
| author_facet | Pichugina, Oksana S. |
| author_sort | Pichugina, Oksana S. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2018-04-04T16:37:16Z |
| description | A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They include set’s cardinality, an irreducible H-representation of the polyhedron, its dimension, the vertex and adjacency vertex criteria, and the number of combinatorially nonisomorphic polyhedra of a fixed dimension. The behavior of some classes of functions over the general signed permutation set is investigated. Functional-analytical representations of this set are constructed including polyhedral-superspherical and strict superspherical. Explicit solutions of a linear problem and a projection problem over the general signed permutation set are presented. The research allows applying continuous methods to optimization on the discrete set and obtaining both exact and approximate solutions with accuracy estimates. |
| first_indexed | 2025-07-17T10:21:02Z |
| format | Article |
| id | journaliasakpiua-article-103892 |
| institution | System research and information technologies |
| language | Russian |
| last_indexed | 2025-07-17T10:21:02Z |
| publishDate | 2017 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| spelling | journaliasakpiua-article-1038922018-04-04T16:37:16Z Optimization over the general signed permutation set of permutations Оптимизация на общем множестве перестановок со знаком Оптимізація на загальній множині перестановок зі знаком Pichugina, Oksana S. combinatorial optimization the polyhedral-spherical set signed permutations the general permutation set the binary set a supersphere the polyhedral-surface method the conditional gradient method комбинаторная оптимизация полиэдрально-сферическое множество перестановки со знаком общее множество перестановок бинарное множество суперсфера полиэдрально-поверхностный метод метод условного градиента комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They include set’s cardinality, an irreducible H-representation of the polyhedron, its dimension, the vertex and adjacency vertex criteria, and the number of combinatorially nonisomorphic polyhedra of a fixed dimension. The behavior of some classes of functions over the general signed permutation set is investigated. Functional-analytical representations of this set are constructed including polyhedral-superspherical and strict superspherical. Explicit solutions of a linear problem and a projection problem over the general signed permutation set are presented. The research allows applying continuous methods to optimization on the discrete set and obtaining both exact and approximate solutions with accuracy estimates. Введено общее множество перестановок со знаком и рассмотрены подходы к оптимизации на нем, основанные на погружении в арифметическое евклидово пространство. В рамках исследования изучены свойства этого евклидового комбинаторного множества и его выпуклой оболочки (общего многогранника перестановок со знаком), такие как мощность множества, несводимое H-представление многогранника, его размерность, критерии и смежности вершин, а также количество комбинаторно неэквивалентных многогранников фиксированной размерности. Исследованы особенности поведения нескольких классов функций на общем множестве перестановок со знаком. Построен ряд функционально-аналитических представлений этого множества, включая полиэдрально-суперсферическое и строгое суперсферическое. Приведены явные решения линейной задачи и задачи проектирования на множество перестановок со знаком. Проведенное исследование позволяет применять непрерывные методы к оптимизации на дискретном множестве и получать как точные, так и приближенные решения оптимизационных задач с оценкой точности. Уведено загальну множину перестановок зі знаком і розглянуто підходи до оптимізації на ній, що ґрунтуються на зануренні в арифметичний евклідів простір. У межах дослідження вивчено властивості евклідової комбінаторної множини та її опуклої оболонки (загального багатогранника перестановок зі знаком), такі як потужність множини, незвідне H-подання багатогранника, його вимірність, критерії вершин та суміжності вершин, а також кількість комбінаторно нееквівалентних багатогранників фіксованої вимірності. Досліджено особливості поведінки кількох класів функцій на загальній множині перестановок зі знаком. Побудовано ряд функціонально-аналітичних подань цієї множини, у тому числі поліедрально-суперсферичне і строге суперсферичне. Наведено явні розв’язки лінійної задачі та задачі проектування на множину перестановок зі знаком. Проведене дослідження дозволяє застосовувати неперервні методи до оптимізації на дискретній множині й отримувати як точні, так і наближені розв’язки оптимізаційних задач з оцінкою точності. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017-12-15 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/103892 10.20535/SRIT.2308-8893.2017.4.07 System research and information technologies; No. 4 (2017); 74-96 Системные исследования и информационные технологии; № 4 (2017); 74-96 Системні дослідження та інформаційні технології; № 4 (2017); 74-96 2308-8893 1681-6048 ru http://journal.iasa.kpi.ua/article/view/103892/114234 Copyright (c) 2021 System research and information technologies |
| spellingShingle | комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта Pichugina, Oksana S. Оптимізація на загальній множині перестановок зі знаком |
| title | Оптимізація на загальній множині перестановок зі знаком |
| title_alt | Optimization over the general signed permutation set of permutations Оптимизация на общем множестве перестановок со знаком |
| title_full | Оптимізація на загальній множині перестановок зі знаком |
| title_fullStr | Оптимізація на загальній множині перестановок зі знаком |
| title_full_unstemmed | Оптимізація на загальній множині перестановок зі знаком |
| title_short | Оптимізація на загальній множині перестановок зі знаком |
| title_sort | оптимізація на загальній множині перестановок зі знаком |
| topic | комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта |
| topic_facet | combinatorial optimization the polyhedral-spherical set signed permutations the general permutation set the binary set a supersphere the polyhedral-surface method the conditional gradient method комбинаторная оптимизация полиэдрально-сферическое множество перестановки со знаком общее множество перестановок бинарное множество суперсфера полиэдрально-поверхностный метод метод условного градиента комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта |
| url | http://journal.iasa.kpi.ua/article/view/103892 |
| work_keys_str_mv | AT pichuginaoksanas optimizationoverthegeneralsignedpermutationsetofpermutations AT pichuginaoksanas optimizaciânaobŝemmnožestveperestanovoksoznakom AT pichuginaoksanas optimízacíânazagalʹníjmnožiníperestanovokzíznakom |