Interior Point Trajectories in Semidefinite Programming
Interior Point Trajectories in Semidefinite Programming
复制标题
半定规划中的内点轨迹
DOI：
10.1137/s105262349630009x
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
K. Scheinberg
中科院分区：
文献类型：
--
作者：
D. Goldfarb;K. Scheinberg
本文研究了半定规划（SDP）中包含中心路的内点轨线。这项工作的灵感来自Megiddo关于线性规划轨迹的开创性工作[ Progress in Math. Programming：Interior-Point Algorithms and Related Methods，N. Megiddo，编，Springer-Verlag，柏林，1989年，第100页。131- 158]。在原始和对偶严格可行性的假设下，我们证明了原始和对偶中心路径的存在，并分别收敛到原始和对偶问题的最优解的解析中心。我们考虑一类轨迹，类似于中心路径，但可以构造通过任何给定的内部可行或不可行点，并研究其收敛性。最后，我们研究了这些轨迹的导数及其收敛性。
In this paper we study interior point trajectories in semidefinite programming (SDP) including the central path of an SDP. This work was inspired by the seminal work of Megiddo on linear programming trajectories [ Progress in Math. Programming: Interior-Point Algorithms and Related Methods, N. Megiddo, ed., Springer-Verlag, Berlin, 1989, pp. 131--158]. Under an assumption of primal and dual strict feasibility, we show that the primal and dual central paths exist and converge to the analytic centers of the optimal faces of, respectively, the primal and the dual problems. We consider a class of trajectories that are similar to the central path but can be constructed to pass through any given interior feasible or infeasible point, and study their convergence. Finally, we study the derivatives of these trajectories and their convergence.