Minimization of even conic functions on the two-dimensional integral lattice

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.