A POLYNOMIAL-TIME PREDICTOR-CORRECTOR ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY PROBLEMS

被引：9

作者：

Ding, Jiu ^{[1
]}

Li, Tien-Yien ^{[1
]}

机构：

[1] Michigan State Univ, Dept Math, E Lansing, MI 48824 USA

来源：

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

基金：

美国国家科学基金会;

关键词：

linear complementarity problem; polynomial-time algorithm; predictor-corrector method;

D O I：

10.1137/0801007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A polynomial-time algorithm for a class of linear complementarity problems with positive semidefinite matrices is presented. The method is based on a one-step Euler's prediction and one-step Newton's correction procedure to follow the homotopy path defined as the set {(x, y) epsilon R-+(n): x(i)Y(i)=mu, i = 1,.., n, mu > 0, y = Mx + q}, and solves the problem in O(n(3.5)L) arithmetic operations. Moreover, after one iteration the value x(T)y decreases with the ratio at least (1-(2/5 root n)).

引用

页码：83 / 92

页数：10

共 19 条

[1]

DING J., 1990, ARAB J SCI ENG, V15, P679

[2]

Fiacco AV, 1990, NONLINEAR PROGRAMMIN

[3]

FRISH K. R., 1955, LOGARITHMIC POTENTIA

[4]

GEORG K., 1983, MATH PROGRAMMING STA

[5]

GONZAGA C. C., 1989, ES21189 COPPE FED U

[6]

GONZAGA C. C., 1989, ES2089 COPPE FED U R

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

KARMARKAR, N .

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

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

[9]

KOJIMA M., 1987, B188 TOK I TECHN DEP

[10]

KOJIMA M., 1987, O N L POTENTIAL REDU

← 1 2 →