Show simple item record

dc.contributor.authorMangasarian, Olvi
dc.description.abstractA fast Newton method is proposed for solving linear programs with a very large ( 106) number of constraints and a moderate ( 102) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for nite values of the penalty parameter but not for the primal linear program. Solving the dual for a nite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to dual problem can be used to generate an accurate primal solution if m n and the primal solution is unique. Utilizing these facts, a fast globally convergent nitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.en
dc.subjectlinear programmingen
dc.subjectNewton methoden
dc.titleA Newton Method for Linear Programmingen
dc.typeTechnical Reporten

Files in this item


This item appears in the following Collection(s)

  • DMI Technical Reports
    DMI Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record