We study the second-order feasibility cone F = { y : \| My \| \le g^Ty } for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix M^TM - gg^T. This representation is used to efficiently solve the problem of projecting an arbitrary point x \in \RR^n onto F : minimmize_y {\|y- x\| : \|My\| \le g^Ty }, which aside from theoretical interest also arises as a necessary subroutine in the re-scaled perceptron algorithm. We develop a method for solving the projection problem to an accuracy epsilon whose computational complexity is bounded by O(mn^2 + n \ln \ln (1/epsilon) + n \ln \ln(1/ minimum { width(F), width(F^*)})) operations. Here the width(F),width(F^*) denotes the widths of F and F^*, respectively. This is a substantial improvement over the complexity of a generic interior-point method.
Citation
MIT Operations Research Center Working Paper, 2006
Article
View On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient Projection