General Central Path Following Algorithm for Convex Quadratic Programming

被引：0

作者：

Chen, Dong-hai ^{[1
]}

Zhang, Ming-wang ^{[1
]}

机构：

[1] China Three Gorges Univ, Coll Sci, Yichang 443002, Hubei, Peoples R China

来源：

2011 INTERNATIONAL CONFERENCE ON FUTURE COMPUTER SCIENCE AND APPLICATION (FCSA 2011), VOL 3 | 2011年

关键词：

convex quadratic programming; interior point methods; general central path following algorithm; polynomial complexity;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A general central path following algorithm for convex quadratic programming with linear constrains is presented. Any primal-dual feasible interior point can be taken as initial point of the algorithm. Each iteration chooses a new direction with the convex combination of the affine-scaling step and centering step, and uses a pure Newton step with the largest possible reduction in duality gap. The algorithm maintains the O(root nL) iteration complexity.

引用

页码：56 / 60

页数：5

共 5 条

[1] AI W.B., 2001, ACTA MATH APPL SIN-E, V7, P296
[2] PATH-FOLLOWING METHODS FOR LINEAR-PROGRAMMING
GONZAGA, CC
[J]. SIAM REVIEW, 1992, 34 (02) : 167 - 224
[3] The largest step path following algorithm for monotone linear complementarity problems
Gonzaga, CC
[J]. MATHEMATICAL PROGRAMMING, 1997, 76 (02) : 309 - 332
[4] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING
KARMARKAR, N
[J]. COMBINATORICA, 1984, 4 (04) : 373 - 395
[5] Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8

← 1 →