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

GONZAGA, CC .

SIAM REVIEW, 1992, 34 (02) :167-224

[3] The largest step path following algorithm for monotone linear complementarity problems [J].

Gonzaga, CC .

MATHEMATICAL PROGRAMMING, 1997, 76 (02) :309-332

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

KARMARKAR, N .

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

[5]

Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8

← 1 →