Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 56-72
Volume 27, No 1, 2020, P. 17-42
UDC 519.854
D. V. Gribanov and D. S. Malyshev
Minimization of even conic functions on the two-dimensional integral lattice
Abstract:
Under consideration is the Successive Minima Problem for the 2-dimensional lattice with respect to the order given by some conic function $f$. We propose an algorithm with complexity of $3,32 log_2$ $R+O(1)$ calls to the comparison oracle of $f$, where $R$ is the radius of the circular searching area, while the best known lower oracle complexity bound is $3 log_2$ $R + O(1)$. We give an efficient criterion for checking that given vectors of a $2$-dimensional lattice are successive minima and form a basis for the lattice. Moreover, we show that the similar Successive Minima Problem for dimension $n$ can be solved by an algorithm with at most $O(n)^{2n} log R$ calls to the comparison oracle. The results of the article can be applied to searching successive minima with respect to arbitrary convex functions defined by the comparison oracle.
Illustr. 2, bibliogr. 24.
Keywords: quasiconvex function, convex function, conic function, quasiconvex polynomial, integral lattice, nonlinear integer programming, successive minima, reduced basis of a lattice.
DOI: 10.33048/daio.2020.27.654
Dmitry V. Gribanov 1
Dmitry S. Malyshev 1
1. National Research University Higher School of Economics,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
e-mail: dimitry.gribanov@gmail.com, dsmalyshev@rambler.ru
Received April 2, 2019
Revised August 15, 2019
Accepted August 28, 2019
References
[1] A. Yu. Chirkov, Minimization of a quasiconvex function on 2-dimensional lattice, Vestn. Lobachevsky State Univ. Nizhny Novgorod, Ser. Model. Optim. Control 1, 227–238 (2003).[2] A. Ahmadi, A. Olshevsky, P. Parrilo, and J. Tsitsiklis, NP-hardness of deciding convexity of quadratic polynomials and related problems, Math. Program. 137 (1–2), 453–476 (2013).
[3] D. Dadush, Integer programming, lattice algorithms, and deterministic volume estimation, Ph. D. Thesis (ProQuest LLC, Ann Arbor, MI; Georgia Institute of Technology, 2012).
[4] D. Dadush, C. Peikert, and S. Vempala, Enumerative lattice algorithms in any norm via $M$-ellipsoid coverings, in Proc. 52nd Annual IEEE Symp. Foundations of Computer Science, Palm Springs, CA, USA, Oct. 23–25, 2011 (IEEE Comput. Soc., Washington, 2011), pp. 580–589.
[5] L. Khachiyan and L. Porkolab, Integer optimization on convex semialgebraic sets, Discrete Comput. Geom. 23 (2), 207–224 (2000).
[6] H. Lenstra, Integer programming with a fixed number of variables, Math. Oper. Res. 8 (4), 538–548 (1983).
[7] J. A. de Loera, R. Hemmecke, M. Koppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, Math. Oper. Res. 31 (1), 147–153 (2006).
[8] S. Heinz, Complexity of integer quasiconvex polynomial optimization, J. Complexity 21 (4), 543–556 (2005).
[9] S. Heinz, Quasiconvex functions can be approximated by quasiconvex polynomials, ESAIM Control Optim. Calc. Var. 14 (4), 795–801 (2008).
[10] R. Hemmecke, S. Onn, and R. Weismantel, A polynomial oracle-time algorithm for convex integer minimization, Math. Program. 126 (1), 97–117 (2011).
[11] 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 (1), 69–84 (2013).
[12] T. Oertel, Integer convex minimization in low dimensions, Ph. D. Thesis (Eidgenössische Technische Hochschule, Zürich, 2014).
[13] T. Oertel, C. Wagner, and R. Weismantel, Integer convex minimization by mixed integer linear optimization, Oper. Res. Lett. 42 (6), 424–428 (2014).
[14] A. Basu and T. Oertel, Centerpoints: A link between optimization and convex geometry, SIAM J. Optim. 27 (2), 866–889 (2017).
[15] A. Yu. Chirkov, D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov, and A. Yu. Zolotykh, On the complexity of quasiconvex integer minimization problem, J. Global Optim. 73 (4), 761–788 (2018).
[16] S. I. Veselov, D. V. Gribanov, N. Yu. Zolotykh, and A. Yu. Chirkov, Minimizing a symmetric quasiconvex function on a two-dimensional lattice, Diskretn. Anal. Issled. Oper. 25 (3), 23–35 (2018) [J. Appl. Ind. Math. 12 (3), 587–594 (2018)].
[17] D. Micciancio, Efficient reductions among lattice problems, in Proc. 19th Annual ACM-SIAM Symp. Discrete Algorithms, San Francisco, California, Jan. 20–22, 2008 (SIAM, Philadelphia, PA, 2008), pp. 84–93.
[18] D. Micciancio and P. Voulgaris, A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, SIAM J. Comput. 42 (3), 1364–1391 (2010).
[19] D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz, Solving the shortest vector problem in $2^n$ time via discrete Gaussian sampling, in Proc. 47th Annual ACM Symp. Theory of Computing, Portland, OR, USA, June 14–17, 2015 (ACM, New York, 2015), pp. 733–742.
[20] D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz, Solving the closest vector problem in $2^n$ time – the discrete Gaussian strikes again! in Proc. 56th Annual IEEE Symp. Foundations of Computer Science, Berkeley, CA, USA, Oct. 18–20, 2015, (IEEE Comput. Soc., Washington, 2011), pp. 563–582.
[21] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics – A Foundation for Computer Science, (Addison-Wesley Prof., Reading, MA, 1994).
[22] J. Cassels, An Introduction to the Geometry of Numbers (Springer, Berlin, 1997).
[23] J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Natl. Bureau of Stand. B: Math. Math. Phys. 71 B (4), 241–245 (1967).
[24] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, in Algorithms and Combinatorics, Vol. 2, (Springer, Berlin, 1993).
