Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs

被引：90

作者：

Kojima, M

Shida, M

Shindoh, S

机构：

[1] Tokyo Inst Technol, Dept Math & Comp Sci, Meguro Ku, Tokyo 152, Japan

[2] Kanagawa Univ, Dept Math, Kanagawa Ku, Yokohama, Kanagawa 221, Japan

[3] Natl Def Acad, Dept Math & Phys, Yokosuka, Kanagawa 239, Japan

来源：

MATHEMATICAL PROGRAMMING | 1998年 / 80卷 / 02期

关键词：

semidefinite programming; infeasible-interior-point method; predictor-corrector-method; superlinear convergence; primal-dual nondegeneracy;

D O I：

10.1007/BF01581723

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno-Todd-Ye type predictor-corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno-Todd-Ye type predictor-corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：129 / 160

页数：32

共 35 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].