Optimization Online


Rational Polyhedral Outer-Approximations of the Second-Order Cone

Burak Kocuk (burak.kocuk***at***sabanciuniv.edu)

Abstract: 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 accuracy and logarithmic in the dimension.

Keywords: second-order cone programming, polyhedral outer-approximation, mixed-integer programming

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 11/30/2019
Entry Accepted: 12/01/2019
Entry Last Modified: 04/17/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society