Skip to main content

An Efficient Rescaled Perceptron Algorithm for Conic Systems

Publication ,  Journal Article
Belloni, A; Freund, RM; Vempala, S
Published in: Mathematics of Operations Research
August 1, 2009

The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width t of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/t2 [see Rosenblatt, F. 1962. Principles of Neurodynamics. Spartan Books, Washington, DC]. Dunagan and Vempala [Dunagan, J., S. Vempala. 2007. A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming 114(1) 101-114] have developed a rescaled version of the perceptron algorithm with an improved complexity of O(n ln(1/t)) iterations (with high probability), which is theoretically efficient in t and, in particular, is polynomial time in the bit-length model. We explore extensions of the concepts of these perceptron methods to the general homogeneous conic system Ax ∈ int k, where K is a regular convex cone. We provide a conic extension of the rescaled perceptron algorithm based on the notion of a deep-separation oracle of a cone, which essentially computes a certificate of strong separation. We show that the rescaled perceptron algorithm is theoretically efficient if an efficient deep-separation oracle is available for the feasible region. Furthermore, when K is the cross-product of basic cones that are either half-spaces or second-order cones, then a deep-separation oracle is available and, hence, the rescaled perceptron algorithm is theoretically efficient. When the basic cones of K include semidefinite cones, then a probabilistic deep-separation oracle for K can be constructed that also yields a theoretically efficient version of the rescaled perceptron algorithm. © 2009 INFORMS.

Duke Scholars

Published In

Mathematics of Operations Research

DOI

EISSN

1526-5471

ISSN

0364-765X

Publication Date

August 1, 2009

Volume

34

Issue

3

Start / End Page

621 / 641

Related Subject Headings

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

Citation

APA
Chicago
ICMJE
MLA
NLM
Belloni, A., Freund, R. M., & Vempala, S. (2009). An Efficient Rescaled Perceptron Algorithm for Conic Systems. Mathematics of Operations Research, 34(3), 621–641. https://doi.org/10.1287/moor.1090.0388
Belloni, A., R. M. Freund, and S. Vempala. “An Efficient Rescaled Perceptron Algorithm for Conic Systems.” Mathematics of Operations Research 34, no. 3 (August 1, 2009): 621–41. https://doi.org/10.1287/moor.1090.0388.
Belloni A, Freund RM, Vempala S. An Efficient Rescaled Perceptron Algorithm for Conic Systems. Mathematics of Operations Research. 2009 Aug 1;34(3):621–41.
Belloni, A., et al. “An Efficient Rescaled Perceptron Algorithm for Conic Systems.” Mathematics of Operations Research, vol. 34, no. 3, Aug. 2009, pp. 621–41. Scopus, doi:10.1287/moor.1090.0388.
Belloni A, Freund RM, Vempala S. An Efficient Rescaled Perceptron Algorithm for Conic Systems. Mathematics of Operations Research. 2009 Aug 1;34(3):621–641.

Published In

Mathematics of Operations Research

DOI

EISSN

1526-5471

ISSN

0364-765X

Publication Date

August 1, 2009

Volume

34

Issue

3

Start / End Page

621 / 641

Related Subject Headings

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