×

Dual barrier functions with superfast rates of convergence for the linear programming problem. (English) Zbl 0631.90036

It is shown that barrier functions applied to the dual linear program can be modified to give multiplier estimates that converge to the solution of the primal problem. Newton’s method is considered for implementing this approach and numerical results presented. It has been shown that there is a connection between these methods and Karmarkar’s algorithm, but for the class of problems considered further improvements are still required before those methods become competitive with active set methods.

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI