An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step

Document Type : Original paper

Authors

Azarbaijan Shahid Madani University

Abstract

An infeasible interior-point algorithm for solving the $P_*$-matrix linear complementarity problem based on a kernel function with trigonometric barrier term is analyzed. Each (main) iteration of the algorithm consists of a feasibility step and several centrality steps, whose feasibility step is induced by a trigonometric kernel function. The complexity result coincides  with the best result for infeasible interior-point methods for $P_*$-matrix linear complementarity problem.

Keywords

Main Subjects


[1] Ch.-P. Chen and F. Qi, Inequalities of some trigonometric functions, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 15 (2004), 71–78.
[2] T. Ill´es and M. Nagy, A mizuno-todd-ye type predictor-corrector algorithm for sufficient linear complementarity problems, European J. Oper. Res. 181 (2007), 1097–1111.
[3] J. Ji and F.A. Potra, An infeasible-interior-point method for the p∗-matrix lcp, Rev. Anal. Num´er. Th´eor. Approx. XXVII (1998), no. 2, 277–295.
[4] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), 375–395.
[5] B. Kheirfam, Full-newton step infeasible interior-point algorithm for sufficient linear complementarity problems, TOP Revised.
[6] B. Kheirfam, Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term, Numer. Algorithms 61 (2012), no. 4, 659–680.
[7] B. Kheirfam, A full nesterov-todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function, Numer. Algebra Contr. Optim. 3 (2013), no. 4, 601–614.
[8] B. Kheirfam, A full-newton step infeasible interior-point algorithm for linear complementarity problems based on a kernel function, Algor. Oper. Res. 7 (2013), 103–110.
[9] B. Kheirfam, A new complexity analysis for full-newton step infeasible interior-point algorithm for horizontal linear complementarity problems, J. Optim. Theory Appl. 161 (2014), no. 3, 853–869.
[10] M. Kojima, N. Megiddo, and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Program. 61 (1993), no. 3, 263–280.
[11] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems. lecture notes in comput. sci., vol. 538, Springer-Verlag, Berlin, 1991.
[12] Z. Liu, W. Sun, and F. Tian, A full-newton step infeasible interior-point algorithm for linear programming based on a kernel function, Appl. Math. Optim. 60 (2009), 237–251.
[13] I.J. Lustig, Feasible issues in a primal-dual interior-point method for linear programming, Math. Program. 49 (1990), no. 1-3, 145–162.
[14] J. Miao, A quadratically convergent O((1 + κ)√nl)-iteration algorithm for the p∗(κ)-matrix linear complementarity problem, Math. Program. 69 (1995), 355–368.
[15] S. Mizuno, Polynomiality of infeasible-interior-point algorithms for linear programming, Math. Program. 67 (1994), no. 1, 109–119.
[16] S. Mizuno, M.J. Todd, and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res. 18 (1993), no. 4, 964–981.
[17] F.A. Potra, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, Math. Program. 67 (1994), 383–406.
[18] , An o(nl) infeasible-interior-point algorithm for lcp with quadratic convergence, Ann. Oper. Res. 62 (1996), 81–102.
[19] F.A. Potra and R. Sheng, Predictor-corrector algorithm for solving p∗(κ)-matrix lcp from arbitrry positive starting points, Math. Program. 67 (1996), no. 1, 223–244.
[20] , A large step infeasible interior point method for the p∗-matrix lcp, SIAM J. Optim. 7 (1997), no. 2, 318–335.
[21] F. Qi, D.W. Niu, and B.N. Guo, Refinements, generalizations, and applications of jordan’s inequality and related problems, Journal of Inequalities and Applications (2009), no. Article ID 271923, 52 Pages.
[22] C. Roos, A full-newton step o(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), no. 4, 1110–1136.
[23] C. Roos, T. Terlaky, and J-Ph. Vial, Theory and algorithms for linear optimization. an interior-point approach, John Wiley and Sons, Chichester, UK, 1997.
[24] L. Zhang, Y.Q. Bai, and Y. Xu, A full-newton step infeasible interior- point algorithm for monotone lcp based on a locally-kernel function, Numer. Algorithms 61 (2012), no. 1, 57–81.
[25] Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim. 4 (1994), no. 1,
208–227.