ON THE IMPLEMENTATION OF A PRIMAL-DUAL INTERIOR POINT METHOD
ON THE IMPLEMENTATION OF A PRIMAL-DUAL INTERIOR POINT METHOD
复制标题
DOI：
10.1137/0802028
复制
发表时间：
1992-11-01
影响因子：
3.1
通讯作者：
Mehrotra, Sanjay
中科院分区：
文献类型：
--
作者：
Mehrotra, Sanjay
给出了一种二阶原对偶内点法的实现方法。它使用二阶泰勒多项式来近似原对偶轨迹。二阶导数的计算与定心方向的计算相结合。这种方法的计算不要求原解和对偶解可行。给出了计算目标轨迹的所有高阶导数的表达式。该实现确保在每次迭代中适当的势函数减少一个常量。这种方法有几个显著的特点。给出了一种估计定心参数的自适应启发式算法。用于计算步长的方法也是自适应的。给出了一种新的计算起点的实用方法。这种方法对称地处理原始问题和对偶问题。本文给出了netlib中可用问题子集的计算结果。在相互测试的问题上，结果表明，所提出的方法比Lustig， Marsten和Shanno Tech提出的实现所需的迭代次数减少了大约40%。Rep. TR J-89-11, Georgia institute of Technology, Atlanta, 1989]。与Adler、Karmarkar、Resende和Veiga [Math]中的双仿射缩放方法相比，它需要的迭代次数减少了大约50%。Programming, 44 (1989), pp. 297-336]，与同一篇论文中的二阶对偶仿射缩放方法相比，迭代次数减少了35%。该方法对定心参数的估计、步长和起始点的确定都有助于减少迭代次数。然而，由于二阶导数的使用的贡献是最显著的。在测试的问题中，平均而言，显示的实现比Lustig， Marsten和Shanno描述的OB1（02/90版本）快大约两倍，比Murtagh和Saunders描述的MINOS 5.3快2.5倍[Tech.众议员SOL 83-20，斯坦福大学运筹部，斯坦福大学，加利福尼亚州，1983]。
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 computations 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 approach for estimating the centering parameter and finding the step length and the starting point have contributed to the reduction in the number of iterations. However, the contribution due to the use of second derivative is most significant.On the tested problems, on the average the implementation shown was found to be approximately two times faster than OB1 (version 02/90) described in Lustig, Marsten, and Shanno and 2.5 times faster than MINOS 5.3 described in Murtagh and Saunders [Tech. Rep. SOL 83-20, Dept. of Operations Research, Stanford Univ., Stanford, CA, 1983].