A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP

被引：4

作者：

Achache M. ^{[1
]}

Khebchache R. ^{[2
]}

机构：

[1] Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas de Sétif1, Sétif

[2] Département de Mathématiques, Faculté des Sciences, Université Ferhat Abbas de Sétif1, Sétif

来源：

Afrika Matematika | 2015年 / 26卷 / 1-2期

关键词：

Short-step primal-dual algorithms; Complexity of algorithms; Interior point methods; Linear complementarity problems;

D O I：

10.1007/s13370-013-0193-z

中图分类号：

学科分类号：

摘要：

In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step and the strategy of the central path to obtain an ϵ-approximate solution of LCP. This algorithm yields the best currently well-known theoretical complexity iteration bound, namely, (Formula presented.) which is as good as the bound for the linear optimization analogue. The implementation of the algorithm and the algorithm in Wang et al. (Fuzzy Inform Eng 54:479–487, 2009) is done followed by a comparison between these two obtained numerical results. © 2013, African Mathematical Union and Springer-Verlag Berlin Heidelberg.

引用

页码：139 / 151

页数：12

共 15 条

[1]

Achache M., A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math., 25, 1, pp. 97-110, (2006)

[2]

Achache M., A weighted path-following method for the linear complementarity problem, Studia Universitatis Babes-Bolyai Series Informatica, 49, 1, pp. 61-73, (2004)

[3]

Ben-Tal A., Nemirovski A., Lectures on modern convex optimization, Analysis, Algorithms and Engineering Applications, volume 2 of MPS-SIAM. Series on Optimization. SIAM, (2000)

[4]

Cottle R.W., Pang J.S., Stone R.E., The Linear Complementarity Problem, (1992)

[5]

Darvay Z., A weighted-path-following method for linear optimization, Studia Universitatis Babes-Bolyai Series Informatica, 47, 2, pp. 3-12, (2002)

[6]

Ding J., Li T.Y., An algorithm based on weighted logarithmic barrier functions for linear complementarity problems. Arabian, J. Sci. Eng, 15, 4B, pp. 679-685, (1990)

[7]

Kojima M., Mizuno S., Yoshize A., A polynomial-time algorithm for a class of linear complementarity problems, Math. Program., 44, pp. 1-26, (1989)

[8]

Jansen B., Roos R., Terlaky T., Primal-dual target-following algorithms for linear programming, Ann. Oper. Res., 62, pp. 197-231, (1996)

[9]

Peng J., Roos R., Terlaky T., New complexity analysis of the primal-dual Newton method for linear optimization, Ann. Oper. Res., 99, pp. 23-39, (2000)

[10]

Roos R., Terlaky T., Vial J.P., Theory and algorithms for linear optimization, An interior-Point Approach, (1997)

← 1 2 →