文档详情

《《1992 On the implementation of a primal-dual interior point method》.pdf

发布:2015-09-28约8.88万字共27页下载文档
文本预览下载声明
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
显示全部
相似文档