Document Type : Research Paper
Authors
Department of Mathematics and Statistics, Imam Hossein Comprehensive University, Tehran, Iran.
Abstract
An infeasible interior-point algorithm for mixed symmetric cone linear complementarity problems is proposed. Using the machinery of Euclidean Jordan algebras and Nesterov-Todd search direction, the convergence analysis of the algorithm is shown and proved. Moreover, we obtain a polynomial time complexity bound which matches the currently best known iteration bound for infeasible interior-point methods.
Keywords
Main Subjects
[1] M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems, Appl. Math. Comput., 216 (2010), pp. 1889-1895.
[2] M. Achache and R. Khebchache, A full-Newton step feasible weighted primal-dual interior-point algorithm for monotone LCP, Afr. Mat., 26 (2015), pp. 139-151.
[3] J. Faraut and A. Koranyi, Analysis on symmetric cones, Oxford University Press, New York, 1994.
[4] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), pp. 331-357.
[5] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge 1986.
[6] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, in: Lecture Notes in Computer Science, vol. 538, Springer-Verlag, Berlin, Germany 1991.
[7] Y. Lin and A. Yoshise, A homogeneous model for mixed complementarity problems over symmetric cones, Vietnam J. Math., 35 (2007), pp. 541-561.
[8] H. Masouri and M. Pirhaji, A polynomial interior-point algorithm for monotone linear complementarity problems, J. Optim. Theory Appl., 157 (2013), pp. 451-461.
[9] H. Masouri, M. Zangiabadi, and M. Pirhaji, A full Newton step $O(n)$ infeasible-interior-point algorithm for linear complementarity problems, Nonlinear Anal., Real World Appl., 12 (2011), pp. 454-561.
[10] H. Masouri, M. Zangiabadi, and M. Pirhaji, A path-following feasible interior-point algorithm for mixed symmetric cone linear complementarity problems, Journal of New Researches in Mathematics, 1 (2016), pp. 109-120.
[11] S.H. Schmieta and F. Alizadeh, Extension of primal dual interior-point algorithms to symmetric cones, Math. Program. Ser. A, 96 (2003), pp. 409-438.
[12] J.F. Sturm, Similarity and other spectral relations for symmetric cones, Linear Algebra Appl. 312 (2000), pp. 135-154.
[13] G.Q. Wang, Y. Yue, and X.Z. Ci, Weighthed-path-following interior-point algorithm to monotone mixed linear complementarity problem, Fuzzy Inf. Eng., 4 (2009), pp. 435-445.
[14] M. Zangiabadi, G. Gu, and C. Roos, A full Nesterov Todd step infeasible interior-point method for second-order cone optimization, J. Optim. Theory. Appl., 158 (2013), pp. 816-858.
[2] M. Achache and R. Khebchache, A full-Newton step feasible weighted primal-dual interior-point algorithm for monotone LCP, Afr. Mat., 26 (2015), pp. 139-151.
[3] J. Faraut and A. Koranyi, Analysis on symmetric cones, Oxford University Press, New York, 1994.
[4] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), pp. 331-357.
[5] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge 1986.
[6] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, in: Lecture Notes in Computer Science, vol. 538, Springer-Verlag, Berlin, Germany 1991.
[7] Y. Lin and A. Yoshise, A homogeneous model for mixed complementarity problems over symmetric cones, Vietnam J. Math., 35 (2007), pp. 541-561.
[8] H. Masouri and M. Pirhaji, A polynomial interior-point algorithm for monotone linear complementarity problems, J. Optim. Theory Appl., 157 (2013), pp. 451-461.
[9] H. Masouri, M. Zangiabadi, and M. Pirhaji, A full Newton step $O(n)$ infeasible-interior-point algorithm for linear complementarity problems, Nonlinear Anal., Real World Appl., 12 (2011), pp. 454-561.
[10] H. Masouri, M. Zangiabadi, and M. Pirhaji, A path-following feasible interior-point algorithm for mixed symmetric cone linear complementarity problems, Journal of New Researches in Mathematics, 1 (2016), pp. 109-120.
[11] S.H. Schmieta and F. Alizadeh, Extension of primal dual interior-point algorithms to symmetric cones, Math. Program. Ser. A, 96 (2003), pp. 409-438.
[12] J.F. Sturm, Similarity and other spectral relations for symmetric cones, Linear Algebra Appl. 312 (2000), pp. 135-154.
[13] G.Q. Wang, Y. Yue, and X.Z. Ci, Weighthed-path-following interior-point algorithm to monotone mixed linear complementarity problem, Fuzzy Inf. Eng., 4 (2009), pp. 435-445.
[14] M. Zangiabadi, G. Gu, and C. Roos, A full Nesterov Todd step infeasible interior-point method for second-order cone optimization, J. Optim. Theory. Appl., 158 (2013), pp. 816-858.
)