- 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/2006Entry Accepted: 10/10/2006Entry Last Modified: 10/10/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.