A primal-dual predictor-corrector interior-point method for symmetric cone programming with O(r log E-1) iteration complexity

被引：1

作者：

Shahraki, M. Sayadi ^{[1
]}

Mansouri, H. ^{[2
]}

Zangiabadi, M. ^{[2
]}

机构：

[1] Inst Res Fundamental Sci IPM, Sch Math, POB 19395-5746, Tehran, Iran

[2] Shahrekord Univ, Fac Math Sci, Dept Appl Math, Shahrekord, Iran

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2017年 / 94卷 / 10期

关键词：

Euclidean Jordan algebra; Symmetric cone; interior-point methods; predictor-corrector algorithm; wide neighbourhood; 90C05; 90C51; PATH-FOLLOWING METHOD; WIDE NEIGHBORHOOD; SEMIDEFINITE OPTIMIZATION; JORDAN ALGEBRAS; ALGORITHMS;

D O I：

10.1080/00207160.2016.1274742

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper,we propose a new predictor-corrector interior-point method for symmetric cone programming. This algorithm is based on a wide neighbourhood and the Nesterov-Todd direction. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of , where r is the rank of the associated Euclidean Jordan algebras. In particular, the complexity bound is , where is a given tolerance. To our knowledge, this is the best complexity result obtained so far for interior-point methods with a wide neighbourhood over symmetric cones. The numerical results show that the proposed algorithm is effective.

引用

页码：1998 / 2010

页数：13

共 30 条

[11] Barrier functions in interior point methods [J].

Guler, O .

MATHEMATICS OF OPERATIONS RESEARCH, 1996, 21 (04) :860-885

[12]

Kojima M., 1989, Progress in Mathematical Programming: Interior-Point and Related Methods

[13] A NEW CLASS OF LARGE NEIGHBORHOOD PATH-FOLLOWING INTERIOR POINT ALGORITHMS FOR SEMIDEFINITE OPTIMIZATION WITH O(√n log Tr(X0 S0)/ε) ITERATION COMPLEXITY [J].

Li, Yang ;

Terlaky, Tamas .

SIAM JOURNAL ON OPTIMIZATION, 2010, 20 (06) :2853-2875

[14]

Liu C, 2012, THESIS

[15] Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones [J].

Liu, Changhe ;

Liu, Hongwei ;

Liu, Xinze .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2012, 154 (03) :949-965

[16] A New Wide Neighborhood Primal-Dual Infeasible-Interior-Point Method for Symmetric Cone Programming [J].

Liu, Hongwei ;

Yang, Ximei ;

Liu, Changhe .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2013, 158 (03) :796-815

[17] Path-following interior point algorithms for the Cartesian P *(κ)-LCP over symmetric cones [J].

Luo ZiYan ;

Xiu NaiHua .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2009, 52 (08) :1769-1784

[18] Simplified O(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps [J].

Mansouri, H. ;

Roos, C. .

OPTIMIZATION METHODS & SOFTWARE, 2007, 22 (03) :519-530

[19] ON THE IMPLEMENTATION OF A PRIMAL-DUAL INTERIOR POINT METHOD [J].

Mehrotra, Sanjay .

SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (04) :575-601

[20] ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING [J].

MIZUNO, S ;

TODD, MJ ;

YE, YY .

MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) :964-981

← 1 2 3 →