Skip to main content

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

Publication ,  Journal Article
Belloni, A; Freund, RM
Published in: SIAM Journal on Optimization
December 1, 2008

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

SIAM Journal on Optimization

DOI

ISSN

1052-6234

Publication Date

December 1, 2008

Volume

19

Issue

3

Start / End Page

1073 / 1092

Related Subject Headings

  • Operations Research
  • 4901 Applied mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Belloni, A., & Freund, R. M. (2008). On the second-order feasibility cone: Primal-dual representation and efficient projection. SIAM Journal on Optimization, 19(3), 1073–1092. https://doi.org/10.1137/06067198X
Belloni, A., and R. M. Freund. “On the second-order feasibility cone: Primal-dual representation and efficient projection.” SIAM Journal on Optimization 19, no. 3 (December 1, 2008): 1073–92. https://doi.org/10.1137/06067198X.
Belloni A, Freund RM. On the second-order feasibility cone: Primal-dual representation and efficient projection. SIAM Journal on Optimization. 2008 Dec 1;19(3):1073–92.
Belloni, A., and R. M. Freund. “On the second-order feasibility cone: Primal-dual representation and efficient projection.” SIAM Journal on Optimization, vol. 19, no. 3, Dec. 2008, pp. 1073–92. Scopus, doi:10.1137/06067198X.
Belloni A, Freund RM. On the second-order feasibility cone: Primal-dual representation and efficient projection. SIAM Journal on Optimization. 2008 Dec 1;19(3):1073–1092.

Published In

SIAM Journal on Optimization

DOI

ISSN

1052-6234

Publication Date

December 1, 2008

Volume

19

Issue

3

Start / End Page

1073 / 1092

Related Subject Headings

  • Operations Research
  • 4901 Applied mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics