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


Journal Article

We study the second-order feasibility cone F = {y ∈ ℝn : ∥ My ∥ ≤ gTy} for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix MTM - ggT. This representation is used to efficiently solve the problem of projecting an arbitrary point x ∈ ℝn onto F: miny{∥ y -x∥ : ∥ My ∥ ≤ gTy}, 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(mn2+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.

Full Text

Duke Authors

Cited Authors

  • Belloni, A; Freund, RM

Published Date

  • December 1, 2008

Published In

Volume / Issue

  • 19 / 3

Start / End Page

  • 1073 - 1092

International Standard Serial Number (ISSN)

  • 1052-6234

Digital Object Identifier (DOI)

  • 10.1137/06067198X

Citation Source

  • Scopus