Shane Henderson (Cornell University)


Title:  Replacing Ellipsoids by Cylinders: A Probabilistic Analysis of Low-Rank

Approximations in Optimization Problems


Joint work with Spyros Schismenos and Adrian Lewis


A recent effort in designing external-beam radiation therapy for cancer treatment gave rise to a second-order cone program, which is an optimization problem where the feasible region is essentially an intersection of ellipsoids. The number and dimension of the ellipsoids meant that the problem could not even be stored, much less solved, despite the availability of efficient numerical algorithms for this kind of problem. The positive-definite matrices that specify the ellipsoids were replaced by low-rank approximations, which correspond to approximating ellipsoids by infinitely long cylinders. The computational results suggested that the approach worked quite well.


In this talk, I will give a probabilistic analysis of the use of low-rank approximations in a stylized second-order cone program. The optimization problem itself is random, and we consider the relative error between the optimal objective values of the original problem and its low-rank approximation. Our results give estimates on the rate at which the number of constraints should grow as the dimension of the problem increases to ensure small relative error, for different kinds of low-rank approximations.