  We consider minimizing a conic quadratic objective over a polyhedron. Such
problems arise in parametric value-at-risk minimization, portfolio
optimization, and robust optimization with ellipsoidal objective uncertainty;
and they can be solved by polynomial interior point algorithms for conic
quadratic optimization. However, interior point algorithms are not well-suited
for branch-and-bound algorithms for the discrete counterparts of these problems
due to the lack of effective warm starts necessary for the efficient solution
of convex relaxations repeatedly at the nodes of the search tree.
  In order to overcome this shortcoming, we reformulate the problem using the
perspective of the quadratic function. The perspective reformulation lends
itself to simple coordinate descent and bisection algorithms utilizing the
simplex method for quadratic programming, which makes the solution methods
amenable to warm starts and suitable for branch-and-bound algorithms. We test
the simplex-based quadratic programming algorithms to solve convex as well as
discrete instances and compare them with the state-of-the-art approaches. The
computational experiments indicate that the proposed algorithms scale much
better than interior point algorithms and return higher precision solutions. In
our experiments, for large convex instances, they provide up to 22x speed-up.
For smaller discrete instances, the speed-up is about 13x over a barrier-based
branch-and-bound algorithm and 6x over the LP-based branch-and-bound algorithm
with extended formulations.
