Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах

• Опубліковано в: : Компьютерная математика
• Дата: 2016
• Автори: Пичугина, О.С., Яковлев, С.В.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
• Теми: Теория и методы оптимизации
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/168408
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах / О.С. Пичугина, С.В. Яковлев // Компьютерная математика. — 2016. — № 1. — С. 143-154. — Бібліогр.: 13 назв. — рос.

Разработан подход к построению нижних оценок квадратичной функции на множестве перестановочных матриц Π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.