Rational polyhedral outer-approximations of the second-order cone

Kocuk, Burak (2021) Rational polyhedral outer-approximations of the second-order cone. Discrete Optimization, 40 . ISSN 1572-5286 (Print) 1873-636X (Online)

Full text not available from this repository. (Request a copy)


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.
Item Type: Article
Uncontrolled Keywords: Mixed-integer programming; Polyhedral outer-approximation; Second-order cone programming
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Burak Kocuk
Date Deposited: 03 Sep 2022 17:38
Last Modified: 03 Sep 2022 17:38
URI: https://research.sabanciuniv.edu/id/eprint/43430

Actions (login required)

View Item
View Item