Замечания о расположениях точек на квадриках
https://doi.org/10.18255/1818-1015-2012-4-72-77
Аннотация
Рассмотрена задача минимизации квадратичного многочлена на множестве всех точек многомерного вещественного пространства, координаты которых равны нулю или единице. Получены некоторые ограничения на взаимное расположение точек минимума, когда их достаточно много.
Ключевые слова
Об авторе
Александр Владиславович Селиверстов
Институт проблем передачи информации им. А. А. Харкевича РАН
Россия
старший научный сотрудник, кандидат физико-математических наук
Россия
старший научный сотрудник, кандидат физико-математических наук
Список литературы
1. Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Издательство Института математики, 2005. 408 с.
2. Billionnet A., Elloumi S. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem // Mathematical programming. Ser. A. 2007. V. 109. №1. P. 55–68.
3. Ahlat¸cio˘glu 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 // Annals of operations research. 2012. V. 199. №1. P. 33–49.
4. Емеличев В. А., Коротков В. В. Об устойчивости лексикографического решения векторной минимаксной квадратичной булевой задачи // Тр. Института матем. НАН Беларуси. 2011. Т. 19. №2. С. 26–36.
5. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.
6. Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical programming. 1989. V. 45. №1–3. P. 139–172.
7. Максименко А. Н. О числе фасет 2-смежностного многогранника // Модел. и анализ информ. систем. 2010. Т. 17. №1. С. 76–82.
8. Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.
9. Zhao W., Posner M. E. A large class of facets for the K-median polytope // Mathematical programming. Ser. A. 2011. V. 128. №1–2. P. 171–203.
10. Galli L., Kaparis K., Letchford A. N. Gap inequalities for non-convex mixed-integer quadratic programs // Operations research letters. 2011. V. 39. №5. P. 297–300.
11. Николаев А. В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Модел. и анализ информ. систем. 2011. Т. 18. №3. С. 82–100.
12. Делоне Б. Н. Геометрия положительных квадратичных форм // УМН. 1937. №3. С. 16–62.
13. Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. 2009. Т. 45. №3. C. 73–78.
14. Селиверстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. 2011. Т. 11. №3. С. 330–335. Электронный научный журнал http://www.jip.ru
15. Costello K. P., Vu V. H. The rank of random graphs // Random structures and algorithms. 2008. V. 33. №3. P. 269–285.
Рецензия
Для цитирования:
Селиверстов А.В. Замечания о расположениях точек на квадриках. Моделирование и анализ информационных систем. 2012;19(4):72-77. https://doi.org/10.18255/1818-1015-2012-4-72-77
For citation:
Seliverstov A.V. Some Notes about Arrangements of Points on Quadrics. Modeling and Analysis of Information Systems. 2012;19(4):72-77. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-72-77
Просмотров:
802
Послать статью по эл. почте 