  


Rational Polyhedral OuterApproximations of the SecondOrder Cone
Burak Kocuk (burak.kocuksabanciuniv.edu) Abstract: It is wellknown that the secondorder cone can be outerapproximated to an arbitrary accuracy by a polyhedral cone of compact size defined by irrational data. In this paper, we propose two rational polyhedral outerapproximations of compact size retaining the same guaranteed accuracy. The first outerapproximation has the same size as the optimal but irrational outerapproximation 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, smallsize integer quadratic programs. The second outerapproximation has a size larger than the optimal irrational outerapproximation by a linear additive factor in the dimension of the secondorder 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: secondorder cone programming, polyhedral outerapproximation, mixedinteger programming Category 1: Linear, Cone and Semidefinite Programming Category 2: Integer Programming Citation: Download: [PDF] Entry Submitted: 11/30/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  