Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{*}\left(\kappa \right)$-LCP

Achache, Mohamed

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 131-143

In this paper, a weighted-path-following interior point algorithm for $P_{*}\left(\kappa \right)$-linear complementarity problems ($P_{*}\left(\kappa \right)$-LCP) is presented. The algorithm uses at each weighted interior point iteration only feasible full-Newton steps and the strategy of the central-path for getting a solution for $P_{*}\left(\kappa \right)$-LCP. We prove that the proposed algorithm has quadratically convergent with polynomial time. The complexity bound, namely, $O((1+\kappa )\sqrt{n}log\frac{n}{ϵ})$ of the algorithm is obtained. Few numerical tests are reported to show the efficiency of the algorithm.

Classification : 90C33, 90C51, 11Y16
Keywords: Linear complementarity problems, P_∗(κ)-matrix, weighted-path-following, interior-point methods, polynomial complexity

M. Achache, A weighted path-following method for the linear complementarity problem. Studia Univ. Babes-Bolyai, Informatica XLIX (2004) 61–73. | Zbl | MR

M. Achache and R. Khebchache, A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP. Afrika Matematika 26 (2015) 139–151. | Zbl | MR | DOI

G.M. Cho, Large-update interior point algorithm for $P_{*}$-linear complementarity problem. J. Inequalities Appl. 363 (2014) 1–12. | MR

R.W. Cottle, J.S. Pang and R.E. Stone, The linear complementarity problem. Academic Press, San Deigo (1992). | Zbl | MR

Zs. Darvay, A weighted-path-following method for linear optimization. Studia Univ. Babes-Bolyai, Informatica XLVII (2002). | Zbl | MR

J. Ding and T.Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems. Arab. J. Sci. Eng. 15 (1990) 679–685. | Zbl | MR

T. Illés and M. Nagy, The Mizuno-Todd-Ye predictor-corrector algorithm for sufficient matrix linear complementarity problem. Oper. Res. report (2004). | Zbl | MR

B. Jansen, C. Roos, T. Terlaky and J.Ph. Vial, Primal-dual target-following algorithms for linear programming. Ann. Oper. Res. 62 (1997) 197–231. | Zbl | MR | DOI

H. Mansouri and H. Asadi, A quadratically convergent $O\left((1+\kappa )\sqrt{n}\right)$ interior point algorithm for the $P_{*}\left(\kappa \right)-$ matrix horizontal linear complementarity problem. J. Sci. Islamic Republic of Iran 23 (2012) 237–244. | MR

I. Pólik, Novel analysis of interior point methods for linear optimization problems [in Hungarian]. Msc thesis, Eotvos Lorand University of Sciences. Faculty of Natural Sciences, Budapest (2002).

C. Roos, T. Terlaky and J. Ph. Vial, Theory and Algorithms for Linear optimization. An Interior Point Approach. John Wiley and Sons, Chichester (1997). | Zbl | MR

G.Q. Wang and Y.Q. Bai, Polynomial interior-point algorithms for $P_{*}\left(\kappa \right)$-horizontal linear complementarity problem. J. Comput. Appl. Math. 233 (2009) 249–263. | Zbl | MR

G.Q. Wang, Y.J. Yue and X.Z. Cai, A weighted path-following method for monotone horizontal linear complementarity problem. Fuzzy Inform. Eng. 54 (2009) 479–487. | Zbl | DOI

G.Q. Wang, X.J. Fan, D.T. Zhu and D.Z. Wang, New complexity analysis of a full-Newton step feasible interior point algorithm for $P_{*}\left(\kappa \right)$-LCP. Optim. Lett. 9 (2015) 1105–1119. | Zbl | MR | DOI

G.Q. Wang, C.J. Yu and K.L. Teo, A full-Newton step feasible interior-point algorithm for $P_{*}\left(\kappa \right)$-linear complementarity problem. J. Global Optim. 59 (2014) 81–99. | Zbl | MR | DOI

S.J. Wright, Primal-dual interior point methods. Copyright by SIAM (1997). | Zbl | MR