Locating the least 2-norm solution of linear programs via a path-following methods

Abstract. A linear program has a unique least 2-norm solution provided that the linear program has a solution. To locate this solution, most of the existing methods were devised to solve certain equivalent perturbed quadratic programs or unconstrained minimization problems. Different from these traditional methods, we provide in this paper a new theory and an effective numerical method to seek the least 2-norm solution of a linear program. The essence of this method is a (interior-point-like) path-following algorithm that traces a newly introduced regularized central path which is fairly different from the central path used in interior-point methods. One distinguishing feature of the method is that it imposes no assumption on the problem. The iterates generated by this algorithm converge to the least 2-norm solution whenever the linear program is solvable; otherwise, the iterates converge to a point which gives a minimal KKT residual when the linear program is unsolvable. Key words. Linear programming, path-following algorithm, regularized central path, least 2-norm solution. AMS subject classifications. 90C05, 90C33, 90C51, 65K05 1. Introduction. Conside