Том 20, номер 3, 2013 г., Стр. 65-70
УДК 514.172.45
Селиверстов А. В.
О мономах квадратичных форм
Аннотация:
Получены некоторые ограничения на взаимное расположение нулей в матрице вещественной квадратичной формы, которая достигает минимума на большом множестве вершин многомерного куба с центром в начале координат и рёбрами, параллельными координатным осям. В частности, если граф матрицы содержит точку сочленения, то множество минимумов соответствующей квадратичной формы не является максимальным по включению среди всех таких множеств для различных квадратичных форм.
Библиогр. 21.
Ключевые слова: дискретная оптимизация, квадратичная форма, многогранник, фасета, граф, матрица.
Селиверстов Александр Владиславович 1
1. Ин-т проблем передачи информации им. А. А. Харкевича РАН,
Большой Каретный пер., 19, стр. 1, 127994 Москва, Россия
е-mail: slvstv@iitp.ru
Статья поступила 28 июня 2012 г.
Исправленный вариант — 10 января 2013 г.
Литература
[1] Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. - Новосибирск: Изд-во ин-та математики, 2005. - 408 с.
[2] Береснев В. Л. Алгоритмы локального поиска для задачи конкурентного размещения предприятий // Автоматика и телемеханика. - 2012. - № 3. - С. 12–27.
[3] Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 4. - С. 3–16.
[4] Горбунов К. Ю., Селиверстов А. В., Любецкий В. А. Взаимное расположение параллельных гиперплоскостей, квадрик и вершин многомерного куба // Пробл. передачи информ. - 2012. - Т. 48, №2. - C. 113–120.
[5] Колоколов А. А., Орловская Т. Г., Рыбалка М. Ф. Анализ алгоритмов целочисленного программирования с использованием L-разбиения и унимодулярных преобразований // Автоматика и телемеханика. - 2012. - № 2. - С. 178–190.
[6] Максименко А. Н. Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 3. - С. 76–83.
[7] Максименко А. Н. Аналог теоремы Кука для многогранников // Изв. вузов. Математика. - 2012. - № 8. - С. 34–42.
[8] Селиверстов А. В. Замечания о расположениях точек на квадриках // Моделирование и анализ информ. систем. - 2012. - Т. 19, № 4. - С. 72–77.
[9] Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. - 2009. - Т. 45, № 3. - C. 73–78.
[10] Селиверстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. - 2011. - Т. 11, № 3. - P. 330–335.
[11] Схрейвер А. Теория линейного и целочисленного программирования. Т. 1. - М.: Мир, 1991. - 360 с.
[12] Ahlatçioglu A., Bussieck M., Esen M., Guignard M., Jagla J.-H., Meeraus A. Combining QCR and CHR for convex quadratic pure 0–1 programming problems with linear constraints // Ann. Oper. Res. - 2012. - Vol. 199, N 1. - P. 33–49.
[13] Avis D. Computational experience with the reverse search vertex enumeration algorithm // Optim. Methods Softw. - 1998. - Vol. 10, N 2. - P. 107–124.
[14] Avis D., Fukuda K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra // Discrete Comput. Geom. - 1992. - Vol. 8, N 1. - P. 295–313.
[15] Billera L. J., Sarangarajan A. All 0-1 polytopes are traveling salesman polytopes // Combinatorica. - 1996. - Vol. 16, N 2. - P. 175–188.
[16] Billionnet A., Elloumi S. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem // Math. Program. - 2007. - Vol. 109, N 1. - P. 55–68.
[17] Fukasawa R., Goycoolea M. On the exact separation of mixed integer knapsack cuts // Math. Program. - 2011. - Vol. 128, N 1–2. - P. 19–41.
[18] Galli L., Kaparis K., Letchford A. N. Gap inequalities for non-convex mixed-integer quadratic programs // Oper. Res. Lett. - 2011. - Vol. 39, N 5. - P. 297–300.
[19] Padberg M. The boolean quadric polytope: some characteristics, facets, and relatives // Math. Program. - 1989. - Vol. 45, N 1–3. - P. 139–172.
[20] Tamir A. New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems // Oper. Res. Lett. - 2009. - Vol. 37, N 5. - P. 303–306.
[21] Wang Y., Lü Z., Glover F., Hao J.-K. Path relinking for unconstrained binary quadratic programming // Eur. J. Oper. Res. - 2012. - Vol. 223, N 3. - P. 595–604.
