Content area
In this document, we study the use of the nonnegative least squares method to solve the assignment problem (via the primal-dual method), the maximum cardinality matching and also the minimization of separable differentiable convex functions. In addition to that, we propose a new method whereby the solution of the assignment problem can be found by solving a single nonnegative least squares problem.
The motivation for studying the nonnegative least squares primal-dual algorithm comes from its efficiency in solving linear programming problems as was shown empirically in [6]. (See also [19]). The first primal-dual linear programming algorithm was formulated for solving the assignment problem. It was discovered by Harold Kuhn [21], and called the Hungarian method in honor of two Hungarian mathematicians whose work was used in developing the algorithm. The Hungarian method proved to be an effective method for solving assignment problems. Any new primal-dual algorithm must be effective on some class of problems to be of interest. In particular, it must be compared to the Hungarian method for the assignment problem. With this in mind, we have tried to determine how the nonnegative least squares primal-dual algorithm relates to the Hungarian method for the assignment problem. We have established several connections between the two algorithms, and more generally, between the nonnegative least squares algorithm and the weighted matching problem on general graphs. In [6], the authors showed that the nonnegative least squares algorithm is a steepest ascent method for solving the dual of a linear programming problem. This means that this method should require fewer steps, on average, than the Hungarian method. That this is the case was shown empirically in [6], and more evidence that this is the case will be offered in Chapter 1. Our main result is a procedure for obtaining the solution of an assignment problem by solving a single nonnegative least squares problem.
In Chapter 2, we discuss the theory behind the nonnegative least squares algorithm, the primal-dual algorithm and the nonnegative least squares primal-dual algorithm developed by E. Barnes et al. in [6].
In Chapter 3, we devise a fast procedure to compute the unrestricted least squares solution by exploiting the special structure of the incidence matrix of a bipartite graph. First, we show how computing the unrestricted least squares is used in a modified version of the nonnegative least squares algorithm, and, in this way, we derive a very efficient procedure to calculate the new dual direction of the primal-dual method applied to the assignment problem.
In Chapter 4, we explain how to extract a solution for the matching problem from the nonnegative least squares solution. The main idea is to make a connection between solutions obtained by the nonnegative least squares algorithm and the solutions of the maximum cardinality matching problem for the same graph.
In Chapter 5, we look into some theoretical results concerning the solution of minimization of p-norms and separable differentiable convex functions subject to constraint matrices that are incidence matrices.
In Chapter 6, we show that the assignment problem can be reduced to a single nonnegative least squares problem. This means that the primal-dual approach can be made to converge in one step for the assignment problem. This method does not reduce the primal-dual approach to one step for general linear programming problems, but it appears to give a good starting dual feasible point for the general problem.
Throughout this document, we use the acronym NNLS to stand for Nonnegative Least Squares.