تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,146,439 |
تعداد دریافت فایل اصل مقاله | 1,004,990 |
An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step | ||
Communications in Combinatorics and Optimization | ||
مقاله 4، دوره 3، شماره 1، شهریور 2018، صفحه 51-70 اصل مقاله (515.65 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2018.25801.1038 | ||
نویسندگان | ||
Masoumeh Haghighi؛ | ||
Azarbaijan Shahid Madani University | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
Linear complementarity problem؛ Full-Newton step؛ Infeasible interiorpoint method؛ Kernel function؛ Polynomial complexity | ||
مراجع | ||
[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. | ||
آمار تعداد مشاهده مقاله: 1,234 تعداد دریافت فایل اصل مقاله: 1,136 |