A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem

被引：18

作者：

Kheirfam, B. ^{[1
]}

Mahdavi-Amiri, N. ^{[2
]}

机构：

[1] Azarbaijan Shahid Madani Univ, Dept Appl Math, Tabriz, Iran

[2] Sharif Univ Technol, Dept Math Sci, Tehran, Iran

来源：

OPTIMIZATION LETTERS | 2014年 / 8卷 / 03期

关键词：

Linear complementarity problem; Full Nesterov-Todd step; Small-update method; Polynomial complexity; POLYNOMIAL-TIME; JORDAN ALGEBRAS; CONVERGENCE;

D O I：

10.1007/s11590-013-0618-5

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a new primal-dual path-following interior-point algorithm for linear complementarity problem over symmetric cones. The algorithm is based on a reformulation of the central path for finding the search directions. For a full Nesterov-Todd step feasible interior-point algorithm based on the search directions, the complexity bound of the algorithm with the small update approach is the best available.

引用

页码：1017 / 1029

页数：13

共 22 条

[1]

Cottle Richard W, 1992, THE LINEAR COMPLEMEN

[2] Linear systems in Jordan algebras and primal-dual interior-point algorithms [J].

Faybusovich, L .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1997, 86 (01) :149-175

[3] A Jordan-algebraic approach to potential-reduction algorithms [J].

Faybusovich, L .

MATHEMATISCHE ZEITSCHRIFT, 2002, 239 (01) :117-129

[4] Euclidean Jordan algebras and interior-point algorithms [J].

Faybusovich, L .

POSITIVITY, 1997, 1 (04) :331-357

[5] Full Nesterov-Todd step infeasible interior-point method for symmetric optimization [J].

Gu, G. ;

Zangiabadi, M. ;

Roos, C. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 214 (03) :473-484

[6] Barrier functions in interior point methods [J].

Guler, O .

MATHEMATICS OF OPERATIONS RESEARCH, 1996, 21 (04) :860-885

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

KARMARKAR, N .

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

[8] Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J].

Kojima, M ;

Shindoh, S ;

Hara, S .

SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (01) :86-125

[9] Kernel-Based Interior-Point Methods for Monotone Linear Complementarity Problems over Symmetric Cones [J].

Lesaja, G. ;

Roos, C. .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2011, 150 (03) :444-474

[10] Primal-dual interior-point methods for self-scaled cones [J].

Nesterov, YE ;

Todd, MJ .

SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (02) :324-364

← 1 2 3 →