Exploring the Power of Rescaling

The goal of our research is a comprehensive exploration of the power of rescaling to improve the efficiency of various algorithms for linear optimization and related problems. Linear optimization and linear feasibility problemsarguably yield the fundamental problems of optimization. Advances in solvingthese problems impact the core of optimization theory, and consequently itspractical applications. The development and analysis of solution methods for linear optimization is one of the major topics in optimization research. Although the polynomial time ellipsoid method has excellent theoretical properties,however it turned out to be inefficient in practice.Still today, in spite of the dominance of interior point methods, various algorithms, such as perceptron algorithms, rescaling perceptron algorithms,von Neumann algorithms, Chubanov\u27s method, and linear optimization related problems,such as the colorful feasibility problem -- whose complexity status is still undecided --are studied.Motivated by the successful application of a rescaling principle on the perceptron algorithm,our research aims to explore the power of rescaling on other algorithms too,and improve their computational complexity. We focus on algorithms forsolving linear feasibility and related problems, whose complexity depend on a quantity $\rho$, which is a condition number for measuring the distance to the feasibility or infeasibility of the problem.These algorithms include the von Neumann algorithm and the perceptron algorithm. First, we discuss the close duality relationship between the perceptron and the von Neumann algorithms. This observation allows us to transit one algorithm as a variant of the other, as well as we can transit their complexity results. The discovery of this duality not only provides a profound insight into both of the algorithms, but also results in new variants of the algorithms.Based on this duality relationship, we propose a deterministic rescaling von Neumann algorithm. It computationally outperforms the original von Neumann algorithm. Though its complexity has not been proved yet, we construct a von Neumann example which shows that the rescaling steps cannot keep the quantity $\rho$ increasing monotonically. Showing a monotonic increase of $\rho$ is a common technique used to prove the complexity of rescaling algorithms. Therefore, this von Neumann example actually shows that another proof method needs to be discovered in order to obtain the complexity of this deterministic rescaling von Neumann algorithm. Furthermore, this von Neumann example serves as the foundation of a perceptron example, which verifies that $\rho$ is not always increasing after one rescaling step in the polynomial time deterministic rescaling perceptron algorithm either.After that, we adapt the idea of Chubanov\u27s method to our rescaling frame and develop a polynomial-time column-wise rescaling von Neumann algorithm. Chubanov recently proposed a simple polynomial-time algorithm for solving homogeneous linear systems with positive variables. The Basic Procedure of Chubanov\u27s method can either find a feasible solution, or identify an upper bound for at least one coordinate of any feasible solution. The column-wise rescaling von Neumann algorithm combines the Basic Procedure with column-wise rescaling to identify zero coordinates in all feasible solutions and remove the corresponding columns from the coefficient matrix. This is the first variant of the von Neumann algorithm with polynomial-time complexity. Furthermore, compared with the original von Neumann algorithm which returns an approximate solution, this rescaling variant guarantees an exact solution for feasible problems.Finally, we develop the methodology of higher order rescaling and propose a higher-order perceptron algorithm.We implement the perceptron improvement phase by utilizing parallel processors.Therefore, in a multi-core environment we may obtain several rescaling vectors without extra wall-clock time.Once we use these rescaling vectors in a single higher-order rescaling step, better rescaling ratesmay be expected and thus computational efficiency is improved