Rational polyhedral outer-approximations of the second-order cone

Official URL: https://dx.doi.org/10.1016/j.disopt.2021.100643

It is well-known that the second-order cone can be outer-approximated to an arbitrary accuracy ϵ by a polyhedral cone of compact size defined by irrational data. In this paper, we propose two rational polyhedral outer-approximations of compact size retaining the same guaranteed accuracy ϵ. The first outer-approximation has the same size as the optimal but irrational outer-approximation from the literature. In this case, we provide a practical approach to obtain such an approximation defined by the smallest integer coefficients possible, which requires solving a few, small-size integer quadratic programs. The second outer-approximation has a size larger than the optimal irrational outer-approximation by a linear additive factor in the dimension of the second-order cone. However, in this case, the construction is explicit, and it is possible to derive an upper bound on the largest coefficient, which is sublinear in ϵ and logarithmic in the dimension. We also propose a third outer-approximation, which yields the best possible approximation accuracy given an upper bound on the size of its coefficients. Finally, we discuss two theoretical applications in which having a rational polyhedral outer-approximation is crucial, and run some experiments which explore the benefits of the formulations proposed in this paper from a computational perspective.