Minimizing a Symmetric Quasiconvex Function on a Two-Dimensional Lattice

被引：0
作者：
Veselov S.I. [1 ]
Gribanov D.B. [1 ]
Zolotykh N.Y. [1 ]
Chirkov A.Y. [1 ]
机构：
[1] Institute of Information Technology, Mathematics, and Mechanics, Lobachevsky Nizhny Novgorod State University, pr. Gagarina 23, Nizhny Novgorod
来源：
Veselov, S.I. (sergey.veselov@itmm.unn.ru) | 2018年 / Pleiades journals卷 / 12期
基金：
俄罗斯科学基金会;
关键词：
integer lattice; oracle; quasiconvex function;
D O I：
10.1134/S199047891803016X
中图分类号：
学科分类号：
摘要：
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. © 2018, Pleiades Publishing, Ltd.
引用
收藏
页码：587 / 594
页数：7
相关论文
共 14 条
  • [1] Chirkov A.Y., Minimization of Quasiconvex Function on Two-Dimensional Integer Lattice, Vestnik Nizhegorod. Univ. N. I. Lobachevskogo, Mat. Model. Optim. Upravl., 1, pp. 227-238, (2003)
  • [2] Zolotykh N.Y., Chirkov A.Y., A Lower Bound for Complexity of Minimization of Quasi-Convex Function on Integer Lattice, Vestnik Nizhegorod. Univ. N. I. Lobachevskogo, 5, 2, pp. 93-96, (2012)
  • [3] Basu A., Oertel T., Centerpoints:A Link BetweenOptimization andConvexGeometry, SIAM J.Optim., 27, 2, pp. 866-889, (2017)
  • [4] Oertel T., Integer ConvexMinimization in Low Dimensions, (2014)
  • [5] Oertel T., Wagner C., Weismantel R., Integer ConvexMinimization byMixed Integer Linear Optimization, Oper. Res. Lett., 42, 6, pp. 424-428, (2014)
  • [6] Heinz S., Complexity of Integer Quasiconvex Polynomial Optimization, J. Complexity, 21, 4, pp. 543-556, (2005)
  • [7] Hildebrand R., Koppe M., A New Lenstra-Type Algorithm for Quasiconvex Polynomial Integer Minimization with Complexity 2O(n log n), Discrete Optim., 10, 1, pp. 69-84, (2013)
  • [8] Heinz S., Quasiconvex Functions Can Be Approximated by Quasiconvex Polynomials, ESAIM, Control Optim. Calc. Var., 14, 4, pp. 795-801, (2008)
  • [9] Vinogradov I.M., Elements of Number Theory, (2016)
  • [10] Sukharev A.G., Timokhov A.V., Fyodorov V.V., A Course onOptimizationMethods, (1986)
12