On the second-order feasibility cone: Primal-dual representation and efficient projection
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.
Duke Scholars
Published In
DOI
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics
Citation
Published In
DOI
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics