Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах
Разработан подход к построению нижних оценок квадратичной функции на множестве перестановочных матриц Πn , основанный на применении функциональных представлений и выпуклых продолжений в полиэдральносферических релаксационных задачах. Построены оригинальные квадратичные функциональные представления Π...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168408 |
| 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. — № 1. — С. 143-154. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862617801474179072 |
|---|---|
| author | Пичугина, О.С. Яковлев, С.В. |
| author_facet | Пичугина, О.С. Яковлев, С.В. |
| citation_txt | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах / О.С. Пичугина, С.В. Яковлев // Компьютерная математика. — 2016. — № 1. — С. 143-154. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Разработан подход к построению нижних оценок квадратичной функции на множестве перестановочных матриц Πn , основанный на применении функциональных представлений и выпуклых продолжений в полиэдральносферических релаксационных задачах. Построены оригинальные квадратичные функциональные представления Πn . Сформировано семейство однопараметрических выпуклых квадратичных продолжений с Πn на все евклидово пространство. Результаты применимы как в приближенных алгоритмах квадратичной оптимизации, так и в точных методах типа ветвей и границ, основанных на полиэдральных, сферических и других видах релаксации.
Розроблено підхід до побудови нижніх оцінок квадратичної функції на множині перестановочних матриць Πn , що ґрунтується на застосуванні функціональних представлень і опуклих продовжень у поліедрально-сферичних релаксаційних задачах. Побудовано оригінальні квадратичні функціональні представлення Πn . Сформовано сімейство однопараметричних опуклих квадратичних продовжень цільової функції з Πn на весь евклідів простір. Результати застосовні як в наближених алгоритмах квадратичної оптимізації, так і в точних методах типу методу гілок та меж, що ґрунтуються на поліедральних, сферичних та інших видах релаксації.
An approach to construction of lower bounds of quadratic function over the set Πn of permutation matrices based on the use of functional representations and convex extensions in polyhedralspherical relaxation problems is developed. A number of original quadratic functional representations of Πn are designed. A family of one-parameter convex quadratic extensions of the objective function from Πn onto the whole Euclidean space is formed. The results are applicable in approximate algorithms of quadratic optimization and in the exact methods such as Branch&Bound ones, based on polyhedral, spherical, and other relaxations.
|
| first_indexed | 2025-12-07T13:13:00Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-168408 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Russian |
| last_indexed | 2025-12-07T13:13:00Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Пичугина, О.С. Яковлев, С.В. 2020-05-01T16:14:39Z 2020-05-01T16:14:39Z 2016 Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах / О.С. Пичугина, С.В. Яковлев // Компьютерная математика. — 2016. — № 1. — С. 143-154. — Бібліогр.: 13 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168408 519.85 Разработан подход к построению нижних оценок квадратичной функции на множестве перестановочных матриц Πn , основанный на применении функциональных представлений и выпуклых продолжений в полиэдральносферических релаксационных задачах. Построены оригинальные квадратичные функциональные представления Πn . Сформировано семейство однопараметрических выпуклых квадратичных продолжений с Πn на все евклидово пространство. Результаты применимы как в приближенных алгоритмах квадратичной оптимизации, так и в точных методах типа ветвей и границ, основанных на полиэдральных, сферических и других видах релаксации. Розроблено підхід до побудови нижніх оцінок квадратичної функції на множині перестановочних матриць Πn , що ґрунтується на застосуванні функціональних представлень і опуклих продовжень у поліедрально-сферичних релаксаційних задачах. Побудовано оригінальні квадратичні функціональні представлення Πn . Сформовано сімейство однопараметричних опуклих квадратичних продовжень цільової функції з Πn на весь евклідів простір. Результати застосовні як в наближених алгоритмах квадратичної оптимізації, так і в точних методах типу методу гілок та меж, що ґрунтуються на поліедральних, сферичних та інших видах релаксації. An approach to construction of lower bounds of quadratic function over the set Πn of permutation matrices based on the use of functional representations and convex extensions in polyhedralspherical relaxation problems is developed. A number of original quadratic functional representations of Πn are designed. A family of one-parameter convex quadratic extensions of the objective function from Πn onto the whole Euclidean space is formed. The results are applicable in approximate algorithms of quadratic optimization and in the exact methods such as Branch&Bound ones, based on polyhedral, spherical, and other relaxations. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах Опуклі продовження для класу квадратичних задач на перестановочних матрицях Convex extensions for the quadratic problems over permutation matrices Article published earlier |
| spellingShingle | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах Пичугина, О.С. Яковлев, С.В. Теория и методы оптимизации |
| title | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| title_alt | Опуклі продовження для класу квадратичних задач на перестановочних матрицях Convex extensions for the quadratic problems over permutation matrices |
| title_full | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| title_fullStr | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| title_full_unstemmed | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| title_short | Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| title_sort | выпуклые продолжения для класса квадратичных задач на перестановочных матрицах |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168408 |
| work_keys_str_mv | AT pičuginaos vypuklyeprodolženiâdlâklassakvadratičnyhzadačnaperestanovočnyhmatricah AT âkovlevsv vypuklyeprodolženiâdlâklassakvadratičnyhzadačnaperestanovočnyhmatricah AT pičuginaos opuklíprodovžennâdlâklasukvadratičnihzadačnaperestanovočnihmatricâh AT âkovlevsv opuklíprodovžennâdlâklasukvadratičnihzadačnaperestanovočnihmatricâh AT pičuginaos convexextensionsforthequadraticproblemsoverpermutationmatrices AT âkovlevsv convexextensionsforthequadraticproblemsoverpermutationmatrices |