Том 27, номер 1, 2020 г., Стр. 17-42

УДК 519.854
Грибанов Д. В., Малышев Д. С.
Минимизация чётных конических функций на двумерной целочисленной решётке

Аннотация:
Рассматривается задача построения последовательных минимумов двумерной целочисленной решётки относительно порядка, заданного некоторой конической функцией $f$. Для указанной задачи предлагается алгоритм со сложностью $3,32 log_2$ $R+O(1)$ обращений к оракулу сравнения функции $f$, где $R$ — радиус круговой области поиска, тогда как нижняя оценка сложности на данный момент составляет $3 log_2$ $R + O(1)$. В настоящей работе приводится эффективный критерий проверки того, что заданные векторы двумерной решётки являются последовательными минимумами и образуют базис решётки. Также показывается, что аналогичная задача поиска последовательных минимумов для решёток размерности $n$ может быть решена алгоритмом, использующим не более чем $O(n)^{2n} log R$ обращений к оракулу сравнения. Результаты работы могут быть применены для поиска последовательных минимумов относительно любых выпуклых функций, заданных оракулом сравнения.
Ил. 2, библиогр. 24.

Ключевые слова: квазивыпуклая функция, выпуклая функция, коническая функция, квазивыпуклый полином, целочисленная решётка, нелинейное целочисленное программирование, последовательные минимумы решётки, приведённый базис решётки.

DOI: 10.33048/daio.2020.27.654

Грибанов Дмитрий Владимирович ¹
Малышев Дмитрий Сергеевич ¹
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dimitry.gribanov@gmail.com, dsmalyshev@rambler.ru

Статья поступила 2 апреля 2019 г.
После доработки — 15 августа 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

[1] Чирков А. Ю. Минимизация квазивыпуклой функции на двумерной целочисленной решётке // Вестн. Нижегород. ун-та им. Н. И. Лобачевского. Сер. Мат. моделирование и оптим. управление. 2003. № 1. C. 227–238.

[2] Ahmadi A., Olshevsky A., Parrilo P., Tsitsiklis J. NP-hardness of deciding convexity of quadratic polynomials and related problems // Math. Program. 2013. Vol. 137, No. 1–2. P. 453–476.

[3] Dadush D. Integer programming, lattice algorithms, and deterministic volume estimation: Thes. . . . doct. phylosophy. Georgia Inst. Tech., 2012. 280 p.

[4] Dadush D., Peikert C., Vempala S. Enumerative lattice algorithms in any norm via M-ellipsoid coverings // Proc. 52nd Annu. IEEE Symp. Foundations of Computer Science (Palm Springs, CA, Oct. 23–25, 2011). P. 580–589.

[5] Khachiyan L., Porkolab L. Integer optimization on convex semialgebraic sets // Discrete Comput. Geom. 2000. Vol. 23, No. 2. P. 207–224.

[6] Lenstra H. Integer programming with a fixed number of variables // Math. Oper. Res. 1983. Vol. 8, No. 4. P. 538–548.

[7] De Loera J. A., Hemmecke R., Koppe M., Weismantel R. Integer polynomial optimization in fixed dimension // Math. Oper. Res. 2006. Vol. 31, No. 1. P. 147–153.

[8] Heinz S. Complexity of integer quasiconvex polynomial optimization // J. Complexity. 2005. Vol. 21, No. 4. P. 543–556.

[9] Heinz S. Quasiconvex functions can be approximated by quasiconvex polynomials // ESAIM Control Optim. Calc. Var. 2008. Vol. 14, No. 4. P. 795–801.

[10] Hemmecke R., Onn S., Weismantel R. A polynomial oracle-time algorithm for convex integer minimization // Math. Program. 2011. Vol. 126, No. 1. P. 97–117.

[11] Hildebrand R., Köppe M. A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(n log n)}$ // Discrete Optim. 2013. Vol. 10, No. 1. P. 69–84.

[12] Oertel T. Integer convex minimization in low dimensions: Thes. . . . doct. phylosophy. Eidgenös. Techn. Hochschule, Zürich, 2014. 127 p.

[13] Oertel T., Wagner C., Weismantel R. Integer convex minimization by mixed integer linear optimization // Oper. Res. Lett. 2014. Vol. 42, No. 6. P. 424–428.

[14] Basu A., Oertel T. Centerpoints: A link between optimization and convex geometry // SIAM J. Optim. 2017. Vol. 27, No. 2. P. 866–889.

[15] Chirkov A. Yu, Gribanov D. V., Malyshev D. S., Pardalos P. M., Veselov S. I., Zolotykh A. Yu. On the complexity of quasiconvex integer minimization problem // J. Global Optim. 2018. Vol. 73, No. 4. P. 761–788. DOI:10.1007/s10898-018-0729-8.

[16] Веселов С. И., Грибанов Д. В., Золотых Н. Ю., Чирков А. Ю. Минимизация симметричной квазивыпуклой функции на двумерной решётке // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 23–35.

[17] Micciancio D. Efficient reductions among lattice problems // Proc. Annu. ACM-SIAM Symp. Discrete Algorithms (San Francisco, CA, Jan. 20–22, 2008). P. 84–93. DOI: 10.1145/1347082.1347092.

[18] Micciancio D., Voulgaris P. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations // SIAM J. Comput. 2010. Vol. 42, No. 3. P. 1364–1391.

[19] Aggarwal D., Dadush D., Regev O., Stephens-Davidowitz N. Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling // STOC’15. Proc. 47th Annu. ACM Symp. Theory of Computing (Portland, OR, June 14–17, 2015). P. 733–742. DOI: 10.1145/2746539.2746606.

[20] Aggarwal D., Dadush D., Stephens-Davidowitz N. Solving the Closest Vector Problem in $2^n$ time — the discrete Gaussian strikes again! // IEEE 56th Annu. Symp. Foundations of Computer Science (Berkeley, CA, Oct. 18– 20, 2015). P. 563–582. DOI: 10.1109/FOCS.2015.41.

[21] Graham R., Knuth D., Patashnik O. Concrete mathematics — A foundation for computer science (2nd ed.). Reading, MA: Addison-Wesley Pro., 1994. 657 p.

[22] Cassels J. An introduction to the geometry of numbers. Berlin; Heidelberg: Springer-Verl. 1997. 343 p.

[23] Edmonds J. Systems of distinct representatives and linear algebra // J. Res. Nat. Bureau Stand. B. Math. Math. Phys. 1967. Vol. 71, No. 4. P. 241–245.

[24] Grötschel M., Lovász L., Schrijver A. Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics. Vol. 2. Berlin; Heidelberg: Springer-Verl. 1993. 363 p.