A New Strategy in the Complexity Analysis of an Infeasible-Interior-Point Method for Symmetric Cone Programming

被引：12

作者：

Yang, Ximei ^{[1
,2
]}

Liu, Hongwei ^{[1
]}

Zhang, Yinkui ^{[2
]}

机构：

[1] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China

[2] Henan Normal Univ, Sch Math & Informat Sci, Xinxiang 453007, Henan, Peoples R China

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 2015年 / 166卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Jordan algebra; Symmetric cone programming; Infeasible-interior-point method; Polynomial complexity; POLYNOMIAL CONVERGENCE; ALGORITHMS;

D O I：

10.1007/s10957-014-0670-z

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we give a new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. Using the strategy, we improve the theoretical complexity bound of an infeasible-interior-point method. Convergence is shown for a commutative class of search directions, which includes the Nesterov-Todd direction and the and directions.

引用

页码：572 / 587

页数：16

共 27 条

[1]

Faraut J., 1994, ANAL SYMMETRIC CONE

[2] Linear systems in Jordan algebras and primal-dual interior-point algorithms [J].

Faybusovich, L .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1997, 86 (01) :149-175

[3] Full Nesterov-Todd step infeasible interior-point method for symmetric optimization [J].

Gu, G. ;

Zangiabadi, M. ;

Roos, C. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 214 (03) :473-484

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

Guler, O .

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

[5] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

[6]

Liu C, 2012, THESIS XIDIAN U

[7] 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

[8] 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

[9] 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

[10] FEASIBILITY ISSUES IN A PRIMAL DUAL INTERIOR-POINT METHOD FOR LINEAR-PROGRAMMING [J].

LUSTIG, IJ .

MATHEMATICAL PROGRAMMING, 1990, 49 (02) :145-162

← 1 2 3 →