A New Primal-Dual Predictor-Corrector Interior-Point Method for Linear Programming Based on a Wide Neighbourhood

被引：3

作者：

Shahraki, M. Sayadi ^{[1
]}

Mansouri, H. ^{[1
]}

Zangiabadi, M. ^{[1
]}

机构：

[1] Shahrekord Univ, Fac Math Sci, Dept Appl Math, POB 115, Shahrekord, Iran

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 2016年 / 170卷 / 02期

关键词：

Primal-dual interior-point methods; Predictor-corrector method; Wide neighbourhood; ALGORITHMS;

D O I：

10.1007/s10957-016-0927-9

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we propose a new predictor-corrector interior-point algorithm for linear programming based on a wide neighbourhood. In each iteration, the algorithm computes the Ai-Zhang's predictor direction (SIAM J. Optim. 16(2):400-417, 2005) and a new corrector direction, in an attempt to improve its performance. We drive that the duality gap reduces in both predictor and corrector steps. Moreover, we also prove that the complexity of the algorithm coincides with the best iteration bound for small neighbourhood algorithms. Finally, some numerical experiments are provided which reveal capability and effectiveness of the proposed method.

引用

页码：546 / 561

页数：16

共 15 条

[1] An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J].

Ai, WB ;

Zhang, SZ .

SIAM JOURNAL ON OPTIMIZATION, 2005, 16 (02) :400-417

[2] Neighborhood-following algorithms for linear programming [J].

Ai, WB .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2004, 47 (06) :812-820

[3]

Barnes E.R., 1988, TECHNICAL REPORT

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

KARMARKAR, N .

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

[5]

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

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

[7]

Liu CH, 2011, OPTIM LETT, V5, P729, DOI 10.1007/s11590-010-0242-6

[8]

Megiddo N., 1986, PROGR MATH PROGRAMMI

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

[10] INTERIOR PATH FOLLOWING PRIMAL-DUAL ALGORITHMS .2. CONVEX QUADRATIC-PROGRAMMING [J].

MONTEIRO, RDC ;

ADLER, I .

MATHEMATICAL PROGRAMMING, 1989, 44 (01) :43-66

← 1 2 →