HYPER-RECTANGLE COVER THEORY AND ITS APPLICATIONS

Abstract

In this thesis, we propose a novel hyper-rectangle cover theory which provides a new approach to analyzing mathematical problems with nonnegativity constraints on variables. In this theory, two fundamental concepts, cover order and cover length, are introduced and studied in details.

In the same manner as determining the rank of a matrix, we construct a specific e ́chelon form of the matrix to obtain the cover order of a given matrix efficiently and effectively. We discuss various structures of the e ́chelon form for some special cases in detail. Based on the structure and properties of the constructed e ́chelon form, the concepts of non-negatively linear independence and non-negatively linear dependence are developed. Using the properties of the cover order, we obtain the necessary and sufficient conditions for the existence and uniqueness of the solutions for linear equations system with nonnegativity constraints on variables for both homogeneous and non-homogeneous cases. In addition, we apply the cover theory to analyze some typical problems in linear algebra and optimization with nonnegativity constraints on variables, including linear programming problems and non-negative least squares (NNLS) problems. For linear programming problem, we study the three possible behaviors of the solutions for it through hyper-rectangle cover theory, and show that a series of feasible solutions for the problem with the zero-cover e ́chelon form structure. On the other hand, we develop a method to obtain the cover length of the covered variable. In the process, we discover the relationship between the cover length determination problem and the NNLS problem. This enables us to obtain an analytical optimal value for the NNLS problem.