Том 25, номер 3, 2018 г., Стр. 23-35

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

Аннотация:
Рассматривается задача минимизации симметричной квазивыпуклой функции, заданной оракулом на множестве целых точек квадрата. Сформулирован критерий оптимальности решения, получена логарифмическая нижняя оценка сложности задачи и разработан алгоритм, у которого число обращений к оракулу превышает нижнюю оценку не более чем в 3 раза.
Библиогр. 14.

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

DOI: 10.17377/daio.2018.25.585

Веселов Сергей Иванович ¹
Грибанов Дмитрий Владимирович ¹
Золотых Николай Юрьевич ¹
Чирков Александр Юрьевич ¹
1. Институт информационных технологий, математики и механики,
Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: sergey.veselov@itmm.unn.ru, dmitry.gribanov@itmm.unn.ru, nikolai.zolotykh@itmm.unn.ru, aleksandr.chirkov@itmm.unn.ru

Статья поступила 6 июля 2017 г.
Исправленный вариант — 15 декабря 2017 г.

Литература

[1] Виноградов И. М. Основы теории чисел. М.: Лань, 2009.

[2] Золотых Н. Ю., Чирков А. Ю. Нижняя оценка сложности минимизации строго квазивыпуклой функции на целочисленной решётке // Вестн. Нижегород. ун-та им. Н. И. Лобачевского. 2012. № 5. C. 93–96.

[3] Сухарев А. Г., Тимохов А. В., Фёдоров В. В. Курс методов оптимизации. М.: Наука, 1986.

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

[5] Avriel M., Wilde D. J. Optimality proof for the symmetric Fibonacci search technique // Fibonacci Q. 1966. Vol. 4, No. 3. P. 265–269.

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

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

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

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

[10] Kiefer J. Sequential minimax search for a maximum // Proc. Amer. Math. Soc. 1953. Vol. 4, No. 3. P. 502–506.

[11] Oertel T. Integer convex minimization in low dimensions: Thes. ... doct. phylosophy. Eidgenössische Technische Hochschule, Zürich, 2014.

[12] 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.

[13] Schrijver A. Theory of linear and integer programming. Chichester: John Wiley & Sons, 1998.

[14] Sun W., Yuan Y. Optimization theory and methods: Nonlinear programming. Vol. 1. New York: Springer, 2006. (Springer Optim. Its Appl.; Vol. 1).