Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:3, 587–594
Volume 25, No 3, 2018, P. 23-35
UDC 519.854
S. I. Veselov, D. V. Gribanov, N. Yu. Zolotykh, and A. Yu. Chirkov
Minimizing a symmetric quasiconvex function on a two-dimensional lattice
Abstract:
We consider the minimization problem for a symmetric quasiconvex function defined by an oracle on the set of integer points of a square. We formulate an optimality criterion for the solution, obtain a logarithmic lower bound for the complexity of the problem, and propose an algorithm for which the number of inquiries to the oracle is at most thrice the lower bound.
Bibliogr. 14.
Keywords: quasiconvex function, oracle, integer lattice.
DOI: 10.17377/daio.2018.25.585
Sergey I. Veselov 1
Dmitry V. Gribanov 1
Nikolay Yu. Zolotykh 1
Aleksandr Yu. Chirko 1
1. Institute of Information Technology, Mathematics, and Mechanics,
Lobachevsky Nizhny Novgorod State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
e-mail: sergey.veselov@itmm.unn.ru, dmitry.gribanov@itmm.unn.ru, nikolai.zolotykh@itmm.unn.ru, aleksandr.chirkov@itmm.unn.ru
Received 6 July 2017
Revised 15 December 2017
References
[1] I. M. Vinogradov, Osnovy teorii chisel, Lan’, Moscow, 2009. Translated under the title Elements of Number Theory, Dover, Mineola, NY, 2016.[2] N. Yu. Zolotykh and A. Yu. Chirkov, Lower bound for complexity of minimization of quasi-convex function on integer lattice, Vestn. Nizhegorod. Univ. N. I. Lobachevskogo, No. 5 (2), 93–96, 2012.
[3] A. G. Sukharev, A. V. Timokhov, and V. V. Fyodorov, Kurs metodov optimizatsii (A Course in Optimization Methods), Nauka, Moscow, 1986.
[4] A. Yu. Chirkov, Minimization of quasi-convex function on two-dimensional integer lattice, Vestn. Nizhegorod. Univ. N. I. Lobachevskogo, Mat. Model. Optim. Upr., No. 1, 227–238, 2003.
[5] M. Avriel and D. J. Wilde, Optimality proof for the symmetric Fibonacci search technique, Fibonacci Q., 4, No. 3, 265–269, 1966.
[6] A. Basu and T. Oertel, Centerpoints: A link between optimization and convex geometry, SIAM J. Optim., 27, No. 2, 866–889, 2017.
[7] S. Heinz, Complexity of integer quasiconvex polynomial optimization, J. Complexity, 21, No. 4, 543–556, 2005.
[8] S. Heinz, Quasiconvex functions can be approximated by quasiconvex polynomials, ESAIM, Control Optim. Calc. Var., 14, No. 4, 795–801, 2008.
[9] R. Hildebrand and M. Köppe, A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(n log n)}$, Discrete Optim., 10, No. 1, 69–84, 2013.
[10] J. Kiefer, Sequential minimax search for a maximum, Proc. AMS, 4, No. 3, 502–506, 1953.
[11] T. Oertel, Integer convex minimization in low dimensions, PhD Dissertation, ETH Zurich, 2014.
[12] T. Oertel, C. Wagner, and R. Weismantel, Integer convex minimization by mixed integer linear optimization, Oper. Res. Lett., 42, No. 6, 424–428, 2014.
[13] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, GB, 1998.
[14] W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006 (Springer Optim. Its Appl., Vol. 1).
