On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient Projection

Alexandre Belloni (bellonimit.edu)
Robert M. Freund (rfreundmit.edu)

Abstract: 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.

Keywords: second-order cone, dual cone, projection

Category 1: Linear, Cone and Semidefinite Programming

Citation: MIT Operations Research Center Working Paper, 2006

Download: [PDF]

Entry Submitted: 10/10/2006
Entry Accepted: 10/10/2006
Entry Last Modified: 10/10/2006

Modify/Update this entry