ISSN:
1573-2878
Keywords:
Linear programming
;
interior-point methods
;
polynomial covnergence
;
quadratic convergence
;
superlinear convergence
;
least-squares problems
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02192566
Permalink
