POLYHEDRAL APPROXIMATION OF THE SECOND-ORDER CONE : COMPUTATIONAL EXPERIMENTS

A second-order cone program involves the minimization of a linear objective
over the intersection of an affine space and the Cartesian product of
second-order (quadratic) cones. This convex problem includes as special cases
linear optimization and convex quadratically constrained quadratic
optimization, but is less general than semidefinite programming.

Recently, Aharon Ben-Tal and Arkadi Nemirovski presented a polyhedral
approximation of the second-order cone. Namely, they build an
$\epsilon$-approximation of $\mathbb{L}^n$ using $p$ additional (free)
variables and $q$ linear inequalities such that $p, q < O(1) n \ln
\frac{2}{\epsilon - 1}$.

In this talk, we discuss an implementation of this approximating procedure.
We'll present computational results involving two types of second-order cone
problems: multi-load truss topology design problems and linearly constrained
convex quadratic problems.