On the nonnegative least squares

Nonnegative Least Squares;Assignment problem;NNLS primal-dual

Santiago, Claudio Prata ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Nonnegative Least Squares;    Assignment problem;    NNLS primal-dual;   

Others  :  https://smartech.gatech.edu/bitstream/1853/31768/1/santiago_claudio_p_200912_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

In this document, we study the nonnegative least squares primal-dual method for solving linear programming problems. In particular, we investigate connections between this primal-dual method and the classical Hungarian method for the assignment problem.Firstly, we devise a fast procedure for computing the unrestricted least squares solution of a bipartite matching problem by exploiting the special structure of the incidence matrix of a bipartite graph. Moreover, we explain how to extract a solution for the cardinality matching problem from the nonnegative least squares solution. We also give an efficient procedure for solving the cardinality matching problem on general graphs using thenonnegative least squares approach.Next we look into some theoretical results concerning the minimization of p-norms, and separable differentiable convex functions, subject to linear constraints described by node-arc incidence matrices for graphs. Our main result is the reduction of the assignment problem 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.