A Newton Method for Linear Programming
Abstract
A 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.
Subject
linear programming
Newton method
Permanent Link
http://digital.library.wisc.edu/1793/64318Citation
02-02