ACCELERATION AND PARALLELIZATION OF THE PATH-FOLLOWING INTERIOR POINT METHOD FOR A LINEARLY CONSTRAINED CONVEX QUADRATIC PROBLEM

被引：13

作者：

Nesterov, Y. ^{[1
]}

Nemirovsky, A. ^{[1
]}

机构：

[1] USSR Acad Sci, Cent Econ & Math Inst, Moscow 117418, Russia

来源：

SIAM JOURNAL ON OPTIMIZATION | 1991年 / 1卷 / 04期

关键词：

interior point methods; polynomial time algorithms; parallel computations;

D O I：

10.1137/0801033

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, the strategies for acceleration of the path-following polynomial time interior point method for linear and linearly constrained quadratic programming problems are studied. These strategies are based on (i) exploiting the results of computations done at the previous iterations (Karmarkar's acceleration scheme and a scheme based on the preconditioned conjugate gradient method); (ii) implementation of "fast" linear algebra routines; (iii) parallel computations.

引用

页码：548 / 564

页数：17

共 13 条

[1]

GOLDFARB D., 1988, O N3L PRIMAL INTERIO

[2]

GONZAGA C. C., 1987, ALGORITHM SOLVING LI

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

KARMARKAR, N .

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

[4] A POLYNOMIAL-TIME ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS [J].

KOJIMA, M ;

MIZUNO, S ;

YOSHISE, A .

MATHEMATICAL PROGRAMMING, 1989, 44 (01) :1-26

[5]

KOJIMA M. S., 1988, RES REPORTS INFORM S, VB-217

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

MONTEIRO, RDC ;

ADLER, I .

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

[7] INTERIOR PATH FOLLOWING PRIMAL-DUAL ALGORITHMS .1. LINEAR-PROGRAMMING [J].

MONTEIRO, RDC ;

ADLER, I .

MATHEMATICAL PROGRAMMING, 1989, 44 (01) :27-41

[8]

Nesterov Yu, 1989, SELF CONCORDANT FUNC

[9]

NESTEROV Yu. E., 1988, IZV AKAD NAUK SSSR T, V3, P3

[10]

NESTEROV Yu. E., 1988, POLYNIMIAL TIME ITE

← 1 2 →