An Efficient Rescaled Perceptron Algorithm for Conic Systems

• 成果类型: Article
• 署名作者: Belloni, Alexandre; Freund, Robert M.; Vempala, Santosh
• 署名单位: Duke University; Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0388
• 发表日期: 2009
• 页码: 621-641
• 关键词: polynomial-time algorithm; complexity; PROGRAMS

摘要

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