Optimization Online


Examples with Decreasing Largest Inscribed Ball for Deterministic Rescaling Algorithms

Dan Li(dal207***at***lehigh.edu)
Tamás Terlaky(terlaky***at***lehigh.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 )


Download: [PDF]

Entry Submitted: 09/18/2015
Entry Accepted: 09/18/2015
Entry Last Modified: 09/18/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society