Solving Conic Systems via Projection and Rescaling

• 成果类型: Article
• 署名作者: Pena, Javier; Soheili, Negar
• 署名单位: Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1105-4
• 发表日期: 2017
• 页码: 87-111
• 关键词: interior-point algorithms; perceptron; preconditioners

摘要

We propose a simple projection and rescaling algorithm to solve the feasibility problem find x is an element of L boolean AND Omega, where L and Omega are respectively a linear subspace and the interior of a symmetric cone in a finite-dimensional vector space V. This projection and rescaling algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov's projection-based method for linear feasibility problems. As in these predecessors, each main iteration of our algorithm contains two steps: a basic procedure and a rescaling step. When L boolean AND Omega not equal empty set, the projection and rescaling algorithm finds a point x is an element of L boolean AND Omega in at most O(log(1/delta(L boolean AND Omega)) iterations, where delta(L boolean AND Omega) is an element of (01, 1] is a measure of the most interior point in L boolean AND Omega. The ideal value delta(L boolean AND Omega) = 1 is attained when L boolean AND Omega contains the center of the symmetric cone Omega. We describe several possible implementations for the basic procedure including a perceptron scheme and a smooth perceptron scheme. The perceptron scheme requires O(r(4)) perceptron updates and the smooth perceptron scheme requires O(r(2)) smooth perceptron updates, where r stands for the Jordan algebra rank of V.