Minimizing a Symmetric Quasiconvex Function on a Two-Dimensional Lattice
- Authors: Veselov S.I.1, Gribanov D.B.1, Zolotykh N.Y.1, Chirkov A.Y.1
-
Affiliations:
- Institute of Information Technology, Mathematics, and Mechanics
- Issue: Vol 12, No 3 (2018)
- Pages: 587-594
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213104
- DOI: https://doi.org/10.1134/S199047891803016X
- ID: 213104
Cite item
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.
Keywords
About the authors
S. I. Veselov
Institute of Information Technology, Mathematics, and Mechanics
Author for correspondence.
Email: sergey.veselov@itmm.unn.ru
Russian Federation, pr. Gagarina 23, Nizhny Novgorod, 603950
D. B. Gribanov
Institute of Information Technology, Mathematics, and Mechanics
Email: sergey.veselov@itmm.unn.ru
Russian Federation, pr. Gagarina 23, Nizhny Novgorod, 603950
N. Yu. Zolotykh
Institute of Information Technology, Mathematics, and Mechanics
Email: sergey.veselov@itmm.unn.ru
Russian Federation, pr. Gagarina 23, Nizhny Novgorod, 603950
A. Yu. Chirkov
Institute of Information Technology, Mathematics, and Mechanics
Email: sergey.veselov@itmm.unn.ru
Russian Federation, pr. Gagarina 23, Nizhny Novgorod, 603950