- Examples with Decreasing Largest Inscribed Ball for Deterministic Rescaling Algorithms Dan Li(dal207lehigh.edu) Tamás Terlaky(terlakylehigh.edu) Abstract: Recently, Pena and Soheili presented a deterministic rescaling perceptron algorithm and proved that it solves a feasible perceptron problem in $O(m^2n^2\log(\rho^{-1}))$ perceptron update steps, where $\rho$ is the radius of the largest inscribed ball. The original stochastic rescaling perceptron algorithm of Dunagan and Vempala is based on systematic increase of $\rho$, while the proof of Pena and Soheili is based on the increase of the volume of a so-called cap. In this note we present a perceptron example to show that with this deterministic rescaling method, $\rho$ may decrease after one rescaling step. Furthermore, inspired by our previous work on the duality relationship between the perceptron and the von Neumann algorithms, we propose a deterministic rescaling von Neumann algorithm which is a direct transformation of the deterministic rescaling perceptron algorithm. Though the complexity of this algorithm is not proved yet, we show by constructing a von Neumann example that $\rho$ does not increase monotonically for the deterministic rescaling von Neumann algorithm either. The von Neumann example serves as the foundation of the perceptron example. This example also shows that proving the complexity of the rescaling von Neumann algorithm cannot be based on monotonic expansion of $\rho$. At last, we present computational results of the deterministic rescaling von Neumann algorithm. The results show that the performance of the rescaling algorithm is improved compared with the original von Neumann algorithm when solving the test problems. Keywords: Rescaling perceptron algorithm, the largest inscribed ball, von Neumann algorithm, linear feasibility problem Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF]Entry Submitted: 09/18/2015Entry Accepted: 09/18/2015Entry Last Modified: 09/18/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.