Geodesic
Minimizing a~symmetric quasiconvex function on a~two-dimensional lattice
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 23-35.

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

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.
Mots-clés : quasiconvex function, oracle
Keywords: integer lattice. 
@article{DA_2018_25_3_a1,
     author = {S. I. Veselov and D. V. Gribanov and N. Yu. Zolotykh and A. Yu. Chirkov},
     title = {Minimizing a~symmetric quasiconvex function on a~two-dimensional lattice},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {23--35},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_3_a1/}
}
TY  - JOUR
AU  - S. I. Veselov
AU  - D. V. Gribanov
AU  - N. Yu. Zolotykh
AU  - A. Yu. Chirkov
TI  - Minimizing a~symmetric quasiconvex function on a~two-dimensional lattice
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 23
EP  - 35
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_3_a1/
LA  - ru
ID  - DA_2018_25_3_a1
ER  - 
%0 Journal Article
%A S. I. Veselov
%A D. V. Gribanov
%A N. Yu. Zolotykh
%A A. Yu. Chirkov
%T Minimizing a~symmetric quasiconvex function on a~two-dimensional lattice
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 23-35
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_3_a1/
%G ru
%F DA_2018_25_3_a1
S. I. Veselov; D. V. Gribanov; N. Yu. Zolotykh; A. Yu. Chirkov. Minimizing a~symmetric quasiconvex function on a~two-dimensional lattice. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 23-35. http://geodesic.mathdoc.fr/item/DA_2018_25_3_a1/

[1] I. M. Vinogradov, Elements of Number Theory, Dover, Mineola, NY, 2016 | MR

[2] N. Yu. Zolotykh, A. Yu. Chirkov, “Lower bound for complexity of minimization of quasi-convex function on integer lattice”, Vestn. Nizhegorod. Univ. N. I. Lobachevskogo, 2012, no. 5, 93–96

[3] A. G. Sukharev, A. V. Timokhov, V. V. Fyodorov, A Course in Optimization Methods, Nauka, Moscow, 1986 | MR

[4] A. Yu. Chirkov, “Minimization of quasi-convex function on two-dimensional integer lattice”, Vestn. Nizhegorod. Univ. N. I. Lobachevskogo, Mat. Model. Optim. Upr., 2003, no. 1, 227–238

[5] Avriel M., Wilde D. J., “Optimality proof for the symmetric Fibonacci search technique”, Fibonacci Q., 4:3 (1966), 265–269 | MR | Zbl

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

[7] Heinz S., “Complexity of integer quasiconvex polynomial optimization”, J. Complexity, 21:4 (2005), 543–556 | DOI | MR | Zbl

[8] Heinz S., “Quasiconvex functions can be approximated by quasiconvex polynomials”, ESAIM, Control Optim. Calc. Var., 14:4 (2008), 795–801 | DOI | MR | Zbl

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

[10] Kiefer J., “Sequential minimax search for a maximum”, Proc. Amer. Math. Soc., 4:3 (1953), 502–506 | DOI | MR | Zbl

[11] Oertel T., Integer convex minimization in low dimensions, Thes. $\dots$ 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., 42:6 (2014), 424–428 | DOI | MR | Zbl

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

[14] Sun W., Yuan Y., Optimization theory and methods: Nonlinear programming, v. 1, Springer Optim. Its Appl., 1, Springer, New York, 2006 | MR | Zbl