On the second-order feasibility cone: Primal-dual representation and efficient projection

We study the second-order feasibility cone F = {y ∈ ℝⁿ : ∥ My ∥ ≤ 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 ∈ ℝⁿ onto F: miny{∥ y -x∥ : ∥ My ∥ ≤ 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 ε, whose computational complexity is bounded by O(mn²+n ln ln(1/ε)+ n ln ln(1/min{width(F), width(F^*)})) operations. Here width(F) and width (F^*) denote the width of F and F^*, respectively. We also perform computational tests that indicate that the method is extremely efficient in practice. © 2008 Society for Industrial and Applied Mathematics.

Duke Scholars

Author Alexandre Belloni Fuqua School of Business