《《1992 On the implementation of a primal-dual interior point method》.pdf
文本预览下载声明
SIAM J. OPTIMIZATION (C) 1992 Society for Industrial and Applied Mathematics
Vol. 2, No. 4, pp. 575-601, November 1992 003
ON THE IMPLEMENTATION OF A PRIMAL-DUAL
INTERIOR POINT METHOD*
SANJAY MEHROTRAt
Abstract. This paper gives an approach to implementing a second-order primal-dual interior point
method. It uses a Taylor polynomial of second order to approximate a primal-dual trajectory. The computa-
tions for the second derivative are combined with the computations for the centering direction. Computations
in this approach do not require that primal and dual solutions be feasible. Expressions are given to compute
all the higher-order derivatives of the trajectory of interest. The implementation ensures that a suitable
potential function is reduced by a constant amount at each iteration.
There are several salient features of this approach. An adaptive heuristic for estimating the centering
parameter is given. The approach used to compute the step length is also adaptive. A new practical approach
to compute the starting point is given. This approach treats primal and dual problems symmetrically.
Computational results on a subset of problems available from netlib are given. On mutually tested
problems the results show that the proposed method requires approximately 40 percent fewer iterations
than the implementation proposed in Lustig, Marsten, and Shanno Tech. Rep. TR J-89-11, Georgia Inst.
of Technology, Atlanta, 1989]. It requires approximately 50 percent fewer iterations than the dual affine
scaling method in Adler, Karmarkar, Resende, and Veiga [Math. Programming, 44 (1989), pp. 297-336],
and 35 percent fewer iterations than the second-order dual affine scaling method in the same paper. The
new approa
显示全部