This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Belloni, A. Articles by Vempala, S.

An Efficient Rescaled Perceptron Algorithm for Conic Systems

Fuqua School of Business, Duke University, Durham, North Carolina 27708
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
College of Computing, Georgia Tech, Atlanta, Georgia 30332
abn5{at}duke.edu, http://www.duke.edu/abn5/
rfreund{at}mit.edu, http://web.mit.edu/rfreund/www
vempala{at}cc.gatech.edu, http://www.cc.gatech.edu/vempala/

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 of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/² [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/)) iterations (with high probability), which is theoretically efficient in 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.

Key Words: convex cones; perception; conic system; separation oracle
History: Received: October 10, 2006; revision received: February 10, 2009;