On Polyhedral Approximations of the Second-Order Cone

By Aharon Ben-Tal, Arkadi Nemirovski. Mathematics of Operations Research, 2001

401 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Industrial and Manufacturing Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/b280df4b0f378a1badfa4693ae44208415022ca6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

In Numerical Analysis

Citations in the corpus

Minimum Loss Network Reconfiguration Using Mixed-Integer Convex Programming (2012, background): “The polyhedral construction requires expressing (36) by a system of conic quadratic constraints of dimensions three each: (38) (39) Equations (38) and (39) are of the form (40) Ben-Tal and Nemirovski [28] show that (40) can be approximated by a system of linear homogeneous equalities and inequalitie”
On Robustness and Regularization of Structural Support Vector Machines (2014, background): “In general, robust optimization addresses optimization problems in which some degree of uncertainty governs the known parameters of the model (Ben-Tal & Nemirovski, 1998; 1999; 2000; 2001; Bertsimas & Sim, 2004).”
On the Geometric Interpretation of the Nonnegative Rank (2010, background): “This extended formulation is actually a particular case of a construction proposed by Ben-Tal and Nemirovski [4] (see also [27,32]) to find an extended formulation of size O(k) for the regular 2-gon in two dimensions.”
An overview on mathematical programming approaches for the deterministic unit commitment problem in hydro valleys (2017, methodology): “In the same scope, Jabr [70] and Quan [111] propose tighter relaxation method based on second-order cone programming and valid inequalities previously studied in [13,51].”
Adaptive Distributionally Robust Optimization (2019, methodology): “…duality of linear optimization, we have equivalently Therefore, Using the explicit formulation of ¯ W in (8), by weak conic duality (see, for instance, Ben-Tal and Nemirovski (2001a)), we have for all p ∈ [ P ], sup where π p ∈ R L 2 , ∀ p ∈ [ P ] are the dual variables associated with the conic…”
Mixed Integer Linear Programming Formulation Techniques (2015, methodology): “For example, the recent paper by Kaibel and Pashkovich [97] develops a technique for constructing extended formulations that generalizes and unifies approaches for the polyhedral approximation of convex sets [19] and for formulations of combinatorial optimization problems [61].”
A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization (2015, methodology): “[25] used the polynomial-size polyhedral relaxation introduced by Ben-Tal and Nemirovski [9] in their “lifted linear programming” branch-and-bound algorithm for MISOCO problems.”
Higher moment coherent risk measures (2007, neutral): “Following Ben-Tal and Nemirovski (1999), the 2dþ 1-dimensional p-order conic constraint (23) can be represented by a set of 3-dimensional p-order conic inequalities w ðk 1Þ 2j 1 p þ wðk 1Þ2j p h i1=p wðkÞj , j ¼ 1, . . . , 2d k, k ¼ 1, . . . , d, ð24Þ where w ðdÞ 1 t and w ð0Þ j wj ð j ¼ 1, . . . ,…”
Extended Formulations in Combinatorial Optimization (2011, background): “The construction principle of Goemans has been generalized to the framework of reflection relations [22], which, for instance, can be used to obtain small extended formulations for all G-permutahedra of finite reflection groups G (see, e.g., Humphreys [20]), including extended formulations of size O”