Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results
Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results
复制标题
DOI：
10.1137/s1052623496304700
复制
发表时间：
1998-08-01
影响因子：
3.1
通讯作者：
Overton, ML
中科院分区：
文献类型：
--
作者：
Alizadeh, F;Haeberly, JPA;Overton, ML
考虑半定规划的原始 - 对偶内点路径跟踪方法。基于应用于三个方程（原始可行性、对偶可行性以及某种形式的中心条件）的牛顿法，讨论了几种变体。重点关注三种此类算法，称为XZ、XZ + ZX和Q方法。对于XZ + ZX和Q算法，在非退化假设下，牛顿系统定义良好，并且其雅可比矩阵在解处非奇异。在非退化假设和一个额外的秩假设下，相关的舒尔补矩阵在中心路径上具有无界的条件数。讨论了实际方面的问题，包括梅赫罗特拉预测 - 校正变体以及数值稳定性问题。与所考虑的其他方法相比，XZ + ZX方法在靠近边界的能力方面更具鲁棒性，收敛更快，并能达到更高的精度。
Primal-dual interior-point path-following methods for semidefinite programming are considered. Several variants are discussed, based on Newton's method applied to three equations: primal feasibility, dual feasibility, and some form of centering condition. The focus is on three such algorithms, called the XZ, XZ+ZX, and Q methods. For the XZ+ZX and Q algorithms, the Newton system is well defined and its Jacobian is nonsingular at the solution, under nondegeneracy assumptions. The associated Schur complement matrix has an unbounded condition number on the central path under the nondegeneracy assumptions and an additional rank assumption. Practical aspects are discussed, including Mehrotra predictor-corrector variants and issues of numerical stability. Compared to the other methods considered, the XZ+ZX method is more robust with respect to its ability to step close to the boundary, converges more rapidly, and achieves higher accuracy.