On the Minimum Norm Solution of Linear Programs

Author: Kanzow C.   Qi H.   Qi L.  

Publisher: Springer Publishing Company

ISSN: 0022-3239

Source: Journal of Optimization Theory and Applications, Vol.116, Iss.2, 2003-02, pp. : 333-345

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper describes a new technique to find the minimum norm solution of a linear program. The main idea is to reformulate this problem as an unconstrained minimization problem with a convex and smooth objective function. The minimization of this objective function can be carried out by a Newton-type method which is shown to be globally convergent. Furthermore, under certain assumptions, this Newton-type method converges in a finite number of iterations to the minimum norm solution of the underlying linear program.