Geodesic
Minimization of even conic functions on~the~two-dimensional integral lattice
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 17-42.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : quasiconvex function, quasiconvex polynomial
Keywords: convex function, conic function, integral lattice, nonlinear integer programming, successive minima, reduced basis of a lattice. 
@article{DA_2020_27_1_a1,
     author = {D. V. Gribanov and D. S. Malyshev},
     title = {Minimization of even conic functions on~the~two-dimensional integral lattice},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--42},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/}
}
TY  - JOUR
AU  - D. V. Gribanov
AU  - D. S. Malyshev
TI  - Minimization of even conic functions on~the~two-dimensional integral lattice
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 17
EP  - 42
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/
LA  - ru
ID  - DA_2020_27_1_a1
ER  - 
%0 Journal Article
%A D. V. Gribanov
%A D. S. Malyshev
%T Minimization of even conic functions on~the~two-dimensional integral lattice
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 17-42
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/
%G ru
%F DA_2020_27_1_a1
D. V. Gribanov; D. S. Malyshev. Minimization of even conic functions on~the~two-dimensional integral lattice. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 17-42. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a1/

[1] A. Yu. Chirkov, “Minimization of a quasiconvex function on 2-dimensional lattice”, Vestn. Lobachevsky State Univ. Nizhny Novgorod, Ser. Model. Optim. Control, 2003, no. 1, 227–238

[2] A. Ahmadi, A. Olshevsky, P. Parrilo, J. Tsitsiklis, “NP-hardness of deciding convexity of quadratic polynomials and related problems”, Math. Program, 137:1–2 (2013), 453–476 | DOI | MR | Zbl

[3] D. Dadush, Integer programming, lattice algorithms, and deterministic volume estimation, Thes. ... doct. phylosophy, ProQuest LLC, Ann Arbor, MI; Georgia Institute of Technology, 2012, 280 pp. | MR

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

[5] L. Khachiyan, L. Porkolab, “Integer optimization on convex semialgebraic sets”, Discrete Comput. Geom., 23:2 (2000), 207–224 | DOI | MR | Zbl

[6] H. Lenstra, Math. Oper. Res., 8:4 (1983), 538–548 | DOI | MR | Zbl

[7] J. A. De Loera, R. Hemmecke, M. Koppe, R. Weismantel, “Integer polynomial optimization in fixed dimension”, Math. Oper. Res., 31:1 (2006), 147–153 | DOI | MR | Zbl

[8] S. Heinz, J. Complexity, 21:4 (2005), 543–556 | DOI | MR | Zbl

[9] S. Heinz, ESAIM Control Optim. Calc. Var., 14:4 (2008), 795–801 | DOI | MR | Zbl

[10] R. Hemmecke, S. Onn, R. Weismantel, “A polynomial oracle-time algorithm for convex integer minimization”, Math. Program., 126:1 (2011), 97–117 | DOI | MR | Zbl

[11] R. Hildebrand, M. Koppe, “A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(n\log n)}$”, Discrete Optim., 10:1 (2013), 69–84 | DOI | MR | Zbl

[12] T. Oertel, Integer convex minimization in low dimensions, Thes. ... doct. phylosophy, Eidgenos. Techn. Hochschule, Zurich, 2014, 127 pp.

[13] T. Oertel, C. Wagner, R. Weismantel, “Integer convex minimization by mixed integer linear optimization”, Oper. Res. Lett., 42:6 (2014), 424–428 | DOI | MR | Zbl

[14] A. Basu, T. Oertel, “Centerpoints: A link between optimization and convex geometry”, SIAM J. Optim., 27:2 (2017), 866–889 | DOI | MR | Zbl

[15] Chirkov A. Yu, D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov, A. Yu. Zolotykh, “On the complexity of quasiconvex integer minimization problem”, J. Global Optim., 73:4 (2018), 761–788 | DOI | MR

[16] S. I. Veselov, D. V. Gribanov, N. Yu. Zolotykh, A. Yu. Chirkov, “Minimizing a symmetric quasiconvex function on a two-dimensional lattice”, J. Appl. Ind. Math., 12:3 (2018), 587–594 | DOI | MR | Zbl

[17] D. Micciancio, “Efficient reductions among lattice problems”, Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (San Francisco, CA, Jan. 20–22, 2008), SIAM, Philadelphia, PA, 2008, 84–93 | MR | Zbl

[18] D. Micciancio, P. Voulgaris, “A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations”, SIAM J. Comput., 42:3 (2010), 1364–1391 | DOI | MR

[19] D. Aggarwal, D. Dadush, O. Regev, N. Stephens-Davidowitz, “Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling”, Proc. 47th Annu. ACM Symp. Theory of Computing (Portland, OR, USA, June 14–17, 2015), ACM, New York, 2015, 733–742 | MR | Zbl

[20] D. Aggarwal, D. Dadush, N. Stephens-Davidowitz, Solving the Closest Vector Problem in $2^n$ time — the discrete Gaussian strikes again!, Proc. 56th Annu. IEEE Symp. Foundations of Computer Science (Berkeley, CA, USA, Oct. 18–20, 2015), IEEE Comput. Soc., Washington, 2015, 563–582 | MR

[21] R. Graham, D. Knuth, O. Patashnik, Concrete mathematics — A foundation for computer science, Addison-Wesley, Reading, MA, 1994, 657 pp. | MR | Zbl

[22] J. Cassels, An introduction to the geometry of numbers, Springer-Verl., Berlin–Heidelberg, 1997, 343 pp. | MR | Zbl

[23] J. Edmonds, “Systems of distinct representatives and linear algebra”, J. Res. Nat. Bureau Stand. B. Math. Math. Phys., 71:4 (1967), 241–245 | DOI | MR | Zbl

[24] M. Grötschel, L. Lovász, A. Schrijver, Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics, v. 2, Springer-Verl., Berlin–Heidelberg, 1993, 363 pp. | MR