  


On the SecondOrder Feasibility Cone: PrimalDual Representation and Efficient Projection
Alexandre Belloni (bellonimit.edu) Abstract: We study the secondorder 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 rescaled 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 interiorpoint method. Keywords: secondorder 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 Modify/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  