×

An interior-point algorithm for \(P_{ast}(kappa)\)-linear complementarity problem based on a new trigonometric kernel function. (English) Zbl 1384.65034

Summary: In this paper, an interior-point algorithm for \(P_{\ast}(\kappa)\)-linear complementarity problem (LCP) based on a new parametric trigonometric kernel function is proposed. By applying strictly feasible starting point condition and using some simple analysis tools, we prove that our algorithm has \(O((1+2\kappa)\sqrt{n} \log n\log\frac{n}{\epsilon})\) iteration bound for large-update methods, which coincides with the best known complexity bound. Moreover, numerical results confirm that our new proposed kernel function is doing well in practice in comparison with some existing kernel functions in the literature.

MSC:

65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C51 Interior-point methods
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernelfunctions for primal-dual interior-point algorithms in linear optimiza-tion, SIAM J. Optim. 15 (2004) 101-128. · Zbl 1077.90038
[2] Y.Q. Bai, G. Lesaja and C. Roos, A new class of polynomial interior-point algorithms for P∗(κ)-linear complementary problems, Pac. J. Op-tim. 4 (2008) 19-41.194S. Fathi-Hafshejani, H. Mansouri and M. Reza Peyghami · Zbl 1161.90507
[3] M. Bouafia, D. Benterki and A. Yassine, An efficient primal-dual in-terior point method for linear programming problems based on a newkernel function with a trigonometric barrier term, J. Optim. TheoryAppl. 170 (2016) 528-545. · Zbl 1346.90568
[4] X.Z. Cai, G.Q. Wang, M. El Ghami and Y.J. Yue, Complexity analysisof primal-dual interior-point methods for linear optimization based ona new parametric kernel function with a trigonometric barrier term,Abstr. Appl. Anal. 2014 (2014) 1-11. · Zbl 1474.90275
[5] G.M. Cho, A new large-update interior-point algorithm for P∗(κ)-linear complementarity problems, Comput. Appli. Math. 216 (2008)265-278. · Zbl 1140.90043
[6] G.M. Cho and M.K. Kim, A new large-update interior-point algorithmfor P∗(κ)-LCPs based on kernel functions, Appli. Math. Comput. 182(2006) 1169-1183. · Zbl 1108.65061
[7] G.M. Cho, M.K. Kim and Y.H. Lee, Complexity of large-updateinterior-point algorithm for P∗(κ)-linear complementarity problems,Comput. Math. Appli. 53 (2007) 948-960. · Zbl 1135.90410
[8] R.W. Cottle, J.S. Pang and R.E. Stone, The Linear ComplementarityProblem, Academic Press Inc., San Diego, 1992. · Zbl 0757.90078
[9] M. El Ghami, Z.A. Guennoun, S. Boula and T. Steihaug, Interior-point methods for linear optimization based on a kernel function witha trigonometric barrier term, J. Comput. Appl. Math. 236 (2012)3613-3623. · Zbl 1242.90292
[10] M. El Ghami, Primal-dual interior-point methods for P∗(κ)-linearcomplementarity problem based on a kernel function with a trigono-metric barrier term, Optim. Theory Decis. Mak. Oper. Res. Appl. 31(2013) 331-349.
[11] S. Fathi-Hafshejani, M. Fatemi and M.R. Peyghami, An interior-pointmethod for P∗(κ)-linear complementarity problem based on a trigono-metric kernel function, J. Appl. Math. Comput. 48 (2015) 111-128. · Zbl 1323.90070
[12] Y. Fathi, Computational complexity of LCPs associated with positivedefinite symmetric matrices, Math. Prog. 17 (1971) 335-344.An interior-point algorithm for P∗(κ)-linear complementarity. . .195 · Zbl 0421.90072
[13] S. Fathi-Hafshejani, H. Mansouri and M.R. Peyghami, A large-updateprimal dual interior-point algorithm for second-order cone optimiza-tion based on a new proximity function, Optimization 65 (2016) 1477-1496. · Zbl 1397.90399
[14] S. Fathi-Hafshejani, A. Fakharzadeh and M.R. Peyghami, A uni-fied complexity analysis of interior point methods for semidefiniteproblems based on trigonometric kernel functions, Optimizatio, DOI:10.1080/02331934.2017.1387258 (2017). · Zbl 1398.90119
[15] M.C. Ferris and J.S. Pang, Complementarity and variational problemsstate of the art, In: Proceedings of the International Conference onComplementarity Problems. SIAM, Philadelphia, 1997)
[16] N.K. Karmarkar, A new polynomial-time algorithm for linear program-ming, In: Proceedings of the 16th Annual ACM Symposium on Theoryof Computing (1984) 302-311.
[17] B. Kheirfam, Primal-dual interior-point algorithm for semidefinite op-timization based on a new kernel function with trigonometric barrierterm, Numer. Algorithms 61 (2012) 659-680. · Zbl 1259.65091
[18] B. Kheirfam,A generic interior-point algorithm for monotone symmet-ric cone linear complementarity problems based on a new kernel func-tion, J. Math. Model. Algorithms Oper. Res. 13 (2014) 471-491. · Zbl 1311.90179
[19] B. Kheirfam and M. Moslemi, A polynomial-time algorithm for linearoptimization based on a new kernel function with trigonometric barrierterm, Yugosl. J. Oper. Res. 25 (2015) 233-250. · Zbl 1474.90279
[20] B. Kheirfam, A primal-dual interior-point algorithm for symmetric op-timization based on a new kernel function with trigonometric barrierterm yielding the best known iteration bounds, Afri. Math. 28 (2017)389-406. · Zbl 1365.90270
[21] M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A unified approachto interior-point algorithms for linear complementarity problems, InLecture Notes in Computer Science. Volume 538, Springer, Berlin,1991. · Zbl 0745.90069
[22] M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior-pointalgorithm for linear programming, In: Megiddo, N. (ed.) Progressin Mathematical Programming: Interior Point and Related Methods,Springer, New York, 1989.196S. Fathi-Hafshejani, H. Mansouri and M. Reza Peyghami · Zbl 0708.90049
[23] Y.H. Lee, Y.Y. Cho and G.M. Cho, Interior-point algorithms forP∗(κ)-LCP based on a new class of kernel functions, J. Glob. Optim.58 (2014) 137-149. · Zbl 1319.90069
[24] G. Lesaja and C. Roos, Unified analysis of kernel-based interior-pointmethods for P∗(κ)-linear complementarity problems, SIAM J. Optim.20 (2010) 3014-3039. · Zbl 1211.90160
[25] X. Li, M. Zhang and Y. Chen, An interior-point algorithm for P∗(κ)-LCP based on a new trigonometric kernel function with a double bar-rier term, J. Appl. Math. Comput. 53 (2017) 487-506. · Zbl 1391.90590
[26] X. Li and M. Zhang, Interior-point algorithm for linear optimizationbased on a new trigonometric kernel function, Oper. Res. Lett. 43(2015) 471-475. · Zbl 1408.90318
[27] N. Megiddo, Pathways to the optimal set in linear programming, In:Megiddo, N. (ed.) Progress in Mathematical Programming: InteriorPoint and Related Methods, pp. 131-158. Springer, New York, 1989 · Zbl 0687.90056
[28] Y.E. Nesterov and A.S. Nemirovskii, Interior point polynomial algo-rithms in convex programming, SIAM Studies in Applied Mathematics.Volume 13, SIAM, Philadelphia, 1994. · Zbl 0824.90112
[29] J. Peng, C. Roos and T. Terlaky, Self-Regularity A New Paradigm forPrimal-Dual Interior-Point Algorithms, Princeton University Press,Princeton, 2002. · Zbl 1136.90045
[30] M.R. Peyghami and K. Amini, A kernel function based interior-pointmethods for solving P∗(κ)-linear complementarity problem, Acta Math.Sin. 26 (2010) 1761-1778. · Zbl 1206.90195
[31] M.R. Peyghami and S. Fathi-Hafshejani, Complexity analysis ofan interior-point algorithm for linear optimization based on a newporiximity function, Numer. Algorithms 67 (2014) 33-48. · Zbl 1300.65042
[32] M.R. Peyghami, S. Fathi-Hafshejani and L. Shirvani,Complexity ofinterior-point methods for linear optimization based on a new trigono-metric kernel function, J. Comput. Appl. Math. 255 (2014) 74-85. · Zbl 1291.90313
[33] M.R. Peyghami and S. Fathi-Hafshejani, An interior point algorithmfor solving convex quadratic semidefinite optimization problems using anew kernel function, Iranian J. Math. Sci. Inform. 12 (2017) 131-152.An interior-point algorithm for P∗(κ)-linear complementarity. . .197 · Zbl 1375.90234
[34] M.R. Peyghami, S. Fathi-Hafshejani and S. Chen, A primal dualinterior-point method for semidefinite optimization based on a class oftrigonometric barrier functions, Oper. Res. Lett. 44 (2016) 319-323. · Zbl 1408.90319
[35] C. Roos, T. Terlaky and J.-P Vial, Theory and Algorithms for LinearOptimization: An Interior Point Approach, Springer, New York, 2005.
[36] G. Sonnevend, An analytic center for polyhedrons and new classesof global algorithms for linear (smooth, convex) programming, in: A.Prakopa, J. Szelezsan and B. Strazicky (Eds.). Lecture Notes in Con-trol and Information Sciences 84 (1986) 866-876.
[37] H. V¨aliaho, P∗-matrices are just sufficient, Linear Algebra Appl. 239(1999) 103-108. · Zbl 0851.15015
[38] Y. Ye, Interior-Point Algorithms:Theory and Analysis, Wiley-Interscience Series in Discrete Mathe-matics and Optimization. Wiley,Chichester, 1997. · Zbl 0943.90070
[39] Y. Fathi, Computational complexity of LCPs associated with positivedefinite matrices, Math. Program. 17 (1979) 335-344. · Zbl 0421.90072
[40] K.G. Murty,Linear Complementarity, Linear and Nonlinear Program-ming. Helderman-Verlag, Berlin, 1988. · Zbl 0634.90037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.