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.